Question 3 (2007)
Aaarghh my favorite again, pumping lemmings with length
So lets assume that the L is context free, then by Pumping lemma with length there is some word of sufficient length such that it can be split into five parts uvxyz and can be pumped.
a
2p-1b
2p+2a
2p
should be long enough for us to pump. So by rule one length(vxy) <=2
p we can have the following two cases
1) vxy consists of only a's or b's
If we pump the first set a
2p-1 it will be longer than the following b's
If we pump the second set b
2p+2 it will become longer than the first set of a's and following set of b's
If we pump the third set a
2p then it will become longer than the first set of a's and second set of b's
None of these words are in the Language
2) vxy consists of a's and b's or b's and a's
If we pump the first set of a's and b's it will grow longer than the remaining a's
If we pump the send set of b's and third set of a's they will become longer than the first set of a's
None of these words are in the Language
Therefore proof by contradiction the language L is NOT context free.
