# Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma:

$L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$

Now I realize that the condition $m \equiv 0 \space mod \space n$, is essentially saying that $m$ is some multiple of $n$. Is it possible that could you go about proving that $L$ is not regular in the way that you can prove that $L = \{0^n 1^n\}$ is not regular since $m$ is a multiple of $n$, since $m = kn$ (where $k$ is some integer)?

Updated:

-- My attempt at the proof:

If the language $L$ is regular, then by the pumping lemma $\exists \space p \space | \space \forall s \in L \cap \Sigma ^{\geq p}$.

Next by the pumping lemma $\exists x, y, z : s = xyz$, where $s$ is a string such that:

(1) $|y|\geq1$

(2) $|xy|\leq p$

(3) $\forall i\geq0, xy^iz \in L$

Now suppose we let $m = kp$, where $k$ is some integer, let the string $s = 0^p 1^{kp}, s\in L$ and $|s|\geq p$. By the pumping lemma the decomposition of $s$ is defined by $s = xyz$. Now we show that $\forall x, y, z$ that (1)-(3) do not hold.

If (1) and (2) hold, then $s=0^p1^{kp} = xyz$, with $|xy|\leq p$ and $|y|\geq 1$.

So $x = 0^u, y=0^v, z=0^w1^{kp}$

$u+v \leq p$, $v \geq 1$, $w \geq 0$

$u+v+w = kp$

But (3) fails for $i=2$ since $xy^2z = 0^u0^v0^v0^w1^{kp} = 0^{u+2v+w}1^{kp} \not\in L$ since $u+2v+w \neq kp$

Hence $L$ is not a regular language.

Is this the correct way to go about this proof?

• Yes, a minor adaptation of the proof should work. Did you try? Where did you get stuck? – Gilles 'SO- stop being evil' Sep 19 '13 at 23:33
• Bingo! you got it.. why don't you answer your question yourself here :) – Subhayan Sep 19 '13 at 23:39
• It's even easier since for $m \not= 0$ and $n$ large enough, $m = 0 \mod n$ never holds. Hence pumping in the word $0^p1^p$ by adding $0$ gives you immediately the desired result. – Tpecatte Sep 20 '13 at 7:36
• I tried to go about using the method of doing the proof using the pumping lemma for $0^p 0^p$, and added it to the main post. Is this the right idea, or am I completely off track? – rsxjan Sep 20 '13 at 19:44
• This is the idea, but $0^{u+w}1^{kp}$ could be in $L$. So my idea was taking $0^p1^p$, then $xy^2z = 0^{p+v}1^p \not\in L$ – Tpecatte Sep 20 '13 at 19:50

## 2 Answers

Here is a nicer proof, (implicitly) using the Myhill-Nerode criterion. Let $p_1,p_2,p_3,\ldots$ be the list of all primes, and consider the words $x_i = 0^{p_i}$, $y_i = 1^{p_i}$. Then $x_i y_i \in L$ while $x_i y_j \notin L$ for $i \neq j$. So given a DFA for $L$, if $\sigma_i$ is the state that the DFA is at after reading $x_i$, we must have $\sigma_i \neq \sigma_j$ for $i \neq j$ (why?), so the DFA must have infinitely many states.

• This is actually a very elegant proof; is there an elegant proof such as this using the pumping lemma for this question? – rsxjan Sep 20 '13 at 21:28
• Yes. Let $p$ be the constant in the pumping lemma, and let $q \geq p$ be prime. Consider the word $w = 0^q 1^q \in L$. Let $w = xyz$ as in the lemma, and consider $xz = 0^r 1^q$ for some $r < q$. Since $q$ is prime, we cannot have both $r \geq 2$ and $r \mid q$. – Yuval Filmus Sep 20 '13 at 22:22

A bit simpler: Assume $$L$$ is regular, so it satisfies the pumping lemma. Call the constant of the lemma $$p$$, and take the string $$w = 0^p 1^p$$, we have that $$w \in L$$ and $$\lvert w \rvert = 2 p \ge p$$. By the lemma, we can write $$w = x y z$$ with $$\lvert x y \rvert \le p$$, $$y \ne \epsilon$$, so that for all $$k \ge 0$$ we have $$x y^k z \in L$$. Now $$y$$ is $$0^r$$, for $$1 \le r \le N \le p$$, if we consider $$k = 2$$ we have $$x y^2 z = 0^{p + r} 1^p$$, and certainly $$p \not\equiv 0 \pmod{p + r}$$, contradiction.