# How does Sipser's proof that $0^n1^n$ is not regular work?

In Sipser's Introduction to the Theory of Computation this is how $$0^n1^n$$ is proved to be not regular

Example 1.73:

Let $$B$$ be the language $$\{0^n1^n|n \ge 0\}$$

We use the pumping lemma to prove that $$B$$ is not regular. The proof is by contradiction. Assume to the contrary that $$B$$ is regular. Let $$p$$ be the pumping length given by the pumping lemma. Choose $$s$$ to be the string $$0^p1^p$$. Because $$s$$ is a member of $$B$$ and $$s$$ has length more than $$p$$, the pumping lemma guarantees that $$s$$ can be split into three pieces, $$s = xyz$$, where for any $$i \ge 0$$ the string $$xy^iz$$ is in $$B$$. We consider three cases to show that this result is impossible.

• The string $$y$$ consists only of $$0$$'s. In this case, the string $$xyyz$$ has more $$0$$'s than $$1$$'s and so is not a member of $$B$$, violating condition 1 of the pumping lemma. This case is a contradiction.

• The string $$y$$ consists only of $$1$$'s. This case also gives a contradiction.

• The string $$y$$ consists of both $$0$$'s and $$1$$'s. In this case, the string $$xyyz$$ may have the same number of $$0$$'s and $$1$$'s, but they will be out of order with some $$1$$'s before $$0$$'s. Hence it is not a member of $$B$$, which is a contradiction.

In the first condition ($$y$$ consists only of $$0$$'s), why would the string $$xyyz$$ have more $$0$$'s than $$1$$'s?

Let's say that $$|x|=p-2$$ and consists only of $$0$$'s. $$|y| = 1$$ and $$y=0$$, $$|z| = p$$ and consists only of $$1$$'s. At this point $$|y| > 0$$ and $$|xy| \le p$$.

In this case we would have the same number of $$0$$'s and $$1$$'s without violating any of the constraints of the pumping lemma. Of course $$xyyyz$$ would violate it then, but that's not his proof.

My question is, why does he state that the number of $$0$$'s is larger than the number of $$1$$'s for $$xyyz$$?

If $$x$$ consists of $$p-2$$ zeros, $$y$$ is 0 and $$z$$ consists of $$p$$ ones, then $$xyz$$ is $$0^{p-1}1^p$$, not $$0^p 1^p$$. Hence, the particular partition you give is impossible. If $$|xy| < p$$, then $$z$$ must take the remaining zeros.
Recall that we started with the assumption that the string $$0^p 1^p$$ was partitioned into three section $$x,y,z$$. This implies the number of zeros in $$x,y,z$$ must be $$p$$, and since $$y$$ is 0, $$xyyz$$ will have more $$0$$'s than $$1$$'s.
With the way you split your string, $$|z|$$ is $$p +1$$ and not $$p$$. Then, $$z$$ will be $$01^p$$ and not $$1^p$$. And with this, the proof stated by Sipser still holds.