17 Mar 2002 22:40:08 -0500

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

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.