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

• 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? – theSongbird Aug 2 '17 at 6:20
• 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. – Yuval Filmus Aug 2 '17 at 6:36
• 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...) – theSongbird Aug 2 '17 at 7:01
• Try it out on a concrete example, and everything will get much clearer. – Yuval Filmus Jun 3 '18 at 12:48
• Yes, that's the idea. – Yuval Filmus Jun 4 '18 at 5:50