Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00236-003-0133-8
 Title: Self-embedded context-free grammars with regular counterparts Authors: Andrei, S. Chin, W.-N. Cavadini, S.V. Issue Date: 2004 Source: Andrei, S., Chin, W.-N., Cavadini, S.V. (2004). Self-embedded context-free grammars with regular counterparts. Acta Informatica 40 (5) : 349-365. ScholarBank@NUS Repository. https://doi.org/10.1007/s00236-003-0133-8 Abstract: In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as X \alpha X and \gamma X \gamma , that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain. © Springer-Verlag 2004. Source Title: Acta Informatica URI: http://scholarbank.nus.edu.sg/handle/10635/43065 ISSN: 00015903 DOI: 10.1007/s00236-003-0133-8 Appears in Collections: Staff Publications

###### Files in This Item:
There are no files associated with this item.

#### SCOPUSTM Citations

7
checked on Feb 15, 2018

#### WEB OF SCIENCETM Citations

2
checked on Jan 29, 2018

#### Page view(s)

60
checked on Feb 12, 2018