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?

| cite | improve this question | | | | |
  • $\begingroup$ 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. $\endgroup$ – bulletshot60 Mar 7 '17 at 21:11

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.

| cite | improve this answer | | | | |
  • $\begingroup$ Thanks. I thought that neither v or x could be empty, but one of them can be. $\endgroup$ – bulletshot60 Mar 7 '17 at 21:42

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.