Re: Q: CFG and regular languages

> 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

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