1
$\begingroup$

To prove that $L=\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|\leq p, |w|\geq p, |yv|>0, xy^iuv^iz \in L \forall i>0$

Take $i=0$ then consider 3 cases:

Case 1:$yuv$ is only a substring of $0s$.

Then $w'=0^a1^{7p} \text{ with } 21p>a\geq 20p$. In this case, $a$ is not divided by $7p$

Case 2:$yuv$ is only a substring of $1s$.

Then $w'=0^{21p}1^{b} \text{ with } 7p>b\geq 6p$. In this case, $21p$ is not divided by $b$

Case 3:$yuv$ contains both $0s$ and $1s$.

Now I am quite sure this also works when $yuv$ includes both $1s$ and $0s$. We get $w'=0^{21p-a}1^{7p-b} \text{ with }p>a>0, p>b>0 \text{ and } p\geq a+b$.

I just can't figure out how to formally state how a contradiction arises from case 3. How can I prove that case 3 also fails? Thanks!

$\endgroup$
1
$\begingroup$

You can try to take a different value for $i$ in that case. It is not necessary to fix one $i$, but the $i$ chosen may depend on the chosen partition $xyuvz$. Will $7p+ib$ always divide $21p+ia$?

$\endgroup$
3
  • $\begingroup$ So assuming 7p+ib divides 21p+ia, i should show that 7p+nib does not divides 21p+nia for some n>1 I assume. How can I formalize this? $\endgroup$ – user1354784 Oct 28 '16 at 2:32
  • $\begingroup$ Actually if $7p+ib$ divides for a given $i$, then $7p+ib$ divides $21p+ia$ for all $i$ so I guess the pumping lemma does not cause a contradiction for the string I chose right? $\endgroup$ – user1354784 Oct 28 '16 at 16:25
  • $\begingroup$ I guess that is only true if you specify $a$ and $b$? $\endgroup$ – Hendrik Jan Oct 28 '16 at 21:43

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.