Re: Q: CFG and regular languages

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