8 Sep 2004 12:05:49 -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: | "Friedrich Neurauter" <friedrich.neurauter@eunet.at> |

Newsgroups: | comp.compilers |

Date: | 8 Sep 2004 12:05:49 -0400 |

Organization: | Compilers Central |

References: | 04-09-035 04-09-042 |

Keywords: | parse, theory |

Posted-Date: | 08 Sep 2004 12:05:49 EDT |

"Eric Bodden" <newsserver_mails@bodden.de> schrieb

*> On 3 Sep 2004 12:42:40 -0400, Lorin Netsch wrote:*

*>*

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

*> > as a regular grammar?*

*>*

*> I believe there can be no way to do so, since I think, there is no way*

*> to convert a grammar that is more than regular to one that is regular.*

*> That is due to the Chomsky hierarchy. Type-3 grammars (regular ones)*

*> are strictly weaker then Type-2 and so forth.*

*>*

*> Regular grammars allow rules of the types*

*> A -> aB*

*> A -> a*

This is not quite correct. Take a look at the definitions of left linear,

right linear, strongly left linear and strongly right linear grammars

*>*

*> Now just imagine the possible productions of a grammar that is not yet*

*> regular:*

*> - A -> B This cannot be represented by a rule of the ones above.*

But this is a so called unit production which can be easily removed from

any grammar without changing the generated language.

*> - A -> Ba The same.*

In a left linear grammar productions like this are allowed and yet left

linear grammars generate regular languages

*> ... and so forth.*

*>*

*> So in my eyes either a grammar is already regular or it is not. And if it*

*> is not it will never be. Please correct me, if I am wrong.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.