|Q: CFG and regular languages firstname.lastname@example.org (Salvador Valerio Cavadini) (2002-09-22)|
|Re: Q: CFG and regular languages email@example.com (A Johnstone) (2002-09-25)|
|Re: Q: CFG and regular languages firstname.lastname@example.org (Hannah Schroeter) (2002-09-25)|
|Re: Q: CFG and regular languages debray@CS.Arizona.EDU (Saumya K. Debray) (2002-09-25)|
|Re: Q: CFG and regular languages email@example.com (Paolo Bonzini) (2002-09-29)|
|Re: Q: CFG and regular languages firstname.lastname@example.org (Mark) (2002-09-29)|
|From:||"Hannah Schroeter" <email@example.com>|
|Date:||25 Sep 2002 23:58:10 -0400|
|Organization:||Schlund + Partner AG|
|Posted-Date:||25 Sep 2002 23:58:10 EDT|
Salvador Valerio Cavadini <firstname.lastname@example.org> wrote:
>I'm looking for an algorithm for determine if a context free grammar
>generates a regular language. Any idea?
>[Hmmn. Would it suffice to check that there's no direct or indirect
>recursion in the rules? -John]
Your condition is sufficient, but not necessary.
A -> <epsilon>
A -> a A
surely generates a regular language (as every CFG with only one
terminal symbol does!), but has recursion.
In http://compilers.iecc.com/comparch/article/01-08-107  there is
mention that the decision problem whether a CFG generates a regular
language is undecidable in general.
 or http://compilers.iecc.com/comparch/article/01-08-127
Return to the
Search the comp.compilers archives again.