0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Addem
    Nov 16, 2023 at 20:09
  • $\begingroup$ @Addem I edited my answer. $\endgroup$
    – Nathaniel
    Nov 16, 2023 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.