0
$\begingroup$

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)?

$\endgroup$
2
  • $\begingroup$ This might help $\endgroup$
    – MJD
    Commented 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$
    – Raphael
    Commented Jul 30, 2012 at 8:41

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .