Solutions (or Hints) to Chapter-end Exercises J;;t, 387
productions are 5 -7 alAI, Al -7 azA z , ... A",_I -7 am generate
{w}.
4.7 We prove (a) 5 ~ A {'A z 'A 4 , (b) A;'A2'A 4 ::; d,2 Az 'A 4 , (c) A z 'A{'A 4 ~
az,,+I.
We first prove (a). 5 ~ A:04 ~ A I A:0zA 4 :b Aj'- I A:0:£,-IA 4 ~
A(,-IA I A z A:£,-jA 4 (We are applying A 3 -7 A jA:0z(n - 2) times and
A 3 -7 AjA z once.) Hence (a). To prove (b) start with A('A:!'A 4 . Then
A{,-IA j A z A:£,-IA 4 ~ A{'-laA z A I A:£'-IA 4 ~ A{'-zaA I A z A j A:£,-jA 4 ~
A ,,-zdAA A A~,-IA ~A'l-zdAoA aAoA A~l-zA :;A,,-zdAoA AoA A~l-zA ~
j
_II~
4
I
_j~j~
4
I
_I~I_
4
A{'-Za3AzaAzAIAIA:£,-zA4 ::; a 4 A {,-zAlA rA:!,-zA4.
.' ,}
Proceeding in a similar way, we get Al'A:£'A 4 =:, a"-A:£'A I "A 4 ·
Hence (b).
Finally, A z 'Aj'A 4 ~ A 2 'A{'-IA 4 a ::; A 2 'A 4 a" ~ A:!,-IAsa',+1 ::; A s a
2
"
~ az,,+I. (We apply A I A 4 -7 A 4 a, A z A 4 -7 Asa, AzA s -7 Asa and
finally As -7 a).
Using (a), (b) and (c), we get 5 ~ a(,,+1)2.
4.8 The productions for (i) are 5 -7 a5 1 B, a5 -7 aa, B -7 a. For (ii) the
productions are 5 -7 A51 a, A -7 a. For (iii) the productions are
5 -7 a51 a.
4.9 The required grammar G = ({5, 51, A, B}, 1:, P, 5), where 1: =
{O, 1, 2, ..., 9} and P consists of
5 -7 °1214161 8, 5 -7 A5 1 , A -7 1 12 I 19
51 -7 °121 416 I8, 5 -7 AB5j, B -7 1 I2I 19
5 -7 °I2 14 I 6 I 8 generate even integers with one digit.
5 -7 A5 1 and A-productions and 5 1 -productions generate all even
numbers with two digits. The remaining productions can be used to
generate all even integers with three digits.
4.10 (a) G = ({5, A, B}, {O, I}, P, 5), where P consists of 5 -7 0511 OA
lIB 1°11, A -7 OA I0, B -7 IB 11. Using 5 -7 051, 5 -7 0,
5 -7 1, we can get 0"'1", where m and differ by 1. To get more O's
(than I's) in the string we have to apply A -7 OA 10, 5 -7 OA
repeatedly. To get more l's, apply 5 -7 IB, B -7 IB 11 repeatedly.
(b) The required productions are 5 -7 a5 1 , 51 -7 b5 l c, 51 -7 bc,
5 -7 a5 z c, 5 z -7 a5 z c, 5 z -7 b, 5 -7 5 3 c, 53 -7 a5 3 b, 53 -7 abo The
first three productions derive ab"c". 5 -7 a5 z c and the 5 r productions
generate a"bc". The remaining productions generate a"b"c.
(c) The required productions are 5 -7 051, 5 -7 01, 5 -7 OAI, A -7
lA, A -7 1.
(d) The required productions are 5 -7 a5c, 5 -7 ac, 5 -7 bc, 5 -7
b5 l c, 51 -7 b5 l c, 51 -7 bc. A typical string in the given language can
be written in the form alb'''cl/lc l where 1, m 2' : 0. 5 -7 a5c, 5 -7 bc
productions are 5 -7 alAI, Al -7 azA z , ... A",_I -7 am generate
{w}.
4.7 We prove (a) 5 ~ A {'A z 'A 4 , (b) A;'A2'A 4 ::; d,2 Az 'A 4 , (c) A z 'A{'A 4 ~
az,,+I.
We first prove (a). 5 ~ A:04 ~ A I A:0zA 4 :b Aj'- I A:0:£,-IA 4 ~
A(,-IA I A z A:£,-jA 4 (We are applying A 3 -7 A jA:0z(n - 2) times and
A 3 -7 AjA z once.) Hence (a). To prove (b) start with A('A:!'A 4 . Then
A{,-IA j A z A:£,-IA 4 ~ A{'-laA z A I A:£'-IA 4 ~ A{'-zaA I A z A j A:£,-jA 4 ~
A ,,-zdAA A A~,-IA ~A'l-zdAoA aAoA A~l-zA :;A,,-zdAoA AoA A~l-zA ~
j
_II~
4
I
_j~j~
4
I
_I~I_
4
A{'-Za3AzaAzAIAIA:£,-zA4 ::; a 4 A {,-zAlA rA:!,-zA4.
.' ,}
Proceeding in a similar way, we get Al'A:£'A 4 =:, a"-A:£'A I "A 4 ·
Hence (b).
Finally, A z 'Aj'A 4 ~ A 2 'A{'-IA 4 a ::; A 2 'A 4 a" ~ A:!,-IAsa',+1 ::; A s a
2
"
~ az,,+I. (We apply A I A 4 -7 A 4 a, A z A 4 -7 Asa, AzA s -7 Asa and
finally As -7 a).
Using (a), (b) and (c), we get 5 ~ a(,,+1)2.
4.8 The productions for (i) are 5 -7 a5 1 B, a5 -7 aa, B -7 a. For (ii) the
productions are 5 -7 A51 a, A -7 a. For (iii) the productions are
5 -7 a51 a.
4.9 The required grammar G = ({5, 51, A, B}, 1:, P, 5), where 1: =
{O, 1, 2, ..., 9} and P consists of
5 -7 °1214161 8, 5 -7 A5 1 , A -7 1 12 I 19
51 -7 °121 416 I8, 5 -7 AB5j, B -7 1 I2I 19
5 -7 °I2 14 I 6 I 8 generate even integers with one digit.
5 -7 A5 1 and A-productions and 5 1 -productions generate all even
numbers with two digits. The remaining productions can be used to
generate all even integers with three digits.
4.10 (a) G = ({5, A, B}, {O, I}, P, 5), where P consists of 5 -7 0511 OA
lIB 1°11, A -7 OA I0, B -7 IB 11. Using 5 -7 051, 5 -7 0,
5 -7 1, we can get 0"'1", where m and differ by 1. To get more O's
(than I's) in the string we have to apply A -7 OA 10, 5 -7 OA
repeatedly. To get more l's, apply 5 -7 IB, B -7 IB 11 repeatedly.
(b) The required productions are 5 -7 a5 1 , 51 -7 b5 l c, 51 -7 bc,
5 -7 a5 z c, 5 z -7 a5 z c, 5 z -7 b, 5 -7 5 3 c, 53 -7 a5 3 b, 53 -7 abo The
first three productions derive ab"c". 5 -7 a5 z c and the 5 r productions
generate a"bc". The remaining productions generate a"b"c.
(c) The required productions are 5 -7 051, 5 -7 01, 5 -7 OAI, A -7
lA, A -7 1.
(d) The required productions are 5 -7 a5c, 5 -7 ac, 5 -7 bc, 5 -7
b5 l c, 51 -7 b5 l c, 51 -7 bc. A typical string in the given language can
be written in the form alb'''cl/lc l where 1, m 2' : 0. 5 -7 a5c, 5 -7 bc