# Re: Q: CFG and regular languages

## "Mark" <whopkins@alpha2.csd.uwm.edu>29 Sep 2002 17:01:38 -0400

From comp.compilers

Related articles
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: "Mark" Newsgroups: comp.compilers Date: 29 Sep 2002 17:01:38 -0400 Organization: University of Wisconsin - Milwaukee, Computing Services Division References: 02-09-132 Keywords: parse, theory Posted-Date: 29 Sep 2002 17:01:38 EDT

>I'm looking for an algorithm for determine if a context free grammar
>generates a regular language. Any idea?

Let A be a subset of X*, and v a word in X*. Define

dA/dv = { w in X*: vw is in A }
Then note that
dA/d1 = A; dA/d(vw) = d/dw (dA/dv).

Let <A> denote the closure of A under derivatives:
<A> = { dA/dv: v in X* }.

If <A> is finite then A is regular and if A is regular, then <A> is finite.

Given a grammar for A, a corresponding grammar for the derivatives dA/dv
can be defined relatively easily.

However, to test the finiteness of <A> requires determining whether the
derivatives dA/dv and dA/dw are equal for general v, w in X*; which
requires telling when two grammars produce the same set. No finite
set of rules can completely test equivalence.

Post a followup to this message