7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ You're right that $y$ can't consist of all $1$'s or $2$'s if $xyz=0^p 1^p 2^p$ and $|xy|\le p$; in fact, it must consist of all $0$'s. But a proof by contradiction is still correct if the contradiction can be reached without leveraging all the assumptions, and that's what they're doing here. There may be some pedagogical reason to walk through the various cases. In this case, though, I agree with you that the short proof is the more elegant one. Their proof would make more sense if they said, "Choose $s$ to be $0^k 1^k 2^k$, where $3k\ge p$." $\endgroup$ – mjqxxxx Feb 25 '14 at 23:28
  • $\begingroup$ mjqxxxx - Thank you for your response. I believe I have a proof that is correct: Since $|xy| \leq p$, $x = 0^a$, $y = 0^b$, and $z = 0^{p - a - b}1^p2^p$, where $a + b \leq p$. Let $i = b$. Then $xy^iz = 0^a0^{bp}0^{p - a - b}1^p1^p = 0^{p + (p - 1)b}1^p1^p$. Hence $xy^iz$ is not in the set. What do you think? $\endgroup$ – Joseph DiNatale Feb 25 '14 at 23:41
  • $\begingroup$ @mjqxxxx Why don't you write it as an answer, for Joseph DiNatale to accept it? $\endgroup$ – frabala Aug 26 '15 at 6:46
0
$\begingroup$

Answer from mjqxxxx (in comment that I put here to void seeing this question as unanswered.

You're right that y can't consist of all 1's or 2's if $xyz=0^p1^p2^p$ and $|xy|\leq p$; in fact, it must consist of all $0$'s. But a proof by contradiction is still correct if the contradiction can be reached without leveraging all the assumptions, and that's what they're doing here. There may be some pedagogical reason to walk through the various cases. In this case, though, I agree with you that the short proof is the more elegant one. Their proof would make more sense if they said, "Choose s to be $0^k1^k2^k$, where $3k\geq p.$"

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