Re: Re:Making an NFA into a grammar
24 Aug 2001 00:47:41 -0400

          From comp.compilers

Related articles
Re:Making an NFA into a grammar (Vinay Kakade) (2001-08-20)
Re: Re:Making an NFA into a grammar (2001-08-24)
| List of all articles for this month |

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 <> 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 van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.