29 Sep 2002 15:44:45 -0400

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

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.