8 Sep 2004 00:06:30 -0400

Related articles |
---|

Regular grammar from CFG? netsch@ti.com (Lorin Netsch) (2004-09-03) |

Re: Regular grammar from CFG? newsserver_mails@bodden.de (Eric Bodden) (2004-09-07) |

Re: Regular grammar from CFG? vannoord@let.rug.nl (2004-09-07) |

Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08) |

Re: Regular grammar from CFG? vbdis@aol.com (2004-09-08) |

Re: Regular grammar from CFG? friedrich.neurauter@eunet.at (Friedrich Neurauter) (2004-09-08) |

Re: Regular grammar from CFG? cdc@maxnet.co.nz (Carl Cerecke) (2004-09-08) |

Re: Regular grammar from CFG? neal.wang@gmail.com (2004-09-13) |

Re: Regular grammar from CFG? scavadini@ucse.edu.ar (2004-09-13) |

From: | Ben Brosgol <brosgol@worldDOTstd.com> |

Newsgroups: | comp.compilers |

Date: | 8 Sep 2004 00:06:30 -0400 |

Organization: | The World : www.TheWorld.com : Since 1989 |

References: | 04-09-035 |

Keywords: | parse, theory |

Posted-Date: | 08 Sep 2004 00:06:30 EDT |

Lorin Netsch wrote:

*> Can anyone tell me how to determine if a given CFG can be represented*

*> as a regular grammar?*

*>*

*> If so, what method can be used to generate the right-linear grammar?*

Whether an arbitrary CFG generates a regular language is undecidable.

(Theorem 4.2.2 in Seymour Ginsburg's "The Mathematical Theory of

Context-Free Languages").

The following was listed as an open problem by Ginsburg (in 1966); I'm

not sure if it's still open:

"Let G be an arbitrary [context-free] grammar. Suppose it is known that

L(G) is regular. Is it solvable to find a right-linear grammar G' such

that L(G) = L(G')?"

Ben Brosgol

brosgol at gnat.com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.