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

mefrill@yandex.ru (Vladimir)
21 Oct 2004 22:19:44 -0400

          From comp.compilers

Related articles
Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-10-17)
Re: Why Chomsky Type 3 grammars are called "Regular"? mefrill@yandex.ru (2004-10-21)
Re: Why Chomsky Type 3 grammars are called "Regular"? torbenm@diku.dk (2004-10-21)
Re: Why Chomsky Type 3 grammars are called "Regular"? dev@gioelebarabucci.com (Gioele Barabucci) (2004-10-23)
Re: Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-11-28)
Re: Why Chomsky Type 3 grammars are called "Regular"? torbenm@diku.dk (2004-12-01)
Re: Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-12-05)
Re: Why Chomsky Type 3 grammars are called "Regular"? henry@spsystems.net (2004-12-11)
| List of all articles for this month |

From: mefrill@yandex.ru (Vladimir)
Newsgroups: comp.compilers
Date: 21 Oct 2004 22:19:44 -0400
Organization: http://groups.google.com
References: 04-10-111
Keywords: parse, theory
Posted-Date: 21 Oct 2004 22:19:44 EDT

"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.


Post a followup to this message

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