29 Sep 2002 17:01:38 -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: | "Mark" <whopkins@alpha2.csd.uwm.edu> |

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 |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.