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