A Note on a Completely Linearly Nested Context-Free Grammar and Its Generalization

Tetsuo MORITA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E77-A  No.12  pp.2106-2108
Publication Date: 1994/12/20
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms, Data Structures and Computational Complexity
Keyword: 
context-free grammar,  linear language,  substitution of languages, 

Full Text: PDF

Summary: 
We introduce a generalized cln grammar (gclng), a generalization of a completely linearly nested context-free grammar (clncfg), of which variables are partitioned linearly and each rule satisfies similar conditions as those of clncfg related to its partition. We show that the class of languages generated by gclng's coincides with the class of quasi-rational languages, and consider the inclusion relations between languages generated by gclng's and those generated by clncfg's.