# CFG pumping lemma

I can't figure out how to prove this is a non CFG.

$\{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}$, Where the number of a's in x = number of a's in y and number of b's in x = to the number of b's in y.

I've been able to come up with a few cases where setting

$s = a^pb^pa^pb^p$

doesn't work.

-
That's clearly not a context free grammar, because it's not a grammar at all. You mean you want to prove it's not a context free language. – Chris Eagle Nov 1 '11 at 10:43
@ChrisEagle yea, meant CFL. Was looking at grammars before, so i was thinking grammars. – Matt Nov 1 '11 at 19:59

Let $L=\{xy\in\{a,b\}^*:n_a(x)=n_a(y)\land n_b(x)=n_b(y)\}$, suppose that $L$ is context-free, and let $p$ be the critical number in the pumping lemma. Let $w_1=a^pb^p$, $w_2=(ab)^p$, and $w=w_1w_2=a^pb^p(ab)^p$. Suppose that $w=uvxyz$, where $|vxy|\le p$, $|vy|\ge 1$, and $uv^nxy^nz\in L$ for every $n\ge 0$. (Note that $uxz$ must belong to $L$: people often forget about the $n=0$ case, and it turns out to be very handy here.)
Suppose first that $vxy$ is a substring of $w_1$. It can’t be of the form $a^k$: after sufficient pumping, all of the $b$’s would be in the second half of the word. If it’s of the form $b^k$, then $uxz$, the $n=0$ case, will be of the form $a^pb^{p-2i}(ab)^p$ for some positive integer $i$. If $i$ is even, say $i=2j$, the first and second halves are $a^pb^{p-4j}(ab)^j$ and $(ab)^{p-j}$, with different numbers of $a$’s. If $i=2j-1$, the two halves are $a^pb^{p-4j+2}(ab)^ja$ and $b(ab)^{p-j+1}$, again with different numbers of $a$’s. Finally, suppose that $vxy$ is of the form $a^kb^j$, where $|v|,|y|\ge 1$. If $v=a^i$ and $y=b^j$, then the $n=2$ case of the pumping lemma will be $a^{p+i}b^{p+j}(ab)^p$; $i<p$, so the initial $a^{p+i}$ is in the first half of the word, while the second half has only $p$ $a$’s. The only remaining possibility is that one of $v$ and $y$ is of the form $a^ib^j$ for non-zero $i,j$, but this runs into the same problem as the previous case.
Now suppose that $vxy$ is a substring of $w_2$. It must be of even length (why?), so either it’s of the form $(ab)^i$ for some $i>0$, or it’s of the form $a(ba)^ib$ for some $i\ge 0$. In either event the $n=0$ case of the pumping lemma is $a^pb^p(ab)^{p-i}$, which has $p$ $a$’s in its first half and only $p-i$ in its second.
The only remaining possibility is that $vxy$ lies partly in $w_1$ and partly in $w_2$, and each of the subcases here is similar to one already handled.