194 g Theory of Computer Science
Definition 6.8 Let G = (V N , L, P, S) be a CFG. G is said to be reduced or
non-redundant if every symbol in V N U L appears in the course of the
delivation of some terminal string, i.e. for every X in v'v U L, there exists
a delivation S ::S aX[3 ::S W E L(G). (We can say X is useful in the
derivation of terminal strings.)
Theorem 6.5 For every CFG G there exists a reduced grammar G' which is
equivalent to G.
Proof We construct the reduced grammar in two steps.
Step 1 We construct a grammar G j equivalent to the given grammar G so
that every variable in G j derives some terminal string (Theorem 6.3).
Step 2 We construct a grammar G' = (V~v, L', p', S) equivalent to Gj so that
every symbol in G' appears in some sentential form of G' which is equivalent
to G j and hence to G. G' is the required reduced grammar.
By step 2 every symbol X in G' appears in some sentential form, say
exX[3. By step 1 every symbol in exX[3 derives some terminal string. Therefore,
S ::S exX[3 ::S >t' for some w in L*, i.e. G' is reduced.
Note: To get a reduced grammar, we must first apply Theorem 6.3 and then
Theorem 6.4. For, if we apply Theorem 6.4 first and then Theorem 6.3, we may
not get a reduced grallli'1lar (refer to Exercise 6.8 at the end of the chapter).
EXAMPLE 6.7
Find a reduced grammar equivalent to the grammar G whose productions are
C ~ aBlb
A ~ a.
B ~ BClAB,
S ~ ABICA,
Solution
Step 1 WI = {A, C} as A ~ a and C ~ b are productions with a terminal
string on R.H.S.
W~ = {A. C} U {AIIA I ~ ex with ex E (L U {A, C})*}
= {k C} U {S} as we have S ~ CA
W 3 = {A, C, S} U {AI IAl ~ ex with ex E (L U {S, A, C})*}
= {A~ C~ S} u 0
v~v= W~ = {S, A, C}
p' = {A j ~ ex IAj, ex E (V~", U L)*}
= {S ~ CA. A ~. a, C ~ b}
Thus.
G] = ({S, A. C}. {a, b}, {S ~ CA, A ~ a, C ~ b}, S)