24 Aug 2001 00:47:41 -0400

Related articles |
---|

Re:Making an NFA into a grammar kvinay@ip.eth.net (Vinay Kakade) (2001-08-20) |

Re: Re:Making an NFA into a grammar vannoord@let.rug.nl (2001-08-24) |

From: | vannoord@let.rug.nl |

Newsgroups: | comp.compilers |

Date: | 24 Aug 2001 00:47:41 -0400 |

Organization: | Faculteit der Letteren, Rijksuniversiteit Groningen, NL |

References: | 01-08-117 |

Keywords: | parse, theory |

Posted-Date: | 24 Aug 2001 00:47:41 EDT |

Vinay Kakade <kvinay@ip.eth.net> wrote:

*> According to my knowledge, a grammar for a regular language can be of*

*> two types: 1. Right Linear Grammar: 2. Left Linear Grammar:*

in such cases you are *guaranteed* that the language is regular. But

of course, in many cases a context-free grammar not in this form will

'happen' to define a regular language. It seemed to me that the

original poster was looking for an algorithm that would be able

to recognize such cases. However, since it is undecidable whether a

context-free grammar defines a regular language, such an algorithm

cannot exist. cf. Hopcroft and Ullman, chapter 8.

Gertjan

--

Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen

vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.