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

torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
1 Dec 2004 23:04:26 -0500

          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: torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers
Date: 1 Dec 2004 23:04:26 -0500
Organization: Department of Computer Science, University of Copenhagen
References: 04-10-111 04-10-144 04-11-114
Keywords: parse, theory
Posted-Date: 01 Dec 2004 23:04:26 EST

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


> Regular expressions can be used to describe type2 languages; therefore I'm
> asking the question. Why T3 steals the name which should pertaining to T2?


Regular expressions _alone_ can not describe _all_ type-2 languages.
Since any type-3 language is also a type-2 language, regular
expressions can describe _some_ type-2 languages. Additionally,
regular expressions _extended_ with non-regular features like
recursion or substring matching can describe some non-type-3
languages. I don't know which of above the you have seen.


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.


                Torben

Post a followup to this message

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