Chapter 6: Context-Free Languages g 195
Step 2 We have to apply Theorem 6.4 to G j • Thus,
WI = IS}
As we have production S -+ CA and S E Wj, W 2 = IS} u {A, C}
As A -+ a and C -+ b are productions with A, C E W 2 , W 3 ={S, A, C, a, b}
As W 3 = V: v U L, p" = {S -+ a I Al E W 3 } = p'
Therefore,
G' = ({S, A, C}, {a, b}, {S -+ CA. A -+ a, C -+ b}, S)
is the reduced grammar.
EXAMPLE 6.8
Construct a reduced grammar equivalent to the grammar
S -+ aAa,
A -+ Sb IbCC IDaA.
C -+ abb IDD,
E -+ ac'
D -+ aDA
Solution
Step 1 W j = {C} as C -+ abb is the only production with a terminal string
on the R.H.S.
W 2 = {C} u {E. A}
as E -+ aC and A -+ bCC are productions with R.H.S. in (L U {C})*
W 3 = {C, E. A} U IS}
as S -+ aAa and aAa is in (L U W 2 ) *
w.+ = W 3 U 0
Hence,
Vv= W, = IS, A, C, E}
p' = {AI -+ al a E (VN U L)*}
= {S -+ aAa, A -+ Sb I bCC, C -+ abb, E -+ aC}
G j = (V
/
V ' {a, b}, p', S)
Step 2 We have to apply Theorem 6.4 to G i . We start with
Wi = IS}
As we have S -+ aAa,
W 2 = IS} U {A, a}
As A -+ Sb IbCC,
W, = IS, A, a} U IS, b, C} = IS, A, C, a, b}
As we have C -+ abb,