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.

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me.

Here is the Definition of Pumping Lemma:

If A is a regular language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions:

  1. for each $i \ge 0$, $xy^iz\in A$,
  2. $|y| > 0$
  3. $|xy|\le p$

Now while explaining why the classic language $B=\{0^n1^n\mid n \ge 0\}$, is not a regular, Sipser gives the following explanations:

Assume the contrary is regular, assume $B$ is regular. Let $p$ be the pumping length given by the pumping lemma. Choose $s$ to be the string $0^p1^p$. Because $s\in B$ and $s$ has length more than $p$, the pumping lemma guarantees that $s$ can be split into three pieces, $s=xyz$, where for any $i\ge 0$ the string $xy^iz\in B$.

However, these cases make this impossible (causing a contradiction):

Case 1 . The string $y$ consists only of $0$s. In this case the string $xyyz$ has more $0$s than $1$s and so it is not a member of $B$, violating condition 1 of the pumping lemma.

Question: I don't understand why assuming $y$ consists of only $0$s, automatically means that the tring $xyyz$ may have more $0$s than $1$s. The string $x$ may be comprised of any number of $0$s and the string $y$ may be comprised of any number of $1$s? My question is, how come the string $xyyz$ results in there being more $0$s than $1$s?

Case 2. The string $y$ consists of both $0$s and $1$s. In this case the string $xyyz$ may have the same number of $0$s and $1$s, but they will be out of order with some $1$s before $0$s. Hence it is not a member of $B$.

Question: Again, with this explanation, I don't understand how they concluded that the string $xyyz$ may have both $0$s and $1$s but out of order, causing a contradiction.

I appreciate any clarification.

Many thanks in advance!

share|improve this question
    
Thanks for pointing that out. See edited. –  Epsilon Mar 10 '13 at 15:15
    
For information on how to get formulas and the like to display properly, this is a good place to start. –  Brian M. Scott Mar 10 '13 at 15:26

2 Answers 2

up vote 2 down vote accepted

For your first question, suppose that $y$ consists entirely of zeroes. Since $s=0^p1^p$, this means that $x=0^k$ and $y=0^\ell$ for some $k\ge 0$ and $\ell\ge 1$ with $k+\ell\le p$, and $z=0^{p-k-\ell}1^p$ is the rest of $s$. But then

$$xy^2z=\underbrace{0^k}_x\underbrace{0^{2\ell}}_{y^2}\underbrace{0^{p-k-\ell}1^p}_z$$

has $k+2\ell+p-k-\ell=p+\ell>p$ zeroes and only $p$ ones. (Remember that $\ell>0$.)

Now suppose that $y$ contains both zeroes and ones. Then $y=0^k1^\ell$ for some positive integers $k$ and $\ell$ such that $k,\ell\le p$. This means that $x=0^{p-k}$, since it must have the rest of the zeroes, and $z=1^{p-\ell}$. Thus,

$$xy^2z=\underbrace{0^{p-k}}_x\underbrace{0^k1^\ell0^k1^\ell}_{y^2}\underbrace{1^{p-\ell}}_z=0^p1^\ell0^k1^p\;.$$

Now $p-k$ might be $0$, i.e., $x$ might be the empty string, but the string $xy^2z$ as a whole definitely has $k>0$ zeroes that are to the right of at least one $1$ (since $\ell\ge 1$), which is impossible for any string in $B$.

share|improve this answer
    
Thanks for the reply. It is not clear to me why s=$0^p$$1^p$ means what you claim it means, in the first line of your explanation, I would appreciate any clarification. –  Epsilon Mar 10 '13 at 15:28
    
@Epsilon: If $y$ is all zeroes, it must be of the form $0^\ell$ for some $\ell>0$. Since $x$ is before $y$ in $s$, $x$ must also consist entirely of zeroes, so it must be of the form $0^k$. However, $x$ could be empty, so $k$ might be $0$. Finally, $xy=0^{k+\ell}$ is the first $k+\ell$ symbols of $s$, and they’re all $0$, so $k+\ell\le p$; if that weren’t the case, $xy$ would be too long to fit in the zero half of $s$. –  Brian M. Scott Mar 10 '13 at 15:32

There seems to be something wrong (or superfluous) with Sipser's treatment (which surprises me). The second case is actually never needed. I'll try to prove an example that can easily be taken to the general case.

WARNING!!! What follows is just a very special case of demonstrating that the language $L = \{ \mathtt{0}^n \mathtt{1}^n : n \geq 0 \}$ is not regular. That special case is thinking that the pumping length of the language is $5$. To prove that $L$ is not regular you would have to alter the sequel to work for any arbitrary natural number $p$.

Suppose that $p = 5$, and consider the string $$w = \mathtt{0}^p \mathtt{1}^p = \mathtt{0}^5 \mathtt{1}^5 = \mathtt{0000011111}.$$ We want to write $w = x y z$ so as to satisfy the following conditions:

  1. $| x y | \leq p = 5$;
  2. $| y | > 0$

Since the string $xy$ must make up an initial part of $w$, and cannot be longer than $5$ characters long, it must come from the first $5$ characters of $w$: these are $\mathtt{0 0 0 0 0}$. In particular $y$ must consist only of $\mathtt{0}$s. Furthermore, since $y$ cannot be the empty string, it must consist of at least one $\mathtt{0}$.

One possible split of this string is $$\overbrace{\mathtt{00}}^{x}\; \overbrace{\mathtt{00}}^y \; \overbrace{\mathtt{011111}}^{z}.$$

Now when we "pump" the $y$ we get strings such as

  • $xy^0z = \mathtt{00} \; \mathtt{011111}$;
  • $xy^1z = \mathtt{00} \; \mathtt{00} \; \mathtt{011111}$;
  • $xy^2z = \mathtt{00} \; \mathtt{00} \; \mathtt{00} \; \mathtt{011111}$;
  • etc.

In general, the number of $\mathtt{0}$s in $x y^i z$ will be $5 + (i-1) |y|$, whereas the number of $\mathtt{1}$s stays constant at $5$.

share|improve this answer
    
Not wrong, but definitely superfluous. If it wasn’t simply a slip of the mind, he probably wanted to illustrate more than one of the things that the pumping lemma can lead to a contradiction. –  Brian M. Scott Mar 10 '13 at 15:29
    
Be careful in giving such examples, I've seen more than my share of students believing they can pick any convenient $p$, or that showing that it doesn't work for $p = 5$ is enough. –  vonbrand Mar 10 '13 at 15:52
    
@Brian: I'm sure that the extra detail is there on purpose, but IMO it is almost anti-pedagogical! If you want to show that more than one thing can go wrong then work with $0^{\lceil p/2 \rceil} 1^{lceil p/2 \rceil}$ and do all the hard work. But not stopping a proof when the result has already been vanquished might confuse students even more. –  Arthur Fischer Mar 10 '13 at 16:08
    
@vonbrand: You're probably right that I should add a simple text warning that the above doesn't actually prove the desired result. Thanks. –  Arthur Fischer Mar 10 '13 at 16:10
    
@Arthur: Oh, I agree; I was just trying to come up with a plausible reason other than brain-fart. –  Brian M. Scott Mar 10 '13 at 16:11

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.