Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – Karolis Juodelė Jan 3 '13 at 22:38
(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$. – Yuval Filmus Jan 3 '13 at 22:40
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


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.