398 g Solutions (or Hints) to Chapter-end Exercises
Step 3 We eliminate unit productions. We then have
W(S) = {S} W(A) = {A], WeE) = {E} Wo(B) = {B},
W](B) = {B} u {C}, W 2 {B) = {B, C} u {D},
W 3 (B) = {B, C, D, E} = W(B) , W(e) = {C, D, E}, WeD) = {D, E}.
The productions in the new grammar G 3 are S ~ AB, A ~ a,
B ~ b, B ~ a and E ~ a. G 3 contains the redundant symbol E. So
G 3 is not the equivalent grammar in the most simplified form.
6.12 (a) As there are no null productions or unit productions, we can
proceed to step 2.
Step 2 Let G I = (V;y, {O, I}, Pj, S), where PI and V;v are
constructed as follows:
(i) A ~ 0, B ~ 1 are included in Pj.
(ii) S ~ lA, B ~ IS give rise to S ~ CIA, B ~ CIS and C I ~ 1.
(iii) S ~ OB, A ~ OS give rise to S ~ CoB, A ~ CaS and Co ~ 0.
(iv) A ~ lAA, B ~ OBB give rise to A ~ ClAA and B ~ CoBB.
V~y = {S, A, B, Co' Cd.
Step 3 G 2 = (Vil, [0. I}, P 2 , 5), where P 2 and v,~, are constructed
as follows:
(i) A ~ 0, B ~ 1, S ~ CIA, B ~ CjS, Cj ~ 1, S ~ CoB,
A ~ CaS, Co ~ °are included in P2•
(ii) A ~ ClAA and B ~ CoBB are replaced by A ~ CIDj, D 1 ~
AA, B ~ CoD2' D 2 ~ BB.
Thus, G 2 = ({S, A, B, Co, Cj, Dj. D 2 }, {O, I}, P 2 , S) is in CNF and
equivalent to the given grammar where P 2 consists of S ~ CjAICoB,
A ~ O!CoS!CIDj, B ~ 1IC I SICoD2, C I ~ 1, Co ~ 0, D I ~ AA and
D 2 ~ BB.
(b) Step 2 G I = (V'x, {a, b, C}, Pj, S), where PI and V'N are
defined as follows:
(i) S ~ a, S ~ b are included in PI
(ii) S ~ cSS is replaced by S ~ CSS, C ~ c, V",v = {S, C}
Step 3 G 2 = (V,<:, {a, b, C}, P 2 , S). where P 2 is defined as follows:
(i) S ~ a, S ~ b, C ~ C are included in P 2 •
(ii) S ~ CSS is replaced by S ~ CD and D ~ SS.
Thus, the equivalent grammar in CNF is G 2 =({S, C, D}, {a, b, c},
P 2 , S). where P 2 consists of S ~ albl CD, C ---;} c, D ---;} SS.
6.13 Consider G =({S}, {a. b, +, *}, P, S), where P consists of S ---;} S + S,
S ---;} S * S. S ~ a, S ~ b.
Step 2 G I = (V(, {a, b, +, 8}, P lo S), where P j is constructed as
follows:
(i) S ~ a, S ~ b are included in PI,
(ii) S ~ S + Sand S ~ S * S are replaced by S ~ SAS, S ~ SBS,
A ~ +, B ~ *
V~· = {S, A, B}
Step 3 We eliminate unit productions. We then have
W(S) = {S} W(A) = {A], WeE) = {E} Wo(B) = {B},
W](B) = {B} u {C}, W 2 {B) = {B, C} u {D},
W 3 (B) = {B, C, D, E} = W(B) , W(e) = {C, D, E}, WeD) = {D, E}.
The productions in the new grammar G 3 are S ~ AB, A ~ a,
B ~ b, B ~ a and E ~ a. G 3 contains the redundant symbol E. So
G 3 is not the equivalent grammar in the most simplified form.
6.12 (a) As there are no null productions or unit productions, we can
proceed to step 2.
Step 2 Let G I = (V;y, {O, I}, Pj, S), where PI and V;v are
constructed as follows:
(i) A ~ 0, B ~ 1 are included in Pj.
(ii) S ~ lA, B ~ IS give rise to S ~ CIA, B ~ CIS and C I ~ 1.
(iii) S ~ OB, A ~ OS give rise to S ~ CoB, A ~ CaS and Co ~ 0.
(iv) A ~ lAA, B ~ OBB give rise to A ~ ClAA and B ~ CoBB.
V~y = {S, A, B, Co' Cd.
Step 3 G 2 = (Vil, [0. I}, P 2 , 5), where P 2 and v,~, are constructed
as follows:
(i) A ~ 0, B ~ 1, S ~ CIA, B ~ CjS, Cj ~ 1, S ~ CoB,
A ~ CaS, Co ~ °are included in P2•
(ii) A ~ ClAA and B ~ CoBB are replaced by A ~ CIDj, D 1 ~
AA, B ~ CoD2' D 2 ~ BB.
Thus, G 2 = ({S, A, B, Co, Cj, Dj. D 2 }, {O, I}, P 2 , S) is in CNF and
equivalent to the given grammar where P 2 consists of S ~ CjAICoB,
A ~ O!CoS!CIDj, B ~ 1IC I SICoD2, C I ~ 1, Co ~ 0, D I ~ AA and
D 2 ~ BB.
(b) Step 2 G I = (V'x, {a, b, C}, Pj, S), where PI and V'N are
defined as follows:
(i) S ~ a, S ~ b are included in PI
(ii) S ~ cSS is replaced by S ~ CSS, C ~ c, V",v = {S, C}
Step 3 G 2 = (V,<:, {a, b, C}, P 2 , S). where P 2 is defined as follows:
(i) S ~ a, S ~ b, C ~ C are included in P 2 •
(ii) S ~ CSS is replaced by S ~ CD and D ~ SS.
Thus, the equivalent grammar in CNF is G 2 =({S, C, D}, {a, b, c},
P 2 , S). where P 2 consists of S ~ albl CD, C ---;} c, D ---;} SS.
6.13 Consider G =({S}, {a. b, +, *}, P, S), where P consists of S ---;} S + S,
S ---;} S * S. S ~ a, S ~ b.
Step 2 G I = (V(, {a, b, +, 8}, P lo S), where P j is constructed as
follows:
(i) S ~ a, S ~ b are included in PI,
(ii) S ~ S + Sand S ~ S * S are replaced by S ~ SAS, S ~ SBS,
A ~ +, B ~ *
V~· = {S, A, B}