|Definition of a regular grammar email@example.com (Colin Manning) (2002-03-09)|
|Re: Definition of a regular grammar firstname.lastname@example.org.OZ.AU (Peter Gammie) (2002-03-11)|
|Re: Definition of a regular grammar email@example.com (ANDREI Stefan) (2002-03-11)|
|Re: Definition of a regular grammar firstname.lastname@example.org (2002-03-11)|
|Re: Definition of a regular grammar email@example.com (2002-03-11)|
|Re: Definition of a regular grammar firstname.lastname@example.org (Peter H. Froehlich) (2002-03-17)|
|From:||"Peter H. Froehlich" <email@example.com>|
|Date:||17 Mar 2002 22:40:08 -0500|
|Posted-Date:||17 Mar 2002 22:40:08 EST|
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
> had to be regular.
> But consider this grammar
> 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,
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 H. Froehlich ->[!]<- http://nil.ics.uci.edu/~phf/
OpenPGP: D465 CBDD D9D2 0D77 C5AF 353E C86C 2AD9 A6E2 309E
Return to the
Search the comp.compilers archives again.