I want to show that the following language is not context-free:
$$\{a^nb^m\mid0\leq n\leq m^2\}$$
I tried the word $w=a^kb^k$, but it does not work, because I can't show that for every possible partition $w=uvxyz$ (with the conditions of the context-free-pumping-lemma), an $i$ exists that the number of $a$'s are more than $k^2$. The problem is, that the number of $b$'s is growing as well.
Every word I tried seems to have this problem. Do you know a word, which might work?
Thanks in advance.
If $p$ is the pumping length, start with $w=a^{p^2}b^p$. Suppose that $w=uvxyz$ is such that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for each $k\ge 0$. Clearly we cannot have $vxy=a^r$ for some $r$, since we can then pump up to get too many $a$s. We also cannot have $vxy=b^r$ for some $r$, since in that case pumping down (i.e., setting $k=0$) takes us out of $L$. It’s also clear that neither $v$ nor $y$ can contain both letters, so we must have $v=a^r$ and $y=b^s$ for some $r,s>0$. If $r>s$, pumping up will take us out of $L$, so $r\le s$. But then pumping down will take us out of $L$, since
$$p^2-r\ge p^2-s>(p-s)^2\;.$$
You’ll have to do a little work to prove the last inequality, but it’s not too hard to show.
