Welcome! Log In Create A New Profile

2006 Q3

Posted by Rey

Announcements		Last Post
	SoC Curricula	09/30/2017 01:08PM
	Demarcation or scoping of examinations and assessment	02/13/2017 07:59AM
	School of Computing Short Learning Programmes	11/24/2014 08:37AM
	Unisa contact information	07/28/2011 01:28PM

Forums Messages New

Rey

2006 Q3
October 29, 2010 07:36PM

Registered: 18 years ago
Posts: 163
Rating: 0

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ⁿxyⁿz when pumped is still in the language. Lets take the word

a^{2^p}ba^{2^p+3}b^{2^p-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^{2^p} then it will be longer than the next a^{2^p+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^{2^p} and b would be longer than the group a^{2^p+3}, and b^{2^p-1}, which isn't in the language

So by contradiction of pumping lemma with length the language L is not context free.