Solutions (or Hints) to Chapter-end Exercises l;\ 397
6.8 Consider G = ({S, A, B}, {a, b}, P, S), where P consists of
S ~ AB Iab and B ~ b.
Step.1 When we apply Theorem 6.4, we get
WI = {S}, W 2 = {S} u {A, B, a, b} = W 3
Hence G j = G.
Step 2 When we apply Theorem 6.3, we obtain
Wj = {S, B}, W 2 = {S, B} u 0 = W 3
So, G 2 = ({S, B}, {a, b}, {S ~ ab, B ~ b}, S).
Obviously, G 2 is not a reduced grammar since B ~ b does not appear
in the course of derivation of any terminal string.
6.9 Step 1 Applying Theorem 6.3, we have
W j = {B}, W 2 = {B} u {C, A}, W 3 = {A, B, C} u {S} = V N
Hence G j = G.
Step 2 Applying Theorem 6.4, we obtain
W j = {S}, W 2 = {S} u {A, a}, W 3 = {S, A, a} u {B, b}
w. = {S, A, B, a, b} u 0
Hence, G 2 =({S, A, B}, {a, b}, P, S), where P consists of S ~ aAa,
A ~ bBB and B ~ abo
6.10 The given grammar has no null productions. So we have to eliminate
unit productions. This has already been done in Example 6.10. The
resulting equivalent grammar is G =({S, A, B, C, D, E}, {a, b}, P,
S), where P consists of S ~ AB, A ~ a, B ~ b I a, C ~ a, D ~ a
and E ~ a. Apply step 1 of Theorem 6.5. As every variable derives
some terminal string, the resulting grammar is G itself.
Now apply step 2 of Theorem 6.5. Then
W j = {S}, W 2 = {S} u {A, B} = {S, A, B}, W 3 = {S, A, B} u
{a, b} = {So A, B, a, b} and W 4 = W 3 .
Hence the reduced grammar is G' = ({S, A, B}, {a, b}, P~ S), where
P' = {5 ~ AB, A ~ a, B ~ b, B ~ a}.
6.11 We prove that by eliminating redundant symbols (using Theorem 6.3
and Theorem 6.4) and then Unit productions, we may not get an
equivalent grammar in the most simplified form. Consider the
grammar G whose productions are 5 ~ AB, A ~ a, B ~ C, B ~ b,
C ~ D, D ~ E and E ~ a.
Step 1 Using Theorem 6.3, we get
Wj = {A, B, E}, W 2 = {A, B, E} u {S, D},
W 3 = {5, A, B, D, E} u {C} = V v .
Hence Gj = G.
Step 2 Using Theorem 6.4, we obtain
W j = {5}, W 2 = {S} u {A, B}, W 3 = {S, A, B} u {a, c, b},
w. = {S, A, B, C. a, b} u {D},
W s = {S, A, B. C, D, a, b} u {E} = V N u L.
Hence G 2 = G 1 = G.