Note that in a regular grammar, at most one variable appears on the right side
of any production. Furthermore, that variable must consistently be either the
rightmost or leftmost symbol of the right side of any production.
Example 3.13
The grammar G 1 = ({S}, {a,b},S,P 1 ), with P 1 given as
S abS|a
is right-linear. The grammar G 2 = ({S, S 1 , S 2 }, {a, b}, S, P 2 ), with productions
S S 1 ab,
S 1 S 1 ab|S 2 ,
S 2 a,
is left-linear. Both G1 and G2 are regular grammars.
The sequence
S ⇒ abS ⇒ ababS ⇒ababa
is a derivation with G 1 . From this single instance it is easy to conjecture that L
(G 1 ) is the language denoted by the regular expression r = (ab)* a. In a similar
way, we can see that L(G 2 ) is the regular language L(aab(ab)*).
Example 3.14
The grammar G =({S, A, B}, {a, b}, S, P) with productions
S A
A aB|λ,