EXAMPLE $3\mathrm{.}14$

The grammar $G=(\{S,A,B\},\{a,b\},S,P)$ with productions $SA,$

$AaB|,|$

$BAb,$

is not regular. Although every production is either in right$-$linear or left$-$linear form, the grammar itself is neither right$-$linear nor leftlinear, and therefore is not regular. The grammar is an example of a linear grammar. A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable. Clearly, a regular grammar is always linear, but not all linear grammars are regular.