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

context-free-grammarformal-languages

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?

Best Answer

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.

Related Question