So to show that the language L1 and L2 are closed under union we do the following
Take all nonterminals in the CFG for L1 and add a 1
Take all nonterminals in the CFG for L2 and add a 2
Now create a new start state S -> S1 | S2 and combine the language so that you get the following
0. S -> S1 | S2
1. S1 -> X1Y1 | aS1
2. X1 -> Y1X1a | a
3. Y1 -> b | Y1Y1
4. S2 -> S2X2 | Y2
5. X2 -> a | aY2 | /\
6. Y2 -> bS2 | bY2 | b
We have obviously not duplicated any nonterminals therefore these languages should still produce the same language as before.
Proof both ways:
1) All words generated by this new CFG can be generated by either S1 or S2
So to generate a word we start in S (0) from here we either go to S1 (1) or S2 (4). On entering either of these states you will be unable to return to S and will only complete the CFG 1 -3 or 4 -6. Since both of these CFG's represent their original CFG's in their entirety, and are unable to enter any state other than those, you will only be able to generate the words in one or the other. Therefore this new CFG generates the words from either S1 or S2 and none other.
2) All words generated by S1 or S2 can be generated by this new CFG
To generate a word from L1 or L2, you would enter it's start state and proceed as normal. Since L1 and L2 are now represented by the states with either 1 or 2 and you are only able to enter one or the other, all word generated by either S1 or S2 can be generated by the new CFG.
> Once again agreed.
> The proof part of the question is a vague to me as
> there aren't really any stepwise proofs for this
> in the text. As you said, waffle waffle waffle for
> a couple of point.
I get the impression that we are the ones being pumped, but after you get it, it's kind of simple, but still REALLY tedious! I hope we don't get PROVE by pumping lemma with length that this language is context free!