1
$\begingroup$

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$?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\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.