Why is the following language not context-free?

Question

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.

Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.

Hence both $v$ and $y$ must consist only of one kind of symbol each. Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.

Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?

*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.

Answer 1

Examining this answer mentioned by Raphael,

I don't believe the pumping lemma could help you with this language. It seems you can always choose the part to pump so that you will "miss" the condition that $m=n^2$.

I also believe the same difficulty will be there if you try to use Ogden's Lemma, which generalize the pumping lemma to deal with such problematic questions, (marking $N$ places will reduce to pumping the marked substring.)

However, the method using Parikh's Theorem, should work and is not very difficult for this case, since $\Psi(L) = \{ (n,m) \mid m\ne n^2\}$. You are left to show that it is not a finite union of "linear" sets. Not too easy, but should be doable.

Answer 2

Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^*b^*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^* b^*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \{a^n b^m \mid m = n^2\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.