Reduction of the Number of Derivations
Theorem: Let G = (N, T, P, S) be a CFG.
The next three languages coincide
(1) {w: w Î T*, S Þlm* w}
(2) {w: w Î T*, S Þrm* w}
(3) {w: w Î T*, S Þ* w} = L(G)
 Gist:
Without any loss of generality, we can consider only leftmost or rightmost derivations.
17/50