0
$\begingroup$

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free.

From my understanding, we want to prove that all 3 conditions of the pumping lemma hold. This will not guarantee that the language is context-free. However, I have found a case where it breaks

Let the string be $abbccc$

If $u = \lambda$, $v = a$, $x = aa$, $y = a$, $z = bbccc$.

Therefore, when we pump the string for $i = 2$, we get $aaaaaabbcccccc$, which is NOT in the language because we have the same number of $a$'s and $c$'s. How is this possible?

$\endgroup$
  • $\begingroup$ Have you tried w = bcc. The professor hinted to find a w such that it is not pumpable. $\endgroup$ – user86060 Mar 22 '18 at 0:23
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Mar 22 '18 at 9:29
2
$\begingroup$

The Pumping Lemma states: "... there exists a constant $p$ such that for each word $w\in L$ with $|w|\ge p$ there exists a decomposition $w = uvxyz$ such that ...", where $p$ is the pumping constant.

You have chosen your own decomposition, and shown it not fit the pumping property. Perhaps there is another decomposition that will work?

And even in the case your example would work, I can claim that the pumping is larger than 6.

$\endgroup$

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.