0
$\begingroup$

I have just started reading about the Pumping Lemma, and I have some difficulties understanding the proofs of non-regularity of languages.

For example, in the book I am reading there's a proof for the fact that the language

$$C =\{w \mid \text{ w has an equal number of 0s and 1s} \}$$ is not regular.

The proof starts like this:

Assume to the contrary that $C$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $0^p1^p$. With $s$ being a member of $C$, and having 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 \in C$$ We would like to show that this outcome is impossible. But wait, it is possible! If we let $x$ and $z$ be the empty string and $y$ be the string $0^p1^p$, then $xy^iz$ always has an equal number of $0$s and $1$s and hence is in $C$. So it seems that $s$ can be pumped.

Here condition 3 in the pumping lemma is useful. It stipulates that when pumping $s$, it must be divided so that $|xy| \leq p$. That restriction on the way that $s$ may be divided makes it easier to show that the string $s = 0^p1^p$ we selected cannot be pumped. If $|xy| \leq p$, then $y$ must consist only of $0$s, so $xyyz \not \in C$. Therefore, $s$ cannot be pumped. That gives us the desired contradiction.

The part that I really didn't catch is the last paragraph, when the third condition (which is explained in the proof immediately after) is used.

The third condition says that the length of the concatenation between $x$ and $y$ must be less or equal to the number $p$ (the pumping length).

Specifically, the part that I don't understand is

If $|xy| \leq p$, then $y$ must consist only of $0$s, so $xyyz \not \in C$.

Why then $y$ must consist of only $0$s? And so why $xyyz \not \in C$?

In general, if you give an explanation of the proof with more details, I might eventually understand it better.

$\endgroup$
1
$\begingroup$

Remember that $s = 0^p1^p = xyz$. Now, if $|xy| \leqslant p$, then $xy$ is a prefix of $0^p$ and hence consists only of $0$s. Now, $y$ being a suffix of $xy$, it also consists only of $0$'s. Therefore, denoting by $|u|_0$ ($|u|_1$) the number of $0$s ($1$s) in a word $u$, one gets $|y|_0 = |y|$ and $|y|_1 = 0$, whence $$ |xyz|_0 = |s|_0 = p = |s|_1 = |xyz|_1 $$ but $$ |xyyz|_0 = |xyz|_0 + |y|_0 = p + |y| \quad \text{and}\quad |xyyz|_1 = |xyz|_1 + |y|_1 = p + 0 = p $$ It follows that if $y$ is a nonempty word, $xyyz \notin C$.

$\endgroup$
  • $\begingroup$ Why if $|xy| \leq p$, then $xy$ is a prefix of $0^p$? We only know that $|s| \geq p$... not sure about that implication... $\endgroup$ – nbro Nov 15 '15 at 19:52
  • $\begingroup$ No, we know that $s = 0^p1^p$. See the sentence "Let $s$ be the string $0^p1^p$" in your question", right after the sentence containing the word pumping length. $\endgroup$ – J.-E. Pin Nov 15 '15 at 19:54
  • $\begingroup$ Yes, I understood that the prover chose $s = 0^p1^p$, but I don't understand your statement: "Now, if $|xy| \leq p$, then $xy$ is a prefix of $0^p$". Why $xy$ is a prefix of $0^p$? We don't know what part is $x$ or what part is $y$ (or do we?). I am really not getting the implication I mentioned above that you said, maybe because I am not so familiar with these concepts... $\endgroup$ – nbro Nov 15 '15 at 20:01
  • $\begingroup$ OK. Take the word $s = 000111$ and consider a prefix of length $\leqslant 3$ of $s$: what are the possibilities? $\endgroup$ – J.-E. Pin Nov 15 '15 at 20:05
  • $\begingroup$ I guess $0$, $00$ and $000$...Ok, so, since $0^p1^p$ contains half of the symbols $0$s (on the left side) and the other half is of $1$s (on the right side), and the length $xy$ is not greater than $p$, and $xy$ is the first part of the string $s$, then it contains just $0$s. Anyway, these are a lot of guesses, of course it becomes difficult to understand these proofs, IMO, but maybe I am just not intelligent enough (or maybe I just need to practice more). $\endgroup$ – nbro Nov 15 '15 at 20:10

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.