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

Question

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?

Answer 1

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