Example of a non context-free language whose complement isn't context-free as well

Question

The language $L=\{a^{2^n} \mid n \geq 0\}$ isn't context free (easily proved using the pumping lemma).

But what about its complement? It seems to me that it's unlikely for it to be context free, but how would one show it?

Answer 1

Actually I do not know how ro apply pumping arguments to the complement $\overline L$.

However, you consider a language over a single letter alphabet $\{a\}$. It is known that the single letter context-free languages are in fact regular (Parikh's Theorem). We also know that regular languages are closed under complement. Thus, for a language $L$, $L$ and $\overline L$ are either both regular, or both non-regular. But as here $L \subseteq \{a\}^*$, regularity and context-freeness coincide, so $L$ and $\overline L$ are either both context-free, or both non-context-free.