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.


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

  • 1
    $\begingroup$ 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. $\endgroup$ – dkaeae May 21 '19 at 7:22
  • $\begingroup$ Do you also think it doesn’t add up? $\endgroup$ – Mr DrinkSoju May 21 '19 at 7:47
  • $\begingroup$ You cannot choose $n=-1$ since $n$ has to be non-negative. It's probably a mistake. $\endgroup$ – Yuval Filmus May 21 '19 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.