Exam paper 2006, pumping lemma, my answer

Herewith that second post I mentioned.

my thoughts herewith on the question 3 for pumping lemmas in 2006 exam paper.

They ask to prove that aⁿ b aⁿ⁺³ b^n-1 is NON CONTEXT Free

So we put down the whole assumption of L is context free and thus has a CFG in CNF with p live productions and a word w with length(w) > 2^p
thus we can apply the pumping lemma and thus the word w can be devided into uvxyz (5 parts) such that uvⁿx^yz is also in L

such that

length(x) > 0
Length(v) + length(y) > 0
Length(vxy) <= 2^p

i choose

i choose n to be 2^p, thus each exponent n will be such (sorry dunno how to format exponent on exponent in this editor)

NOw we take this options where vxy might be.

1. It might be in a single clump of a or b
if so and if then pumped to vvxyy or more, a will be increased at one clump, but not in the others. This would result in the relationship between the first a and the second a to become null and void.
in other words before pumping we had a value of n / n+3 (or rather 2^p / 2^p + 3
after pumping this value will no longer be the same, because the first 2^p would become (2^p)ⁿ where n is the number of times pumped.
Same wouldf apply to any of the other clumps.

2. THe other option is the vxy falls over part of a's and part of b's (straddles as the book says). If so, taking the first two sets of a's and b's, when pumped it would increase either the a's or the b's or both. Again messing up the value relantioship between these a's and b's and the others.

hence all cases are contradictory to assumption.

Does this make sense.?

it seems easier with aⁿbⁿdⁿcⁿ

Danie van Eeden
------------------------

Good luck DVE...Hope we kickass with this one as well...Good luck to everyone else

good luck to you too!

Danie van Eeden
------------------------