# Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $$L=\{0^m1^n:0\le m\le n^2\}$$ is not a CFL. Here is what I have so far.

Suppose for contradiction that it is a CFL and let $$N$$ be the pumping length. Set

$$s = 0^{N^2} 1^N$$

Let $$u,v,x,y,z$$ be a decomposition $$s = uvxyz$$ such that $$uv^ixy^iz\in L$$ for every $$i\in \Bbb N$$, and $$|vxy|\le N$$ and $$|vy|>0$$. If $$vxy$$ is entirely in the 0 block, we can pump it up and violate the conditions of the pumping lemma; likewise if $$vxy$$ is in the 1 block.

What I'm having trouble with is producing a contradiction if $$vxy$$ crosses from the 0 to 1 block. I can show, in this case, that $$v$$ must consist only of 0's and we can assume the number is strictly greater than 0. Likewise $$y$$ consists only of 1's and is not empty. Of course also $$2\le |vy|\le N$$.

But from here I'm stuck. I produced this formula for the total number of 0's in $$uv^ixy^iz$$:

$$N^2 + (i-1)r$$

where $$v=0^r$$. The number of 1's is

$$N + (i-1)s$$

where $$y=1^s$$. Since the pumping lemma implies that this is in $$L$$ then we must have

$$N^2 + (i-1)r \le (N+(i-1)s)^2$$

But I wasn't able to obtain any contradiction from this. Certainly if $$i$$ goes to infinity then this inequality is guaranteed to be true.

Because this seems like a dead-end, and I can't see why picking a different $$s$$ would be any better, I'm thinking perhaps I need to significantly change strategy. I thought about proving that the complement language is not a CFL but since CFLs are not closed under complementation, that shouldn't work right?

In the last case, you should consider $$uxz$$. It is useful to note that $$(N-1)^2 < N^2 - N$$ if $$N > 1$$.
Indeed, if we suppose $$v= 0^r$$ and $$y = 1^s$$, with $$r > 0$$ and $$s>0$$, we also have $$r < N$$ (because $$|vxy| \leqslant N$$).
Then, $$uxz = 0^{N^2 - r}1^{N-s} = 0^m1^n$$. But: $$m = N^2 - r > N^2 - N > N^2-2N+1 = (N-1)^2 \geqslant (N-s)^2 = n^2$$ So $$uxz\notin L$$.
• I probably should have shown how I worked with this, but I tried that, and get $N^2-r \le (N-s)^2$. Ok, so $-r \le -2Ns + s^2$ so $0\le s^2-2Ns+r$ and we can complete the square (just a guess about a good thing to do) and get $0\le (s-N)^2-N^2+r$. But I don't see anything that comes from this. Nov 16 at 20:09