388 ~ Solutions (or Hints) to Chapter-end Exercises
generate a 1 c 1 for 1 2:: 1. 5 -'t b5 1 c, 51 -'t b5 1 c, 51 -'t bc generate b'''d''
for m 2:: 1. For getting a 1b/lld"c
1
, we have to apply 5 -'t a5c I times;
5 -'t bc, 5 -'t b5 1 c, 51 -'t b5 1 c and 51 -'t bc are to be applied. For
m = 1, 5 -'t bc has to be applied. For m > 1, we have to apply
5 -'t b5 i c, 51 -'t b5 1 c and 51 -'t bc repeatedly. The terminal c is added
whenever the terminal a or b is added in the course of the derivation.
This takes care of the condition 1 + m = n.
(e) Let G be a context-free grammar whose productions are
5 ---1 5051505, 5 -'t 5050515, 5 -'t 5150505, 5 -'t A. It is easy to see
that elements in L(G) are in L. Let W E L. We prove that W E L(G)
by induction on Iwi. Note that every string in L is of length 3n,
n 2:: 1. When Iwi = 3, W has to be one of 010, 001 or 100. These
strings can be derived by applying 5 -'t 5051505, 5 -'t 5050515 and
5 -'t 5150505 and then 5 -'t A. Thus there is basis for induction.
Assume the result for all strings of length 3n - 3. Let W ELand let
\wi =3n,w should contain one of 010, 001 or 100 as a substring. Call
the substring W1' Write w = W2WiW3' Then IW2W31 = 3n - 3 and by
induction hypothesis 5 ~ W2W3' Note that all the productions (except
S -'t A) yield a sentential form staning and ending with 5 and having
the symbol 5 between every pair of terminals. Without loss of
generality, we can assume that the last step in the derivation
5 ~ w2w3 is of the form w25w3 => W2W3' SO, 5 => W25w3' But
WI ELand so 5:b WI' Thus, 5:b W2WiW3' In other words, W E L(G).
By the principle of induction, L = L(G).
4.11 The required productions are:
(a) 5 -'t a5 1 , 5) -'t a5, 5 -'t a5 2 , 52 -'t a
(b) 5 -'t a5, 5 -'t b5, 5 -'t a
(c) 5 -'t a5 1 , 51 -'t a5 1 , 51 -'t bS\o 51 -'t a, 5) -'t b
(d) 5 -'t a5), 51 -'t a5 1 , 51 -'t b5 2 , 52 -'t b5 2 , 53 -'t c5 3 , 53 ---1 C
(e) 5 -'t a5 1 , 51 -'t b5, 5 -'t a5 2 , 52 -'t b.
4.12 :b is not symmetric and so the relation is not an equivalence relation
(Refer to Note (ii), page 109)
4.13 It is clear that L(G)) = {a"b" I 11 2:: 1}. In G 2 , 5 => AC => A5B :b
A"-) 5B"-). Also, 5 => AB :b abo Hence 5 :b a"b" for all 11 2:: 1. Tnis
means L(G 2 ) = {a"b" I11 2:: 1} = L(G)).
4.14 L(G) = 0, for we get a variable on the application of each production
and so no terminal string results.
4.15 The required productions are 5 -'t a5), 5) -'t b5 2 , 52 -'t C, 5 ---1 b5 3 ,
53 -'t c5 4 , 54 -'t a, 5 -'t c5 5 , 55 -'t a5 6 , S6 -'t b.
4.16 The required productions are 5 ---1 5\0 51 -'t ab5), 51 -'t ab, S -'t 52,
52 -'t ba5 2 , 52 -'t ba.
generate a 1 c 1 for 1 2:: 1. 5 -'t b5 1 c, 51 -'t b5 1 c, 51 -'t bc generate b'''d''
for m 2:: 1. For getting a 1b/lld"c
1
, we have to apply 5 -'t a5c I times;
5 -'t bc, 5 -'t b5 1 c, 51 -'t b5 1 c and 51 -'t bc are to be applied. For
m = 1, 5 -'t bc has to be applied. For m > 1, we have to apply
5 -'t b5 i c, 51 -'t b5 1 c and 51 -'t bc repeatedly. The terminal c is added
whenever the terminal a or b is added in the course of the derivation.
This takes care of the condition 1 + m = n.
(e) Let G be a context-free grammar whose productions are
5 ---1 5051505, 5 -'t 5050515, 5 -'t 5150505, 5 -'t A. It is easy to see
that elements in L(G) are in L. Let W E L. We prove that W E L(G)
by induction on Iwi. Note that every string in L is of length 3n,
n 2:: 1. When Iwi = 3, W has to be one of 010, 001 or 100. These
strings can be derived by applying 5 -'t 5051505, 5 -'t 5050515 and
5 -'t 5150505 and then 5 -'t A. Thus there is basis for induction.
Assume the result for all strings of length 3n - 3. Let W ELand let
\wi =3n,w should contain one of 010, 001 or 100 as a substring. Call
the substring W1' Write w = W2WiW3' Then IW2W31 = 3n - 3 and by
induction hypothesis 5 ~ W2W3' Note that all the productions (except
S -'t A) yield a sentential form staning and ending with 5 and having
the symbol 5 between every pair of terminals. Without loss of
generality, we can assume that the last step in the derivation
5 ~ w2w3 is of the form w25w3 => W2W3' SO, 5 => W25w3' But
WI ELand so 5:b WI' Thus, 5:b W2WiW3' In other words, W E L(G).
By the principle of induction, L = L(G).
4.11 The required productions are:
(a) 5 -'t a5 1 , 5) -'t a5, 5 -'t a5 2 , 52 -'t a
(b) 5 -'t a5, 5 -'t b5, 5 -'t a
(c) 5 -'t a5 1 , 51 -'t a5 1 , 51 -'t bS\o 51 -'t a, 5) -'t b
(d) 5 -'t a5), 51 -'t a5 1 , 51 -'t b5 2 , 52 -'t b5 2 , 53 -'t c5 3 , 53 ---1 C
(e) 5 -'t a5 1 , 51 -'t b5, 5 -'t a5 2 , 52 -'t b.
4.12 :b is not symmetric and so the relation is not an equivalence relation
(Refer to Note (ii), page 109)
4.13 It is clear that L(G)) = {a"b" I 11 2:: 1}. In G 2 , 5 => AC => A5B :b
A"-) 5B"-). Also, 5 => AB :b abo Hence 5 :b a"b" for all 11 2:: 1. Tnis
means L(G 2 ) = {a"b" I11 2:: 1} = L(G)).
4.14 L(G) = 0, for we get a variable on the application of each production
and so no terminal string results.
4.15 The required productions are 5 -'t a5), 5) -'t b5 2 , 52 -'t C, 5 ---1 b5 3 ,
53 -'t c5 4 , 54 -'t a, 5 -'t c5 5 , 55 -'t a5 6 , S6 -'t b.
4.16 The required productions are 5 ---1 5\0 51 -'t ab5), 51 -'t ab, S -'t 52,
52 -'t ba5 2 , 52 -'t ba.