Suppose, for instance, that ω ε L 1 . Then
is a possible derivation in grammar G 3 . A similar argument can be made for ω ε
L 2 . Also, if ω ε L (G 3 ), then either
or
must be the first step of the derivation. Suppose (8.9) is used. Since sentential
forms derived from S 1 have variables in V 1 , and V 1 and V 2 are disjoint, the
derivation
can involve productions in P 1 only. Hence ω must be in L1. Alternatively, if
(8.10) is used first, then ω must be in L 2 and it follows that L (G 3 ) is the union of
L 1 and L 2 .
Next, consider
Here again S 4 is a new variable and
Then
follows easily.
Finally, consider L (G 5 ) with