2
$\begingroup$

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?

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • 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, 2013 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$ Sep 20, 2013 at 22:22
0
$\begingroup$

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.

$\endgroup$

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.