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

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.

• Is the condition $n \le m^2$ or $n \ge m^2$? May 14 at 16:54
• @YuvalFilmus I think it is indeed $n\leq m^2$, since it is coherent with the first two cases: removing $b$'s prove the word is not in $L$, and it is the same when adding $a$'s. May 14 at 17:58
• @YuvalFilmus it's n≤m2. question edited. May 15 at 7:31

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$$.
• They don't matter. What matters is that after pumping, you're not of the form $a^*b^*$. May 18 at 6:46
• What word do you start with? And what does $uv^2wx^2y$ look like? May 18 at 6:49