# Pumping lemma for Context-Free Languages

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.

-
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

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

-