25 Sep 2002 23:59:02 -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: | "Saumya K. Debray" <debray@CS.Arizona.EDU> |

Newsgroups: | comp.compilers |

Date: | 25 Sep 2002 23:59:02 -0400 |

Organization: | University of Arizona CS Department, Tucson AZ |

References: | 02-09-132 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2002 23:59:02 EDT |

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?*

The problem is undecidable. See Theorem 8.15 in "Introduction

to Automata Theory, Languages, and Computation", by Hopcroft

and Ullman.

--

Saumya Debray

Dept. of Computer Science, University of Arizona, Tucson

debray@cs.arizona.edu

http://www.cs.arizona.edu/people/debray

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.