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

"valentin tihomirov" <spam@abelectron.com> writes:


> The context free grammars written using RegExps in their rules are called
> extended CF grammars or regular right part grammars. Why the Type 3 grammars
> expropriate the RE definition, what does the "regular" mean?


Chomsky type 3 grammars can describe the same set of languages as
regular expressions, i.e., the regular languages. Hence the name.


Allowing regular expressions over terminals and nonterminals in
context-free grammars does not allow them to recognize more languages,
as the regular expressions can be eliminated by rewriting the grammar.
They do, however, make some languages marginally more compact to
describe (though only up to a constant factor).


The Chomsky hierarchy describes both a hierarchy of grammars and a
hierarchy of language classes. Each of these language classes have a
multitude of different equivalent characterizations, both by variant
forms of grammars and by automata. Examples:


Type 3: Left regular grammars, Right regular grammars, regular
                  expressions, deterministic finite automata, indeterministic
                  finite automata, ...


Type 2: Context free grammars, nondeterministic one-way pushdown
                  automata, syntax diagrams, ...


Type 1: Context sensitive grammars (several variants),
                  nodeterministic linear-bounded Turing machines, ...


Type 0: Unrestricted grammars, Turing machines, any Turing-complete
                  programming language.




Torben

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