Re: Definition of a regular grammar

"Peter H. Froehlich" <pfroehli@ics.uci.edu>
17 Mar 2002 22:40:08 -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: "Peter H. Froehlich" <pfroehli@ics.uci.edu>
Newsgroups: comp.compilers
Date: 17 Mar 2002 22:40:08 -0500
Organization: Compilers Central
References: 02-03-040
Keywords: parse, theory
Posted-Date: 17 Mar 2002 22:40:08 EST

Hi there!


On Saturday, March 9, 2002, at 12:12 , Colin Manning wrote:


> 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?


The difference is that the second grammar has mutually recursive
productions (X and Y). Personally, the definition of "type 3" that
I find most intuitive is:


      A grammar is regular if you can rewrite it into a single,
non-recursive
      EBNF production.


If you try this for your second grammar, you get stuck when
replacing X for Y or Y for X depending on how you transform.


Disclaimer: I just had a quick glance at your grammar, so I might
be completely wrong. I learned the hard way that these things
usually take a little time to work out. :-)


Peter
--
Peter H. Froehlich []->[!]<-[] http://nil.ics.uci.edu/~phf/
OpenPGP: D465 CBDD D9D2 0D77 C5AF 353E C86C 2AD9 A6E2 309E


Post a followup to this message

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