Re: Definition of a regular grammar

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

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