3
$\begingroup$

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!

  • 0
    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's2011-08-20

1 Answers 1

3

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

  • 0
    your example it's OK! But if you take y=01, it works accordingly to the shape2011-08-20
  • 0
    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$.2011-08-20
  • 0
    but why it contradicts, it looks exactly as pattern looks 012011-08-20
  • 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$.2011-08-20
  • 0
    Thank you for pointing this out! Now everything became clear.2011-08-20
  • 0
    It took me a while to figure out the reason for your doubts! It is very important to know what the shortcut symbolism *means*.2011-08-20