1
$\begingroup$

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

$\endgroup$
  • 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$ – Karolis Juodelė Jan 3 '13 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$ – Yuval Filmus Jan 3 '13 at 22:40
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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