# What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"):

2.42 Let $$E = \{1,\#\}$$ and $$Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for k \geq 0, each t_i \in 1^*, and t_i \neq t_j whenever i \neq j}\}$$.

Prove that $$Y$$ is not context free.

Solution:

Consider a string $$1^p\#1^{p+1}\# ... \#1^{2p-1}\#1^{2p}\#1^{2p+1}\# > ... \#1^{3p}$$ where $$p$$ is pumping length. While pumping there can be three possibilities :

1. If either v or y has a #. If so, then pump string 3 times. Let's say hash is in v s.t. $$v = 1^m\#1^n$$, then $$v^3$$ will be $$1^m\#1^n1^m\#1^n1^m\#1^n = 1^m\#1^{n+m}\#1^{n+m}\#1^n$$. Otherwise # will be in y, which can be shown similarly.

2. If # lies in $$x, > a$$. $$v$$ lies in $$1^j$$ such that $$j<2p$$. if $$|v| = 1$$then pump up it twice, else if $$|v| > 1$$ then pump up it once. We must get $$t_i$$ which will be equal to some $$t_j$$. I have considered to pump twice if $$|v| = 1$$ because it may happen that $$|y| \neq 0$$. Think what am I talking. b. $$y$$ lies in $$1^j$$ such that $$j \geq 2p$$. if $$|y| = 1$$ then pump down it twice, else if $$|y| > 1$$ then pump down it once. c. If one of the $$v$$ and $$y$$ is empty then pump other up or down once depending on where it lies i.e. $$1^j$$ $$j$$ is greater than $$2p$$ or other way.

3. If both $$v$$ and $$v$$ lies in same $$1^j$$, and $$j \leq 2p$$ then pump up it once. Else if $$j > 2$$p then pump down it once.

## My Question

I know that in pumping lemma if language $$L$$ is a CFL, then $$w \in L = uvwxy$$ and $$uv^nwx^ny \in L$$ for all $$n\geq 0$$.

How can I pump down it twice? I think it means $$n = -1$$.

• In the version of Sipser's book that I have (3rd edition), this is exercise 2.54 and no answer is provided. If yours is an older edition, consider the possibility of the solution having a "bug" and having been removed in later editions. – dkaeae May 21 at 7:22
• Do you also think it doesn’t add up? – Mr DrinkSoju May 21 at 7:47
• You cannot choose $n=-1$ since $n$ has to be non-negative. It's probably a mistake. – Yuval Filmus May 21 at 8:03