# Failure of the Pumping Lemma

On the Wikipedia page for the Pumping Lemma for Context-Free Languages, a language, $$\{b^j c^k d^l | j, k, l \in N\} \cup \{a^i b^j c^k d^l | i > 0, j = k = l\}$$ is introduced. The pumping lemma proof for this supposedly fails because, given a string without a's, you can pump the b's and, given a string with a's, you can pump the a's. In either case, all of the possible cuttings are pumpable according to the constraints of the language.

For example, given the string $$a^k b^k c^k d^k$$ you can split vwx over |a| and pump, leaving |b| = |c| = |d|.

Why can the string $$a b^k c^k d^k$$ not be used?

This seems to meet all the constraints of the pumping lemma, and you cannot split vwx across |a|. If v = a then x must contain at least one b. The string cannot be pumped for any i > 2 as the |b| will exceed the length of |c| and |b| will exceed the length of |d|.

Is there some reason that |a| > 1 or |a| = k?

• I realize that this example as well as { a^i b^j c^k | i = j or j = k but not both } are commonly used to transition into a discussion of Ogden's Lemma. I am curious as to why the above string cannot be used to show the language is not context-free. – bulletshot60 Mar 7 '17 at 21:11

## 1 Answer

The condition of the Pumping lemma is fulfilled for words of the form $ab^kc^kd^k$.

Pick $v=a$, $u=x = \varepsilon$, and $w$, $y$ arbitrary.

• Thanks. I thought that neither v or x could be empty, but one of them can be. – bulletshot60 Mar 7 '17 at 21:42