Re: Re:Making an NFA into a grammar

vannoord@let.rug.nl
24 Aug 2001 00:47:41 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.