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

Question

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?

Answer 1

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.

Answer 2

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.