11 Mar 2002 02:13:01 -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: | jle@forest.owlnet.rice.edu (Jason Lee Eckhardt) |

Newsgroups: | comp.compilers |

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

Organization: | Rice University, Houston, TX |

References: | 02-03-040 |

Keywords: | parse, theory |

Posted-Date: | 11 Mar 2002 02:13:01 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.*

*>*

Not quite. A grammar with those productions is not necessarily regular.

However, a grammar that is _either_ left-linear or right-linear is a

regular grammar.

A left-linear grammar contains only productions of the form:

A->Bx

A->x

while a right-linear grammar contains only productions of the form:

A->xB

A->x

(for x in star-closure(alphabet), A&B in the variables).

See almost any text on formal languages/automata theory for more

info.

*>Do I need to refine my definition of a Type 3? What's missing?*

*>*

See above.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.