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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.