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

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

2
checked on Nov 19, 2017

Page view(s)

58
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.