# Using the Pumping Lemma to show that $\{a^nb^{n^2} : n\in \mathbb{N} \}$ is not a context-free language

Consider the language $L= \left\{a^nb^{n^2} : n\in \mathbb{N}\right\}$.

I want to prove that this language is not context-free by using the Pumping-Lemma for context-free languages.

So, I picked the word $w=a^pb^{p^2}$ where $p$ is the proposed pumping constant and I got a little stuck. If we assume that $w=uvxyz$ for some $u,v,x,y,z\in Σ^*$ as in the Pumping Lemma, then I have some cases.

1. $vxy$ contains only $a$s. So of course for every $r \neq 1$ the word $uv^rxy^rz \notin L$.
2. $vxy$ contains only $b$s. Analogous to the above.
3. The case where $vxy$ contains some $a$s and some $b$s. Can someone show me how to solve this case?

If $v$ contains any $\tt b$ or $y$ contains any $\tt a$, then $uvvxyyz$ will contain letters out of order and certainly won't be in $L$, then.
So it must be that $v=\mathtt a^s$ and $y=\mathtt b^t$ for some $s$ and $t$.
However, then $uvvxyyz={\tt a}^{p+s}{\tt b}^{p^2+t}$ and $uvvvyzzzx={\tt a}^{p+2s}{\tt b}^{p^2+2t}$, and if both of these are in $L$ we must have $$(p+s)^2 = p^2+t \\ (p+2s)^2 = p^2+2t$$ These equations together imply $s=0$ (solve the first for $t$, plug into the second, and simplify), which contradicts the fact that $v$ is nonempty.
• Note also that is $s = 0$ or $t = 0$, pumping will break the balance between $a$s and $b$s, so both are non-zero. Feb 11, 2020 at 18:15