9 Mar 2002 03:12:02 -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: | "Colin Manning" <colinjunk@hotmail.com> |

Newsgroups: | comp.compilers |

Date: | 9 Mar 2002 03:12:02 -0500 |

Organization: | Compilers Central |

Keywords: | parse, theory, question |

Posted-Date: | 09 Mar 2002 03:12:02 EST |

Hi.

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?

Colin Manning

Dept. of Maths & Computing

Cork INstitute of Technology

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.