Re: Definition of a regular grammar

    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

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