Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks!

share|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
add comment

1 Answer 1

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|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
2  
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
show 1 more comment

Your Answer

 
discard

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.