Re: Definition of a regular grammar

jle@forest.owlnet.rice.edu (Jason Lee Eckhardt)
11 Mar 2002 02:13:01 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.