To be a right-linear grammar, *every* production of the grammar must
have one of the two forms V
T*V or V T*.

To be a left-linear grammar, *every* production of the grammar must
have one of the two forms V
VT* or V T*.

You do *not* get to mix the two.
For example, consider a grammar with the following
productions:

This grammar is neither right-linear nor left-linear, hence it is not a regular grammar. We have no reason to suppose that the language it generates is a regular language (one that is generated by a dfa).

In fact, the grammar generates a language whose strings are of the form ab. This language cannot be recognized by a dfa. (Why not?)

Copyright © 1996 by David Matuszek

Last modified Feb 11, 1996