Re: Q: CFG and regular languages

scavadini@ucse.edu.ar writes:
>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.

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