I need a proof that the language L = {$a^nb^ma^nb^m,\:n,m\geq0$} is context free using the pumping lemma. My problem is that I can actually show the conditions of the lemma hold for this language and thus it wouldn't help in disproving the context freeness of this language. In order to do that, I can take $s=uvxyz$ to be $u=a^nb^{m-1}$, $v=b$, $x=a^n$, $y=b$, and $z=b^{m-1}$ and let the constant $p$ (or $m$ in some references) be $p=n+2$; then no matter how I pump $v$ and $y$ up or down, still the number of $b$s would be the same on both sides and with the same order and the resulting string would still be in L. What am I doing wrong here?
Proof that the language $a^nb^ma^nb^m$ is not context free using the pumping lemma.
context-free-grammarpumping-lemma
Best Answer
Suppose $L$ is a CFL with pumping length $p \geq 1$.
Then consider the string $s = a^pb^pa^pb^p$. Clearly $|s| \geq p$. Let $s'$ be the pumped string. For $s' \in L$, either $v = x = b \lor v = x = a$ where $v$ and $x$ are taken from different occurrences of $b$ and $a$ respectively. But in this case $|vwx| \geq p+2$. Qed.