Re: Regular Language
29 Jul 2000 23:18:09 -0400

          From comp.compilers

Related articles
Regular Language (2000-07-23)
Re: Regular Language (2000-07-27)
Re: Regular Language (2000-07-29)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 29 Jul 2000 23:18:09 -0400
Organization: Faculteit der Letteren, Rijksuniversiteit Groningen, NL
References: 00-07-045 00-07-078
Keywords: parse, theory wrote:
> I suppose if you can show that the language grammar has a production
> of the form

> A->BC,
> where B and C are non-terminals you have your proof. Regular
> languages have to have no more than a single non terminal on
> either side in any production in the grammar, going by
> chomsky's hierarchy.

It is not that simple, of course. You are mixing up regular *languages*
versus regular *grammars*. It is trivial to define a non-regular grammar
for a regular language.
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.