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)?


-- 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?

  • 1
    $\begingroup$ Yes, a minor adaptation of the proof should work. Did you try? Where did you get stuck? $\endgroup$ – Gilles 'SO- stop being evil' Sep 19 '13 at 23:33
  • $\begingroup$ Bingo! you got it.. why don't you answer your question yourself here :) $\endgroup$ – Subhayan Sep 19 '13 at 23:39
  • $\begingroup$ 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. $\endgroup$ – Tpecatte Sep 20 '13 at 7:36
  • $\begingroup$ 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? $\endgroup$ – rsxjan Sep 20 '13 at 19:44
  • $\begingroup$ 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$ $\endgroup$ – Tpecatte Sep 20 '13 at 19:50

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.

  • 1
    $\begingroup$ This is actually a very elegant proof; is there an elegant proof such as this using the pumping lemma for this question? $\endgroup$ – rsxjan Sep 20 '13 at 21:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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.


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.