Re: Q: CFG and regular languages

"Paolo Bonzini" <bonzini@gnu.org>
29 Sep 2002 15:44:45 -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: "Paolo Bonzini" <bonzini@gnu.org>
Newsgroups: comp.compilers
Date: 29 Sep 2002 15:44:45 -0400
Organization: http://groups.google.com/
References: 02-09-132
Keywords: parse
Posted-Date: 29 Sep 2002 15:44:45 EDT

> 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]


Not, because


  A -> a A | empty


is obviously regular. You could try to solve the grammar (considering
it as an equation), like


  A -> a B | empty
  B -> A b | c B


becoming


  A -> a c* A b | empty


and look for Terminal+ NonTerminal+ Terminal+ sequences in the
original grammar and at each step of the solution.


To solve the grammar apply standard transformations to change left-
and right-recursion into EBNF. Then either you found that the CFG is
not regular, or you got rid of references to the LHS on the RHS and
you can substitute the EBNF you found into the other rules.


Example:


  A -> a A b | A A | empty


becomes


  A -> (a A b)*


which is not regular.


In the other example above, the steps are


  A -> a B | empty
  B -> A b | c B


becoming


  A -> a B | empty
  B -> c* A b


and then substituting B into A says that, again, the grammar isn't
regular.


Paolo


Post a followup to this message

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