z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom