2007 Q4

Question 4 (2007)

So to show that the language L₁ and L₂ are closed under union we do the following

Take all nonterminals in the CFG for L₁ and add a ₁
Take all nonterminals in the CFG for L₂ and add a ₂
Now create a new start state S -> S₁ | S₂ and combine the language so that you get the following

0. S -> S₁ | S₂
1. S₁ -> X₁Y₁ | aS₁
2. X₁ -> Y₁X₁a | a
3. Y₁ -> b | Y₁Y₁
4. S₂ -> S₂X₂ | Y₂
5. X₂ -> a | aY₂ | /\
6. Y₂ -> bS₂ | bY₂ | 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₁ or S₂
So to generate a word we start in S (0) from here we either go to S₁ (1) or S₂ (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₁ or S₂ and none other.

2) All words generated by S₁ or S₂ can be generated by this new CFG
To generate a word from L₁ or L₂, you would enter it's start state and proceed as normal. Since L₁ and L₂ are now represented by the states with either ₁ or ₂ and you are only able to enter one or the other, all word generated by either S₁ or S₂ can be generated by the new CFG.


Waffle Waffle Waffle.

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.

louisrdev Wrote:
-------------------------------------------------------
> 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.


Check the work of Bronwen. She have done a great job:
http://wikistudent.ws/Unisa/COS301Y

see the 'Study notes' at the end, they are a great resource of help

---------
I'm Year '0110' Computer Student!

visnaicker Wrote:
-------------------------------------------------------
> On my second attempt!
>
> I hope in the rest of my life I never have to pump
> another lemma!

HAHA couldn't agree more!

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!