Show $\{0^m1^n | m \neq n\}$ is not regular

Question

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.

Answer 1

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.