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

henry@spsystems.net (Henry Spencer)
11 Dec 2004 12:23:31 -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: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 11 Dec 2004 12:23:31 -0500
Organization: SP Systems, Toronto, Canada
References: 04-10-111 04-11-114 04-12-009 04-12-029
Keywords: theory, lex
Posted-Date: 11 Dec 2004 12:23:31 EST

valentin tihomirov <spam@abelectron.com> wrote:
>> Regular expressions _alone_ can not describe _all_ type-2 languages.
>
>...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?


Consider:


expression = number | expression "+" number | "(" expression ")"


The first recursion can be converted to a Kleene "*" operator, but the
second can't be -- a finite regular expression can't match balanced
parentheses (and only balanced parentheses) to an arbitrary nesting depth.
--
"Think outside the box -- the box isn't our friend." | Henry Spencer
                                                                -- George Herbert | henry@spsystems.net



Post a followup to this message

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