0
$\begingroup$

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.
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Nov 9, 2021 at 19:25
  • $\begingroup$ @Nathaniel So do you disagree with the answer (and answerer, John L.) to the following question? cs.stackexchange.com/questions/145557/… $\endgroup$
    – billiam
    Nov 18, 2021 at 4:30
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Nov 18, 2021 at 7:46
  • $\begingroup$ @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. $\endgroup$
    – billiam
    Nov 18, 2021 at 22:00
  • $\begingroup$ Sorry for the confusion. "this question" was referring to this one. $\endgroup$
    – Nathaniel
    Nov 18, 2021 at 22:02

2 Answers 2

0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ @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) $\endgroup$
    – kviiri
    Nov 9, 2021 at 19:42

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.