# Both a language and its complement are not context free

Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?

Yes, there is. Consider the language $L = \{a^p \mid p \text{ is prime}\}$ which is not contextfree, neither is its complement. Both statements are very easy to check via Pumping-Lemma.

• Could you give me a hint to prove that the complement of L is not context free? – Samuel Bismuth Jul 2 '18 at 13:31
• Since $L$ is unary, it is context-free iff it is regular iff its complement is regular. – Yuval Filmus Jul 3 '18 at 7:08