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)?
Pumping lemma - do I have to show every way to split string to have a complete answer?
0
$\begingroup$
computer-science
regular-language
context-free-grammar
-
0Yes, you have to consider all (valid) splittings, as can be seen by the Pumping lemma formulation. [This might help, too](http://cs.stackexchange.com/a/276/98). – 2012-07-30
1 Answers
0
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$.