For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Note on a Completely Linearly Nested Context-Free Grammar and Its Generalization
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/12/25
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms, Data Structures and Computational Complexity
context-free grammar, linear language, substitution of languages,
Full Text: PDF(203.5KB)>>
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.