1
$\begingroup$

I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable by the separate pumping lemma for linear languages (as given in Linz's book), but my question is different.

Evidently this is a CFL, and a pushdown automaton can be constructed for it. But if I apply the pumping lemma for CFLs, I find that I'm able to pump strings that don't belong to the language, which would mean that the language is not a CFL. Clearly I'm doing something wrong.

Going by the "game-like" format given in Linz, say you pick $w = a^mb^mc^{2m}$, $|w| \ge m$. The adversary can choose a number of decompositions $w = uvxyz$, they can look like -:

  • $v = a^k, y = a^l$: The case where $|vxy|$ is contained within the $a$'s of the string. Pump $i = 0$, and then $w_0 = a^{m – (k + l)}b^mc^{2m}$ cannot be in the language since the equality no longer holds.
  • $v = a^k, y = b^l$: The case where $v$ is in the $a$ section, $x$ spans across the $a$'s and $b$'s, and $y$ is in the $b$ section. Again, pump $i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ cannot be in the language.

There are more cases like these. Where am I going wrong in the application of the CFL PL?

$\endgroup$
2
  • 1
    $\begingroup$ To correctly apply the pumping lemma and show that the language is not context free, all partitions $uvxyz$ of your chosen string should have the property that pumping them leads to strings that do not belong to the language. $\endgroup$
    – frabala
    Aug 16 '20 at 12:12
  • $\begingroup$ That makes sense. Is my application of the lemma then correct here? - Say the adversary selects $v = b^k$ and $y = c^l$. Are they allowed to select $k = l$? In that case, the word becomes $w_i = a^mb^{m + (i - 1)k}c^{2m + (i - 1)l}$ on pumping. If $k = l$, no matter what $i$ I choose, the word will always be in the language because we're removing/adding equal parts from/to $b$ and $c$. This also means I can't just conclude from one case violation that the language is not a CFL. Real bummer. $\endgroup$
    – PritishC
    Aug 16 '20 at 12:42
1
$\begingroup$

The pumping lemma for CFL states that if $L$ is a CFL, there exists a constant $N \ge 1$ such that for all $\omega \in L$ with $\lvert \omega \rvert \ge N$ there is a division $\sigma = u v w x y$ with $\lvert v w x \rvert \le N$ and $v x \ne \varepsilon$ such that $u v^k w x^k y \in L$ for all $k \ge 0$.

(The pumping lemma for regular languages is similar, the discussion below applies with minor changes).

You want to prove by contradiction that $L$ is not a CFL. So you assume $L$ is a CFL, and get a contradiction to the lemma. This means, in detail:

  • As $L$ is a CFL, it satisfies the lemma. In particular, there is a constant $N$ such that...
  • As the lemma states all long strings in $L$ can be divided, you are free to pick one that is easy to work with.
  • The lemma states there is some division of $\omega$ such that.... for all $k \ge 0$...; to contradict the lemma you have to prove no division works. In practice, you take a given division of your $\omega$ (any division) and for it pick some $k$ for it that doesn't give a string in the language. You might need to divide this into cases.

What happens for strings that don't belong to the language, or are shorter than $N$, is completely irrelevant. It might be that some strings can be pumped, that some values of $k$ work for all strings, ... What is crucial is that for one string $\omega$ (the one you picked) no division works with one value of $k$ (again, the one you picked). As the lemma asserts it works for all long enough strings, with some division for all $k$, one counterexample is enough. Infinite examples prove nothing.

$\endgroup$
1
  • 1
    $\begingroup$ I finally understand what they mean by "one counterexample". This makes it much clearer and now I see where I was going wrong. Thank you! $\endgroup$
    – PritishC
    Aug 17 '20 at 8:11

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.