Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

Question

I am trying to prove that the language $L=${$0^n 1^m |m ≤n^2$} is not a context free language. To do so I selected a string $w=0^p 1^{p^2}$. However, I am new to the CFL pumping lemma, and I am not sure if my proof is correct. Specifically, does the value of $i$ need to be the same for all divisions?

My first division is: v and y both contain 0’s.

$u=0^h$

$v=0^j$

$x=0^k$

$y=0^q$

$z=0^{-h-j-k-q} 1^{p^2}$

When $i=0$, I get $uv^0 xy^0 z=0^h 0^0j 0^k 0^0q 0^{p-h-j-k-q} 1^{p^2}=0^{p-j-q} 1^{p^2}$. This means $w$ contains less than p 0’s, but p2 1’s. This means for any valid value of p, there are more than p2 0’s. So this is not in the language.

The second division is either v or y contain both 0’s and 1’s. When $i=2$ I have $v=0^j 1^k$ or $y=0^j 1^k$, when $i=2$, so 0’s and 1’s out of order as the sequence $0^j 1^k$ will be repeated.

Finally the case that both v and y contain 1’s.

$u=0^p$

$v=1^j$

$x=1^k$

$y=1^q$

$z=1^{p^2-j-k-q}$

When $i=3$, the string becomes $uv^3 xy^3 z=0^p 1^3j 1^k 1^3q 1^{p^2-j-k-q}=0^p 1^{p^2+2j+2q}$. This means s contains more than $p^2$ 1’s, but only p 0’s, so the string is not in the language.

Answer 1

What you have done up to now is correct. The idea is that you should prove that the 'pumping' fails for all possible partitions of $w$. You have considered just two families of partitions, namely, the one for which $vxy\in0^+$ and the one for which $vxy\in1^+$.

You are missing the cases in which the sliding window (ie. $vxy$) crosses the boundary between $0$ and $1$.

Hence, next step is to consider the following cases (here $|w|$ is the length of $w$):

1) $vxy=0^{|vx|}0^h1^k$ where $h,k\geq 1$ and $h+k+|vx|\leq p$

2) $vxy=0^{|vx|}1^{|y|}$ where $|y|>0$ and $|vxy|\leq p$

3) $vxy=0^{|v|}0^h1^k1^{|y|}$ where $h+k=|x|>0$ and $|vxy|\leq p$

4) $vxy=0^{|v|}1^{|xy|}$ where $|v|>0$, $|xy|>0$ and $|vxy|\leq p$

All of the above cases can be easily solved with the technique you used with the former ones.