11 Mar 2002 02:08:44 -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: | ANDREI Stefan <stefan@infoiasi.ro> |

Newsgroups: | comp.compilers |

Date: | 11 Mar 2002 02:08:44 -0500 |

Organization: | Compilers Central |

References: | 02-03-040 |

Keywords: | parse, theory |

Cc: | <compilers@iecc.com> |

Posted-Date: | 11 Mar 2002 02:08:44 EST |

Dear Colin Manning,

*> On 9 Mar 2002, Colin Manning wrote:*

*> 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.*

The grammar is not regular, instead it is linear grammar. A grammar

is called linear if its productions have the form:

A -> p B

A -> B p

A -> p

where A,B are nonterminals and p is a word over the set of terminals.

An equivalent definition is specifying the productions:

A -> p1 B p2

A -> p1

with the same notations.

The class of linear grammars is bigger than the class of regular

grammars.

Please, don't confuse the class of linear languages and the class

of regular languages. A language is called linear if there exists

a linear grammar which generates it.

I think you did this "misunderstanding" maybe because there is another

general theorem:

Theorem. "The language generated by a context free grammar over

a set of terrminals with only one letter in the terminal alphabet

is regular."

So, because the linear grammars are context free, by applying this

previous theorem, it results that the language generated by your

grammar is REGULAR, although your grammar is NOT 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.*

Yes, the language is L(G)={a^n b^n | n >= 1} which is linear language,

but not regular. The point is that the set of terminal symbols has two

symbols !!

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

Please, add to Chomsky hierarchy the class of linear grammars between

context free grammars and regular grammars.

Yours sincerely,

Stefan Andrei

Ph-D, Faculty of Computer Science

"Al.I.Cuza" University

Iasi, ROMANIA

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.