Question 4 (2007)

So to show that the language L

_{1} and L

_{2} are closed under union we do the following

Take all nonterminals in the CFG for L

_{1} and add a

_{1}
Take all nonterminals in the CFG for L

_{2} and add a

_{2}
Now create a new start state S -> S

_{1} | S

_{2} and combine the language so that you get the following

0. S -> S

_{1} | S

_{2}
1. S

_{1} -> X

_{1}Y

_{1} | aS

_{1}
2. X

_{1} -> Y

_{1}X

_{1}a | a

3. Y

_{1} -> b | Y

_{1}Y

_{1}
4. S

_{2} -> S

_{2}X

_{2} | Y

_{2}
5. X

_{2} -> a | aY

_{2} | /\

6. Y

_{2} -> bS

_{2} | bY

_{2} | 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 S

_{1} or S

_{2}
So to generate a word we start in S (0) from here we either go to S

_{1} (1) or S

_{2} (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 S

_{1} or S

_{2} and none other.

2) All words generated by S

_{1} or S

_{2} can be generated by this new CFG

To generate a word from L

_{1} or L

_{2}, you would enter it's start state and proceed as normal. Since L

_{1} and L

_{2} 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 S

_{1} or S

_{2} can be generated by the new CFG.

Waffle Waffle Waffle.