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.
- $vxy$ contains only $a$s. So of course for every $r \neq 1$ the word $uv^rxy^rz \notin L$.
- $vxy$ contains only $b$s. Analogous to the above.
- 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.