Re: Regular grammar from CFG?

>Can anyone tell me how to determine if a given CFG can be represented
>as a regular grammar?
>If so, what method can be used to generate the right-linear grammar?


A couple of years ago I did the same question in this group.


The problem is undecidable in general: given ANY CFG it's impossible
to determine if the language generated is regular or not.


But there are some particular cases where you can give an answer to
the question (including an equivalent regular grammar), for example:


* if the CF grammar's alphabet is unary, the language is regular
* if the CFG is not self-embedded, the language is regular


Also, there are some special case of self-embedded CFG that generate
regular languages.


You can read the following articles:


* Stefan Andrei, Wei-Ngan Chin, Salvador Valerio Cavadini: Self-embedded
context-free grammars with regular counterparts. Acta Inf. 40(5): 349-365
(2004)
n
* Stefan Andrei, Salvador Valerio Cavadini, Wei-Ngan Chin: A new algorithm
for regularizing one-letter context-free grammars. Theor. Comput. Sci.
306(1-3): 113-122 (2003)


* Stefan Andrei, Salvador Cavadini y Wei-Ngan Chin. "Transforming
self-embedded context-free grammars into regular expressions". Faculty of
Computer Science. TR02-06, http://www.infoiasi.ro/~tr/tr.pl.cgi, Iasi
University, Romania (2002) 1-25.




Regards


Salvador Valerio Cavadini
Centro de Investigación y Desarrollo de Software (CIDESOFT)
Facultad de Matemática Aplicada
Universidad Católica de Santiago del Estero (Argentina)
web: http://www.ucse.edu.ar/fma/staff/svcavadini

Return to the comp.compilers page.
Search the comp.compilers archives again.