Re: Definition of a regular grammar

robin@kitsite.com (Robin Houston)
11 Mar 2002 02:13:13 -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: robin@kitsite.com (Robin Houston)
Newsgroups: comp.compilers
Date: 11 Mar 2002 02:13:13 -0500
Organization: http://groups.google.com/
References: 02-03-040
Keywords: parse
Posted-Date: 11 Mar 2002 02:13:13 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.


As you've observed, that's not true. Any grammar that contains only
productions of the form
A -> Bx
A -> x
has to be regular (you can just view the non-terminal symbols as
states in a finite state machine and adjoin a new distinct final
state). Similarly any grammar that contains only productions
A -> xB
A -> x
will also be regular, for the same reason. But you can't mix the two.


(The above remains true even if 'x' can be a string of terminal
symbols, or even any regular expression over the terminal symbols,
rather than just a single symbol.)


  .robin.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.