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)?
-
$\begingroup$ This might help $\endgroup$– MJDCommented Jul 29, 2012 at 23:55
-
$\begingroup$ Yes, you have to consider all (valid) splittings, as can be seen by the Pumping lemma formulation. This might help, too. $\endgroup$– RaphaelCommented Jul 30, 2012 at 8:41
1 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$.