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$
2
  • $\begingroup$ Have you tried w = bcc. The professor hinted to find a w such that it is not pumpable. $\endgroup$
    – user86060
    Commented Mar 22, 2018 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
    Commented Mar 22, 2018 at 9:29

1 Answer 1

3
$\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 and acknowledge you have read our privacy policy.

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