Pumping Lemma proof

Question

We have a language $$ L = \{\text{w element of } \{a,b\}^* \mid \#(a,w) = \#(b,w)^2 \} $$ where $ \#(a,w) $ means the number of letters $a$ in $w$

I would like to show that this language is not context-free.

Assume that L is context-free. Let p be the constant from Pumping Lemma.

$$ w = a^{p^2}b^p $$

Let uvxyz be the decomposition of w as in the lemma. Since $ \mid vxy \mid \le p $ we have to consider three cases:

1. $v$ and $y$ contain only letters from block of $a$'s
   In this case $s'=uv^2xy^2z$ should be the part of language L. But number of letters b in $s'$ is p and number of letters a is more then $p^2$. Contradiction $s' \notin L$.
2. Similar explenation when $v$ and $y$ contain only leters from block of $b$'s
3. $vxy$ contains letters $a$ and $b$
   
   But how to show contradiction in this case?

Answer 1

In the 3rd case there exist constants $c_1, c_2>0$, such that

$$\#(a,uv^nxy^nz)\le c_1 n$$

but

$$\#(b,uv^nxy^nz)\ge c_2 n.$$

Then you have $c_1 n \ge (c_2 n)^2.$

Answer 2

The third case breaks down into several sub-cases, but the only difficult sub-case is the one in which $v=a^k$ and $y=b^\ell$ for some $k,\ell>0$ with $k+\ell\le p$. Then

$$uv^nxy^nz=a^{p^2+(n-1)k}b^{p+(n-1)\ell}\;.$$

For convenience let $m=n-1$, and suppose that $(p+m\ell)^2=p^2+mk$; then $$2pm\ell+m^2\ell^2=mk\;,$$ and hence either $m=0$, or $2p\ell+m\ell^2=k$, and hence

$$m=\frac{k-2p\ell}{\ell^2}\;.$$

Thus, apart from $n=1$ (i.e., $m=0$) there is at most one non-negative integer $n$ such that $uv^nxy^nz\in L$.