# A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rational for it is clear to me. I just can't think of one trivial, easy to prove example. For instance, the complement of a^nb^nc^n is CF, and for more complicated examples I'm often not even sure what the complement is.

In one of your comments you remark that for unary languages this is more intuitive for you. We can simply adapt a unary language to suit your goals by adding the other letters to the alphabet.

Consider $$L_1 = \{a^{n^2} \mid n\ge 1 \}$$ to be a non-regular language over $$\{a\}$$ $$-$$ in fact we can consider any non-regular unary language, using the primes for example. By the closure under complement also $$L_1^c = \{a\}^* \setminus L_1$$ is nonregular. Also for unary languages regular and contextfree are equivalent, so both $$L_1$$ and $$L_1^c$$ are not contextfree.

Note that $$L_1$$ can be considered a language over $$\{a,b,c\}$$ too. We can be a little over-formal and write $$L = \{w\in \{a,b,c\}^* \mid w=a^{n^2} \text{ for some } n\ge 1 \}$$. Clearly $$L$$ is non-contextfree, because that is $$L_1$$.

Also the complement over the full alphabet $$\{a,b,c\}$$ is not context-free: we merely add the regular language of words containing either $$b$$ or $$c$$. $$L^c = \{a,b,c\}^* \setminus L = L_1^c \cup \{a,b,c\}^*\cdot\{b,c\}\cdot\{a,b,c\}^*$$. This (again) follows from closure properties. Assume $$L^c$$ is contextfree, then so would be $$L_1 = L\cap \{a\}^*$$.

Let $$L = \{a^n b^n c^n \mid n \ge 0\}$$. Define $$L' = \{aw \mid w \in L \} \cup \{ bw \mid w \in \overline{L}\} \cup \{\varepsilon\}$$.

Notice that $$L'$$ is not context free by an application of the pumping lemma on $$a^{p+1}b^pc^p$$ for sufficiently large $$p$$.

The complement of $$L'$$ is $$\overline{L}' = \{xw \mid x\in \{b,c\} \mbox{ or } w\not\in L \} \cap \{xw \mid x\in \{a,c\} \mbox{ or } w\in L \}.$$

Consider some word $$bw$$, where $$w \in \Sigma^*$$. Notice that $$bw$$ always belongs to $$\{xw \mid x\in \{b,c\} \mbox{ or } w\not\in L \}$$, therefore it belongs to $$\overline{L}'$$ if and only if it also belongs to $$\{xw \mid x\in \{a,c\} \mbox{ or } w\in L \}$$. This is only true if $$w \in L$$.

We can once again use the pumping lemma on $$ba^pb^pc^p$$ to show that $$\overline{L}'$$ is not context free.

Suppose $$\ell=\{(abc)^p\mid p\text{ is prime}\}$$

According to Parikh's theorem, both $$\ell$$ and its complement $$\ell^c$$ aren't Context-free.

• Thanks. Wow, I was aware of this prime example but for some reason remembered reading somewhere it's only valid if the language is unary. This theorem is actually more advanced than what I'm currently studying, so I'm still trying to understand why the complement is also not CF. For an unary language it's more intuitive for me. Jul 26 at 13:30