# Proving a language is not context free using the Pumping Lemma

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!

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$?
• 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? – user1354784 Oct 28 '16 at 16:25
• I guess that is only true if you specify $a$ and $b$? – Hendrik Jan Oct 28 '16 at 21:43