1
$\begingroup$

I'm going through Michael Sipser's Introduction to the Theory of Computation, and in one of the exercises we are asked to show that $\{0^m1^n | m \neq n\}$ is not a regular language (i.e. is not accepted by a finite automaton). The author gives two proofs, one of them by directly using the pumping lemma on the string $0^p1^{p+p!}$, where $p$ is the pumping length.

I came up with a different solution while reading the answer, which is probably incorrect because the textbook proof is more complicated. I was hoping someone could tell me where the error is: take $01^{p+1}$. Then $01^{p+1}=xyz$ for some $|y|>0$, $|xy|\leq p$ and y can be pumped. Then necessarily $y=0$, because $(01^m)$ can't be pumped for $1 \leq m$. This means $0^{p+1}1^{p+1}$ is in the language, which is a contradiction.

Did I make a mistake, and if so where? Thanks.

$\endgroup$
  • $\begingroup$ Why $y$ cannot be equal to $1$? $\endgroup$ – Boris Novikov Aug 31 '13 at 6:48
  • $\begingroup$ @BorisNovikov: Thanks, I'm dumb sometimes. $\endgroup$ – row Aug 31 '13 at 6:57
  • 1
    $\begingroup$ Can you use the complement? $\endgroup$ – daniel Feb 18 '17 at 3:33
2
$\begingroup$

It appears that you’ve misunderstood the use of the pumping lemma. You want to show that no matter how you decompose $01^{p+1}$ into $xyz$ with $|xy|\le p$ and $|y|>0$, there is an $n\ge 0$ such that $xy^nz\notin L$. You want to do this because the pumping lemma says that if $L$ were regular, you could find at least one decomposition such that $xy^nz\notin L$ for all $n\ge 0$.

Suppose that you decompose $01^{p+1}$ as $x=0$, $y=1^k$ with $1\le k\le p-1$, and $z=1^{p+1-k}$. Then

$$xy^nz=01^{nk}1^{p+1-k}=01^{p+1+(n-1)k}\;.$$

Since $n\ge 0$, $p+1+(n-1)k\ge p+1-k$. Moreover, $k\le p-1$, so $$p+1-k\ge p+1-(p-1)\ge 2\;,$$ and therefore $xy^nz\in L$ for all $n\ge 0$. In other words, there is a possible decomposition of $01^{p+1}$ that cannot always be pumped outside of $L$. Since this is what we would expect if $L$ were regular, this does not prove that $L$ is not regular.

$\endgroup$
  • $\begingroup$ +1 (at least) because before reading this answer, I didn't know what the pumping lemma was, but now I do! $\endgroup$ – Greg Martin Jun 1 '14 at 19:27

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.