Let us observe the language $\newcommand{\lang}{\mathcal L} \lang = \newcommand{\set}[1]{\left\{ #1 \right\}}\set{ 0^i 1^n 2^n \mid i \geq 1, n \in \mathbb{N}}$. Can any of the substrings indicated with $[\ldots]$ below be pumped using the pumping lemma for context free languages?

  1. $00[0]11112222$
  2. $00[01]1112222$
  3. $00011[1122]22$


The pumping lemma for context free languages states, that if a language $\lang$ is context free, after some limiting length $\ell$ any string $x \in \lang$ should be partitionable into the string $x =x_1 x_2 x_3 x_4 x_5$, where $x_2x_4 \neq \epsilon$ and $\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}\abs{x_2x_3x_4} \leq \ell$, so that $x^\prime = x_1x_2^kx_3x_4^kx_5 \in \lang$ for any $k\geq 0$ as well. The repetition of the strings $x_2$ and $x_4$ in the middle of the string $x$ is called pumping.

Because of this:

  1. is not an option, as $[0] = [x_2x_3x_4]$ would mean that either $x_2$ or $x_4$ is empty.

  2. This does not work either, as $[01] = [x_2x_3x_4]$ would mean that for $k\neq 1$, the pumped word would no longer be in the language. This is because the number of $1$s would either exceed or subceed the number of $2$s.

  3. This is a bit trickier, as with $[1122] = [x_2x_3 x_4]$ we could choose $x_2=11$, $x_3 = \epsilon$ and $x_4 = 22$. Now pumping the strings $x_2$ and $x_4$ would still have the word $x^\prime$ in the language: the increase (or decrease) of the number of $1$s is always matched by the changes in the number of $2$s. So this seems to match the requirements for pumping.

However, according to a certain question submit form, my answer is incorrect and option 3 cannot be pumped at the indicated location. Why is that? Does it have something to do with the pumping length $\ell$ of the word $x$?


1 Answer 1


I think you are just right. Maybe there was a typo in the submit form.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .