Pumping lemma - do I have to show every way to split string to have a complete answer?

541 Views Asked by At

In the pumping lemma, we have to split strings into $uvwxy$ (for example). Say the language was $a^n$$b^n$$a^n$$b^n$. We could it this way: $a^r$$a^s$$a^t$$a^u$$b^n$$a^n$$b^n$, with $uvwx$ all contained in the first $a^n$. We can pump the string, and we'll see the string doesn't belong in the language. This is all good, but do I then have to show other ways to split the string? Or is just showing one example enough to be a complete answer (and enough to declare the language as not context free)?

1

There are 1 best solutions below

0
On BEST ANSWER

Say the language was $\{a^n b^n\}$. If your example was good enough to be a complete answer, the same argument would also suggest that $\{a^n b^n\}$ isn't context-free, even though it certainly is.

Since you cannot prove a false statement with a valid proof, this proof is incomplete. Check the conditions of the particular pumping lemma you're using to see what assumptions you made about $u,v,w,x,y$ that are unwarranted. Quite possibly it is your claim that $uvwx$ fits entirely into $a^n$, even though the pumping lemma makes no promise that $|uvwx| \le n$.