Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma

Question

I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof. The language is

$$L = \{ a^n b^m \mid n \leq m^2 \}$$

Assume Demon picks $p$ and I choose $s = a^{p^2}b^p$ and $s = uvwxy$ such that $p \geq |vwx|$.

The first case is $vwx = b^j$. If we choose $i = 0$ everything is ok and the relationship isn't right.

The second case is $vwx = a^j$. If we choose $i = 2$ every thing is ok.

I get stuck when $vwx = a^j b^k$. How can I finish the proof in this case?

Did I choose the right string? I repeated them for $s = a^{p}b^p$ but it didn't work.

Answer 1

When $vwx = a^j b^k$, there are two possibilities:

• $v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^*b^*$, and in particular $uv^2wx^2y \notin L$.
• $v = a^s$ and $x = b^t$, where $s,t>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \leq (p-1)^2$, which translates to $s \geq 2p-1$, which is impossible, since $s \leq p-1$.