# Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

i have seen this question where someone was asking if $$\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$$ is context free.

Then there was an answer that says that it is context free because:

The language, in turn, is context-free. This is because we can write it as a union of context-free languages:

• Words not of the form $$a^*c^*b^*$$

• Words of the form $$a^nb^mc^k$$ where 𝑛>𝑚

• Words of the form $$a^nb^mc^k$$ where 𝑚>𝑘.

So my question is, why can't i take the language $$\{a^nb^nc^k | n > m > k\}$$?

Isn't that also the complement of the language?

If so, that would be pumpable with the word z = $$a^{n+2}b^{n+1}c^n$$ right?

I am a little bit confused and feel like i missed something.

No. $$\{a^nb^mc^k\mid n>m>k\}$$ is not the complement of $$\{a^nb^mc^k\mid n\le m\le k\}$$, for two reasons.

(1) The negation of the logical statement "$$P\land Q$$" is not "$$\lnot P\land \lnot Q$$", it is "$$\lnot P\lor \lnot Q$$".

(2) The original language consists of only strings in the language $$a^*b^*c^*$$, so the complement must include all strings where the order of symbols is not alphabetical.

As a consequence the complement of "$$n\le m\le k$$" is then the union of three languages "$$n>m$$", "$$m>k$$", "not alphabetical", each of which is context-free. Occasionally the "not alphabetical" part $$\{a,b,c\}^*\setminus a^*b^*c^*$$ is overlooked, but as that is a regular language it is the least problematic part.

Isn't that also the complement of the language?

Here that refers to $$L' = \{a^n b^m c^k \mid n > m > k\}$$ but I'm not sure what the language refers to. It could be $$L=\{a^n b^m c^k \mid n \le m \le k\}$$ or $$L'' = \{a,b,c\}^* \setminus L$$. In any case:
• $$L'$$ is not the complement of $$L$$. As (one of the many possible choices for a) witness, notice that $$b$$ belongs to neither $$L$$ nor $$L'$$.
• $$L'$$ is not the complement of $$L''$$. A witness is $$aab$$ since it belongs to both $$L'$$ and $$L''$$.