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

Question

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

Answer 1

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|. $$