Check Proof Using Pumping Lemma to Show Language Not Regular

Question

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular.

I'll state the pumping lemma here for clarity:

Pumping lemma If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

1. for each $i≥0, xy^i z∈A$,
2. $|y|>0$,
3. and $|xy|≤p$.

Assume that $B$ is regular. I 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 ≥ 0$ the string $xy^iz$ is in $B$. I present the following case to show that this is impossible.

1. Divide $s$ into $xyz$: let $x=ε,y=0^p,z=0^p$. In this case, the string $xyyz$ has more 0s than 1s and so is not a member of $B$, violating condition 1 of the pumping lemma. This case is a contradiction. Therefore $B$ is not regular.

Answer 1

To show there is a problem in your proof, I will try to make a similar proof, using another language. I hope you will find that the conclusion of my proof is incorrect and that you will see the similarities with yours. I will then try to explain in more details what the problem is.

Consider the language $L = \{a^mb^n\mid m,n\geqslant 0\}$. I assume that $L$ is regular. Since it is regular, it verifies the pumping lemma. Let then $p$ be the constant in the pumping lemma, and $s = ab^p$. Since $s\in L$ and $s$ has length greater than $p$, then $s$ can be split into $s = xyz$ where for $i\geqslant 0$, $xy^iz\in L$.

I choose the following split to prove a contradiction: divide $s$ into $x = \varepsilon$, $y = ab$ and $z = b^{p-1}$. In this case, $xyyz = abab^p$ is not a word of $L$ therefore $L$ is not regular.

Now obviously there is a problem with the conclusion because $L = a^*b^*$ is clearly a regular language.

To see the problem, let's do a bit of logic. The pumping lemma states:

Being regular $\Rightarrow$ Verifying pumping lemma conclusion

Therefore, we conclude (with contraposition):

Not verifying pumping lemma conclusion $\Rightarrow$ Not being regular

This is the property used to prove a language is not regular. Let's look a little bit closer to the pumping lemma conclusion:

$\exists p$ such that, $\forall s$ of length $\geqslant p$, $\exists xyz$ verifying the three properties

The negation of that conclusion is therefore:

$\forall p$, $\exists s$ of length $\geqslant p$, $\forall xyz$, the three properties are not verified.

That's why I insist that you need to consider ALL $xyz$ decompositions.

Now to go back to Sipser's proof, contrary to what you seem to say in an above comment, I do not claim that the proof is wrong, I claim that your interpretation of it is wrong. Indeed, Sipser says that for a fixed $p$, we consider $s = 0^p1^p$. He then consider a decomposition where $y$ consists only of $0$'s. But he does that because, implicitly, he considers that the decomposition verifies the properties 2. and 3., meaning that $|y| > 0$ and $|xy| < p$. Since $|xy| < p$, that means $xy$ is included in the $0^p$ part of $s$.

By doing that, he is still considering all decomposition of $s$, but is implicitly discarding those that do not verify 2. or 3. (because those ones are already missing some properties needed for the conclusion of the pumping lemma).

Answer 2

Close but not quite right: pay close attention to the fact that we require that $s$ may be divided into $xyz$ in some way that satisfies the three conditions. You show one division that does not satisfy the conditions; what about the rest of the possibilities? (Hint: $s$ is well-chosen in the sense that it limits the form of $xyz$ divisions quite significantly)