11 Mar 2002 02:13:13 -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: | robin@kitsite.com (Robin Houston) |

Newsgroups: | comp.compilers |

Date: | 11 Mar 2002 02:13:13 -0500 |

Organization: | http://groups.google.com/ |

References: | 02-03-040 |

Keywords: | parse |

Posted-Date: | 11 Mar 2002 02:13:13 EST |

"Colin Manning" <colinjunk@hotmail.com> 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.*

As you've observed, that's not true. Any grammar that contains only

productions of the form

A -> Bx

A -> x

has to be regular (you can just view the non-terminal symbols as

states in a finite state machine and adjoin a new distinct final

state). Similarly any grammar that contains only productions

A -> xB

A -> x

will also be regular, for the same reason. But you can't mix the two.

(The above remains true even if 'x' can be a string of terminal

symbols, or even any regular expression over the terminal symbols,

rather than just a single symbol.)

.robin.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.