This proof in my textbook involving the pumping lemma appears incorrect - is it?

467 Views Asked by At

It states

Let $B$ be the language $\{0^n1^n2^n | n \geq 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^p2^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 \geq 0$ the string $xy^iz$ is in $B$. We consider the two cases to show that this result is impossible.

Case 1. The string $y$ consists only of 0s, only of 1s, or only of 2s. In these cases, the string $xyyz$ will not have equal numbers of 0s, 1s, and 2s. Hence $xyyz$ is not a member of $B$, a contradiction.

I only included case 1 because that is where my question lies. How could $y$ ever consist of only $1s$ or $2$s?

If $y$ consisted of only 1s, then $x$ must consist of all of the $0$s contained in the string $s$ (and it may include 1s as well). Then the length of $x$ would be at least $p$. So combined, the length of $xy$ would be greater than $p$. But the pumping lemma says that the length of $|xy| \leq p$. For instance, if $y$ consisted of only $1$s, then $x = 0^p1^{p - a - b}$, $y = 1^a$, $z = 1^{b}2^p$ for some $a, b$ such that $a + b \leq p$. This seems problematic because then $|xy| > p$.

A similar problem occurs were $y$ to consist of only $2$s.