Re: Q: CFG and regular languages

"Hannah Schroeter" <hannah@schlund.de>
25 Sep 2002 23:58:10 -0400

          From comp.compilers
Related articles
Q: CFG and regular languages scavadini@ucse.edu.ar (Salvador Valerio Cavadini) (2002-09-22)
Re: Q: CFG and regular languages adrian@sartre.cs.rhbnc.ac.uk (A Johnstone) (2002-09-25)
Re: Q: CFG and regular languages hannah@schlund.de (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 bonzini@gnu.org (Paolo Bonzini) (2002-09-29)
Re: Q: CFG and regular languages whopkins@alpha2.csd.uwm.edu (Mark) (2002-09-29)
| List of all articles for this month |
From: "Hannah Schroeter" <hannah@schlund.de>
Newsgroups: comp.compilers
Date: 25 Sep 2002 23:58:10 -0400
Organization: Schlund + Partner AG
References: 02-09-132
Keywords: parse, theory
Posted-Date: 25 Sep 2002 23:58:10 EDT

Hello!


Salvador Valerio Cavadini <scavadini@ucse.edu.ar> 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 [1] there is
mention that the decision problem whether a CFG generates a regular
language is undecidable in general.


Kind regards,


Hannah.


[1] or http://compilers.iecc.com/comparch/article/01-08-127

Post a followup to this message

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