Solutions (or Hints)to Chapter-end Exercises ~ 403
6.21 (a) Suppose G = (V N , L, P, S) is right-linear. A production of the
form A ~ a]a2 ... amB, m ~ 2 can be replaced by A ~ alA],
A] ~ a2A2 ..., A m _] ~ amB. A ~ b]b 2 ... b m , m ~ 2, can be
replaced by A ~ bIB], B] ~ b 2 B b ... , B m - 2 ~ blll_]B m _], B m _] ~
b m . The required equivalent regular grammar G' is defined by the new
productions constructed above.
If G =(VN, L, P, S) is left-linear, then an equivalent right-linear
grammar can be defined as G) =(V'N, L, Ph S), where PI consists of
(i) S ~ W when S ~ W is in P and W E L*,
(ii) S ~ wA when A ~ W is in P and W E L*,
(iii) A ~ wB when B ~ Aw is in P and w E L*,
(iv) A ~ w when S ~ Aw is in P and w E L*.
Let w E L(G). If S => w then S ~ w is in P. Therefore, S ~ w is
in PI (by (i».
Assume S => Alwl => A2W2W] => ... Am_1w m _] ... WI => WmWm_1
... WI =W is a derivation in G. Then the productions applied in the
derivation are S ~ Alw], A] ~ A2W2, ..., A IIl - 1 ~ W m . The induced
productions in G] are
A] ~ WI, A 2 ~ W2A h A 3 ~ W02, ., ., S ~ wlI,Am-]
(by (ii), (iii) and (iv)' in the construction of PI)'
Taking the productions in the reverse order we get a derivation of G]
as follows:
Thus L(G) ~ L(G'). The other inclusion can be proved in a similar
way. So G is equivalent to a right-linear grammar G] which is
equivalent to a regular grammar.
(b) Let G = ({S, A}, {a, b, e}, P, S). where P consists of S ~
Sc IAc, A ~ aAb lab. G is linear (by the presence of A ~ aAb).
L(G) = {allbl/ellli m, n ~ I}
Using pumping lemma we prove that L(G) is not regular. Let n be the
number of states in a finite automaton accepting L(G).
Let w =a'W'c". By pumping lemma w =xyz, where Ixyl ::; nand
Iy I > O. If y =J< then xz =a"-kYle". This is not in L(G). By pumping
lemma. xz E L(G) a contradiction.
6.22 L =L(G), where G is a regular grammar. For every variable A in G.
A :b ex implies ex =uB, where u E L* and B E V, Thus Gis nonselfembedding. To prove the sufficiency part, assume that G is a nonselfembedding, context-free grammar. If G' is reduced, in Greibach
normal form and equivalent to G, then G' is also nonself-embedding.
(This can be proved.) Let IL I =nand m be the maximum of the
lengths of right-hand sides of productions in G'. Let ex be any
6.21 (a) Suppose G = (V N , L, P, S) is right-linear. A production of the
form A ~ a]a2 ... amB, m ~ 2 can be replaced by A ~ alA],
A] ~ a2A2 ..., A m _] ~ amB. A ~ b]b 2 ... b m , m ~ 2, can be
replaced by A ~ bIB], B] ~ b 2 B b ... , B m - 2 ~ blll_]B m _], B m _] ~
b m . The required equivalent regular grammar G' is defined by the new
productions constructed above.
If G =(VN, L, P, S) is left-linear, then an equivalent right-linear
grammar can be defined as G) =(V'N, L, Ph S), where PI consists of
(i) S ~ W when S ~ W is in P and W E L*,
(ii) S ~ wA when A ~ W is in P and W E L*,
(iii) A ~ wB when B ~ Aw is in P and w E L*,
(iv) A ~ w when S ~ Aw is in P and w E L*.
Let w E L(G). If S => w then S ~ w is in P. Therefore, S ~ w is
in PI (by (i».
Assume S => Alwl => A2W2W] => ... Am_1w m _] ... WI => WmWm_1
... WI =W is a derivation in G. Then the productions applied in the
derivation are S ~ Alw], A] ~ A2W2, ..., A IIl - 1 ~ W m . The induced
productions in G] are
A] ~ WI, A 2 ~ W2A h A 3 ~ W02, ., ., S ~ wlI,Am-]
(by (ii), (iii) and (iv)' in the construction of PI)'
Taking the productions in the reverse order we get a derivation of G]
as follows:
Thus L(G) ~ L(G'). The other inclusion can be proved in a similar
way. So G is equivalent to a right-linear grammar G] which is
equivalent to a regular grammar.
(b) Let G = ({S, A}, {a, b, e}, P, S). where P consists of S ~
Sc IAc, A ~ aAb lab. G is linear (by the presence of A ~ aAb).
L(G) = {allbl/ellli m, n ~ I}
Using pumping lemma we prove that L(G) is not regular. Let n be the
number of states in a finite automaton accepting L(G).
Let w =a'W'c". By pumping lemma w =xyz, where Ixyl ::; nand
Iy I > O. If y =J< then xz =a"-kYle". This is not in L(G). By pumping
lemma. xz E L(G) a contradiction.
6.22 L =L(G), where G is a regular grammar. For every variable A in G.
A :b ex implies ex =uB, where u E L* and B E V, Thus Gis nonselfembedding. To prove the sufficiency part, assume that G is a nonselfembedding, context-free grammar. If G' is reduced, in Greibach
normal form and equivalent to G, then G' is also nonself-embedding.
(This can be proved.) Let IL I =nand m be the maximum of the
lengths of right-hand sides of productions in G'. Let ex be any