Economical transformations of phrase-structure grammars to scattered context grammars

This paper presents a transformation that converts any phrase-structure grammar, H, in Penttonen normal form to an equivalent scattered context grammar whose size differs from the size of H quite insignificantly; specifically, G has only five more nonterminals, four more context-dependent production...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Meduna Alexander
Dokumentumtípus: Cikk
Megjelent: 1998
Sorozat:Acta cybernetica 13 No. 3
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12588
Leíró adatok
Tartalmi kivonat:This paper presents a transformation that converts any phrase-structure grammar, H, in Penttonen normal form to an equivalent scattered context grammar whose size differs from the size of H quite insignificantly; specifically, G has only five more nonterminals, four more context-dependent productions, and one more context-free production than H. An analogical result holds for Kuroda normal form, too.
Terjedelem/Fizikai jellemzők:225-242
ISSN:0324-721X