Chapter 6: Context-Free Languages l;;! 189
s
a
s
s
a
s
s
a
s
a
Fig. 6,11 Two derivation trees of abababa for Example 6.4.
6.3 SIMPLIFICATION OF CONTEXT-FREE GRAMMARS
In a CFG G, it may not be necessary to use all the symbols in VIy' u L, or
all the productions in P for deriving sentences. So when we study a contextfree language L(G), we try to eliminate those symbols and productions in G
which are not useful for the derivation of sentences.
Consider, for example,
G = ({S. A, B, C, E}, {n, b, c}, P, S)
where
P = {S ~ AB, A ~ n, B ~ b, B ~ C, E ~ ciA}
It is easy to see that L(G) = {nb}. Let G' = ({S, A. B}, {n, b}, p', S), where
P' consists of S ~ AB, A ~ n, B ~ b. UG) = L(G'). We have eliminated
the symbols C, E and c and the productions B ~ C, E ~ c IA. We note the