Re: Why Chomsky Type 3 grammars are called "Regular"?

> Regular expressions _alone_ can not describe _all_ type-2 languages.


Really? I cannot imagine such a construction. In CF grammars, every
non-terminal is mapped to a set of alternative productions. The repeatedly
occuring writing can be short-handed by using Kneele star, ?, + and *
operators. From the Dragon Book "Forms involving the repetition operators *,
+ or ? and possibly the separators ( and ) are called *regular
expressions*." The CF forms using REs are called Extended CF of regular
right part grammars. Do Type3 (RE) languages use any *regular left parts*,
what makes them truly regular? In my opinion, any stream of symbols is
always RE even if it contains no regularities (like ABC), so please explain,
which rules cannot be described with REs?


> Try reading chapter 1-7 of Hopcroft, Motwani & Ullman's "Introduction
> to automata theory, languages and computation" or chapter 1-8 of Linz'
> "An introduction to formal languages and automata" for precise
> characterisations of type-2 and type-3 languages and their properties.
> Other books about languages and automata will also do, these just
> happened to be what I had with arms reach.


Can you please bring the excerpts just to clarify the notion of Regular
Language, where the roots are coming form? I'm familiar with their formal
definitions.

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