Re: Regular Language

vannoord@let.rug.nl
29 Jul 2000 23:18:09 -0400

          From comp.compilers
Related articles
Regular Language thomaspan2000@aol.com (2000-07-23)
Re: Regular Language nospam411@my-deja.com (2000-07-27)
Re: Regular Language vannoord@let.rug.nl (2000-07-29)
| List of all articles for this month |
From: vannoord@let.rug.nl
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

nospam411@my-deja.com 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 http://www.let.rug.nl/~vannoord

Post a followup to this message

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