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

"valentin tihomirov" <spam@abelectron.com> wrote
> 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?


As you probably know, each Chomsky grammar is a device, which
generates some formal language (a set of strings). So, type 3 grammar
also defines some formal language. And this language can be defined by
applying three basic operations to vocabulary (terminals of the
grammar) of the language. These operations are: concatenation,
alternation and Kleene closure. each language that can be constructed
by using these three operations is named as regular. The text with
such the definition of operations applying to vocabulary is named as
regular expression. For instance, we have vocabulary V={a,b,c} and the
ragular expression a*(b|c). The expresion defines the formal language
L={b,c,ab,ac,aab,...}. This language can be defined also by using
Chomsky type 3 grammar:


S --> A B
S --> A C
A --> epsilon
A --> a A
A --> a
B --> b
C --> c


There is a theorem, which says each regular language (i.e. language,
which can be constructed by using three operation above) can be
defined by using three equivalent devices: Chomsky type 3 grammar,
regular expression and finite state machine. Thus, such the
equivalence is the reason to name type 3 grammars as "regular" ones.


Vladimir.

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