Re: Regular grammar from CFG?
13 Sep 2004 10:50:17 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: Regular grammar from CFG? (2004-09-07)
Re: Regular grammar from CFG? (Ben Brosgol) (2004-09-08)
Re: Regular grammar from CFG? (2004-09-08)
Re: Regular grammar from CFG? (Friedrich Neurauter) (2004-09-08)
Re: Regular grammar from CFG? (Carl Cerecke) (2004-09-08)
Re: Regular grammar from CFG? (2004-09-13)
Re: Regular grammar from CFG? (2004-09-13)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 13 Sep 2004 10:50:17 -0400
Organization: Compilers Central
References: 04-09-035 04-09-042
Keywords: parse, theory, bibliography
Posted-Date: 13 Sep 2004 10:50:17 EDT

>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
* 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,, Iasi
University, Romania (2002) 1-25.


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)

Post a followup to this message

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