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?
context-free-grammar
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?
Best Answer
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.