Length Synchronization Context-Free Grammars
Author(s) -
Madhu Mutyam,
Kamala Krithivasan
Publication year - 2004
Publication title -
j. autom. lang. comb.
Language(s) - English
DOI - 10.25596/jalc-2004-457
We propose a new type of regulation on the derivation of a context-free grammar: the productions used for passing from a level of a derivation tree to the next level should have the right-hand members of the same length. We prove that such length synchronized context-free grammars characterize the family of ETOL languages, and therefore are equivalent with the synchronization context-free grammars of H. Juirgensen and K. Salomaa. In this way, a conjecture of H. Jurgensen and K. Salomaa is disproved, about a language which was conjectured not to be generated by a synchronization context-free grammar.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom