# Check Proof Using Pumping Lemma to Show Language Not Regular

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.
• You cannot chose the values of $x$, $y$ and $z$ yourself. You can chose a particular $s$, but then you must show that there is a contradiction for ANY decomposition $s = xyz$. Usually, we consider any decomposition $s =xyz$ that satisfies 2. and 3. and shows that it cannot satisfy 1. Commented Nov 9, 2021 at 19:25
• @Nathaniel So do you disagree with the answer (and answerer, John L.) to the following question? cs.stackexchange.com/questions/145557/… Commented Nov 18, 2021 at 4:30
• No because in this question, you are talking about "a case" (among all of them) of decomposition, and you do not conclude that $B$ is not regular ($B$ is indeed not regular, but the proof is insufficient). What you would need to do is consider other decompositions too, where $|y| < p$ (which would lead to the right conclusion). Commented Nov 18, 2021 at 7:46
• @Nathaniel Thank you for your reply. These are good points you bring up. 1) I'm a bit confused by your reply. When you say "this question", do you mean the one here on this page? If so, I do conclude that 𝐵 is not regular. It is the very last sentence in the question. Commented Nov 18, 2021 at 22:00
• Sorry for the confusion. "this question" was referring to this one. Commented Nov 18, 2021 at 22:02

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)

• @billiam The case you presented is correct but you need to present more cases. You present only one $xyz$ division and that it does not satisfy the conditions, but you must show NO legal $xyz$ division exists. (And no, you chosen division does not satisfy the conditions, but that is ok; we are trying to prove that the language is not regular after all) Commented Nov 9, 2021 at 19:42

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).