2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for the help! Is it enough to simply explain all 4 cases as when there are both 0's and 1's in $vxy$, then when it is pumped up, the 0's and 1's will be out of the correct order? $\endgroup$ – tpm900 Mar 4 '17 at 14:25
  • $\begingroup$ Yes, that the idea. $\endgroup$ – Maczinga Mar 4 '17 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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