Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It seems like I missed something in pumping lemma. Please, help me out

Let's take the simple example from Sipser's book

Prove that language $L = \{0^n1^n | n>=0 \}$ is nonregular. Following the pumping lemma, we choose $s$ to be the string $0^p1^p$, split $s$ into three pieces $s=xyz$ and consider three cases

1) $y$ consists of 0s. (contradiction is understood). OK!

2) $y$ consists of 1s. (contadiction is understood). OK!

3) $y$ consist of both 0s and 1s. "In this case the string xyyz may have the same number of 0s and 1s, but they will be out of order with some 1s before 0s" (but wait a second, we can restrict the order only to allowed one, not understood). not OK!

The same proof can be taken from wikipedia with different explanation

wikipedia page

"By the pumping lemma, there must be some decomposition w = xyz with |xy| ≤ p and |y| ≥ 1 such that $xy^iz$ in L for every i ≥ 0. Using |xy| ≤ p, we know y only consists of instances of a"

(but why only a, completely not understood ). not OK!

Please, all I need is just a hist, what I've missed


share|cite|improve this question
The reason why you only get instances of 0 this case is because you picked the string $0^p1^p$, where p is your pumping length, then you can use $|xy| \leq p$, which implies that y can only be one or more 0's – sxd Aug 20 '11 at 12:53
up vote 3 down vote accepted

Hint: We have strings $x$, $y$, $z$, with $y$ of positive length, such that $xyz$, $xyyz$, $xyyyz$, and so on are in the language.

If $y$ consists of all $0$'s, there will be "unbalanced" words in the language (too many $0$'s). But in the language, every word has equal numbers of $0$'s and $1$'s. (This part you understood.)

The same argument applies if $y$ has $1$'s only.

Suppose now that $y$ is "mixed," worst case is something like $y=000111$. (This is worst because if the number of $0$'s in $y$ was greater than the number of $1$'s, then $xyyz$ would have too many $0$'s. But actually the argument below doesn't depend on whether $y$ is balanced.)

If $y=000111$, then $x000111000111z$ will be in the language. That's a contradiction, for in $$x000111000111z$$ the $0$'s do not all precede the $1$'s. The $0$ after the first $111$ is to the right of a $1$. (In any expression of shape $0^n1^n$, all the $0$'s are to the left of every $1$, no $0$ is ever to the right of a $1$.)

share|cite|improve this answer
your example it's OK! But if you take y=01, it works accordingly to the shape – com Aug 20 '11 at 12:17
The choice $y=01$ also gives a contradiction, for then $x0101z$ will be in the language, and this has a $0$ to the right of a $1$, just like in my $y=000111$. – André Nicolas Aug 20 '11 at 12:36
but why it contradicts, it looks exactly as pattern looks 01 – com Aug 20 '11 at 16:47
The language $0^n1^n$ means empty word, also $01$, also $0011$, also $000111$, also $00001111$, and so on and that's all. So for example $0101$ is not in the language. If we want empty word, also $01$, also $0101$, also $010101$, and so on, we write $(01)^n$. That's very different from $0^n1^n$. Your difficulty has to do with the fact that you are misinterpreting the meaning of $0^n1^n$. – André Nicolas Aug 20 '11 at 17:36
Thank you for pointing this out! Now everything became clear. – com Aug 20 '11 at 18:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.