# How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $$a^{n^2}b^n$$. If you divide it into $$uvwxy$$ and have only $$a$$'s in $$v$$ and $$x$$, you clearly get out of language when you pump up. If you do the same with $$b$$'s and pump down, you get out of language as well. But how dow do you show situation where there are only $$a$$'s in $$v$$ and just $$b$$'s in $$x$$?

Thank you

• Pump down. For large enough $n$ (in terms of the pumping length), you well reach a contradiction. May 23, 2020 at 7:49

Suppose towards a contradiction that $$L$$ is context-free and let $$c$$ be the pumping length of $$L$$. Consider the word $$a^{c^2} b^c$$ which, by the pumping lemma, can be written as $$uvwxy$$ with $$1 \le |vx| \le c$$.

Notice that:

• $$vx$$ cannot contain only $$b$$s, since otherwise $$uwy \not\in L$$.
• $$vx$$ cannot contain only $$a$$s, since otherwise $$uv^2wx^2y \not\in L$$.
• none of $$v$$ and $$x$$ contains both $$a$$s and $$b$$s, since otherwise $$uv^2wx^2y \not\in L$$.

We conclude that $$v$$ contains only $$a$$s, $$x$$ contains only $$b$$s, and $$x$$ contains at least one $$b$$. Then, by the pumping lemma, $$a^{c^2-|v|} b^{c-|x|} = uwy \in L$$. This is a contradiction since: $$(c - |x|)^2 \le (c - 1)^2 = c^2 - 2c + 1 \le i^2 - c < i^2 - |v|.$$

• Thank you very much! This is exactly what I was looking for :-). Could not get the last part properly together. Thank you once again and have a nice day!
– Mike
May 24, 2020 at 6:32