Problem Detail: 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 igeq0, xy^iz in L$ Now suppose we let $m = kp$, where $k$ is some integer, let the string $s = 0^p 1^{kp}, sin 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} notin L$ since $u+2v+w neq kp $ Hence $L$ is not a regular language. Is this the correct way to go about this proof?
Asked By : rsxjan
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14453
