Definition of a regular grammar

"Colin Manning" <colinjunk@hotmail.com>
9 Mar 2002 03:12:02 -0500

          From comp.compilers
Related articles
Definition of a regular grammar colinjunk@hotmail.com (Colin Manning) (2002-03-09)
Re: Definition of a regular grammar peteg@cs.mu.OZ.AU (Peter Gammie) (2002-03-11)
Re: Definition of a regular grammar stefan@infoiasi.ro (ANDREI Stefan) (2002-03-11)
Re: Definition of a regular grammar jle@forest.owlnet.rice.edu (2002-03-11)
Re: Definition of a regular grammar robin@kitsite.com (2002-03-11)
Re: Definition of a regular grammar pfroehli@ics.uci.edu (Peter H. Froehlich) (2002-03-17)
| List of all articles for this month |
From: "Colin Manning" <colinjunk@hotmail.com>
Newsgroups: comp.compilers
Date: 9 Mar 2002 03:12:02 -0500
Organization: Compilers Central
Keywords: parse, theory, question
Posted-Date: 09 Mar 2002 03:12:02 EST

Hi.


I had always assumed that any grammar (Type 3) that contained only
productions of the form
A->Bx
A->xB
A->x
had to be regular.


But consider this grammar
S->aX
X->Yb
Y->aX
X->b


It generates any number of as followed by the same number of bs. Such a
language is not regular.


Do I need to refine my definition of a Type 3? What's missing?


Colin Manning
Dept. of Maths & Computing
Cork INstitute of Technology

Post a followup to this message

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