|Definition of a regular grammar email@example.com (Colin Manning) (2002-03-09)|
|Re: Definition of a regular grammar firstname.lastname@example.org.OZ.AU (Peter Gammie) (2002-03-11)|
|Re: Definition of a regular grammar email@example.com (ANDREI Stefan) (2002-03-11)|
|Re: Definition of a regular grammar firstname.lastname@example.org (2002-03-11)|
|Re: Definition of a regular grammar email@example.com (2002-03-11)|
|Re: Definition of a regular grammar firstname.lastname@example.org (Peter H. Froehlich) (2002-03-17)|
|From:||email@example.com (Jason Lee Eckhardt)|
|Date:||11 Mar 2002 02:13:01 -0500|
|Organization:||Rice University, Houston, TX|
|Posted-Date:||11 Mar 2002 02:13:01 EST|
Colin Manning <firstname.lastname@example.org> wrote:
>I had always assumed that any grammar (Type 3) that contained only
>productions of the form
>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
A left-linear grammar contains only productions of the form:
while a right-linear grammar contains only productions of the form:
(for x in star-closure(alphabet), A&B in the variables).
See almost any text on formal languages/automata theory for more
>Do I need to refine my definition of a Type 3? What's missing?
Return to the
Search the comp.compilers archives again.