Question 3 (2006)
I really don't like pumping lemma. REALLY. So help and criticism on this answer appreciated. Would it be worth the marks, did I leave something out? Nit pick people, nit pick!
Assuming that L is context free, then by pumping lemma with length, all words of sufficient length (length(w) > 2
p) may be split into 5 parts such that uv
nxy
nz when pumped is still in the language. Lets take the word
a
2pba
2p+3b
2p-1
Where p is the number of live productions if the language was in CNF. Which should be long enough.
Now lets break the word down so that each vxy
1) Could be all a's or all b's, but if you pump the first a
2p then it will be longer than the next a
2p+3 and the same for the third set of b's and visa versa, which isn't in the language.
2) Could be a's and b's or b's and a's. Again pumping the first set of a
2p and b would be longer than the group a
2p+3, and b
2p-1, which isn't in the language
So by contradiction of pumping lemma with length the language L is not context free.