I have a question about a specific pumping lemma problem for Context-Free Languages.

Suppose we have the following Language:

$L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 \}$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma.

Let $z = a^{n}b^{n+1}c^{n+1}d^{n}$, then $z \in L$.

Than according to the lemma, $z$ can be written as $z = uvwxy$ where the following properties hold:

  1. $|vx| \geq 1$
  2. $|vwx| \leq n$
  3. for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

We have 6 different possibilities for $vwx$:

  1. $vwx = a^{i}$ where $i \leq n$
  2. $vwx = a^{i}{b^j}$ where $i+j \leq n$
  3. $vwx = b^i$ and $i \leq n$
  4. $vwx = b^{i}c^{j}$ and $i+j \leq n$
  5. $vwx = c^{i}$ with $i \leq n$
  6. $vwx = c^{i}d^{j}$ and $i+j \leq n$

Is this right so far? The thing that I'm unsure of is if my different cases for $vwx$ are right.

How do I choose the pumping length for case 2? If I choose $i$ = 2, what if $i$ is zero ? Then I don't have any contradiction.

Thanks in advance

  • 1
    $\begingroup$ No matter how much you pump $b$ or $c$ you won't get a contradiction. This language might not be pumping lemma provable (though don't take my word for it). Intuition about CFGs says that in a long enough string there will be many choices about what to pump and one of them will always fail, but I don't know how to state that formally. $\endgroup$ Jan 3, 2013 at 22:38
  • $\begingroup$ (1) You're using $i$ for two different quantities. (2) If $i = 0$ in case 2, then you're in case 3. (3) In case 3, you can replace $vwx$ with $w$ (i.e. choose $i = 0$ in property 3 of the pumping lemma, but that's a different $i$! better choose a different letter for it), and then you get $a^n b^m c^{n+1} d^n$ where $m < n+1$. $\endgroup$ Jan 3, 2013 at 22:40

1 Answer 1


Let me rephrase property 3 of the pumping lemma: for every $l \geq 0$, $uv^lwx^ly \in L$. Now let's consider the seven different cases:

Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Case 2: $vx = a^ib^j$ where $i,j > 0$. Like case 1 or case 3.

Case 3: $vx = b^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1-i} c^{n+1} d^n \notin L$.

Case 4: $vx = b^ic^j$ where $i,j > 0$. Like case 3 or case 5.

Case 5: $vx = c^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1} c^{n+1-i} d^n \notin L$.

Case 6: $vx = c^id^j$ where $i,j > 0$. Like case 5 or case 7.

Case 7: $vx = d^i$ where $i > 0$. Choose $l = 2$ to get $a^n b^{n+1} c^{n+1} d^{n+i} \notin L$.

  • $\begingroup$ This is something I don't quite get: why do you have to go through all those cases? Isn't one enough to prove that $L \notin CFL$? Here's what I'm thinking: if we say $L\in CFL$, than every word respects the conditions of pumping lemma, right? If one word does not respect these conditions in $any$ of these cases, than it is not in $L$, thus $L \notin CFL$. Isn't that so? $\endgroup$ Aug 2, 2017 at 6:20
  • 1
    $\begingroup$ You don't get to choose the decomposition $z = uvwxy$. The pumping lemma states that if $L$ is context-free then every long enough $z \in L$ has such a decomposition which satisfies certain properties (it can be "pumped"). To refute the conclusion of the lemma, we need to show that no such decomposition of $z$ satisfies the properties. We only used one word $z$, but we had to consider all decompositions. $\endgroup$ Aug 2, 2017 at 6:36
  • $\begingroup$ I think I got it. Thanks! One more question though: I assume that this is also the case for the Pumping Lemma for $REG$? (though on all posts on this website I've seen people only choose one decomposition...) $\endgroup$ Aug 2, 2017 at 7:01
  • 1
    $\begingroup$ Try it out on a concrete example, and everything will get much clearer. $\endgroup$ Jun 3, 2018 at 12:48
  • 1
    $\begingroup$ Yes, that's the idea. $\endgroup$ Jun 4, 2018 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.