# Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n$ for some natural number n $\}$ context free?

I was wondering if this language is context-free:

$L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n$ for some natural number n $\}$

I know that this language is not regular because it fails the pumping lemma for regular languages but that does not necessarily mean it is not context-free. I'm not sure whether to use the pumping lemma for context-free languages to show that this is not context free or to provide context-free grammar to show that it is context free.

I've tried creating a context-free grammar to generate this language but ran into trouble which makes me believe that this language is not context-free, but I am still unsure.

If someone could point me in the right direction that would be greatly appreciated.

## 1 Answer

Suppose $L$ was context-free. Then $L \cap 0^*$ were also context-free. Since $L \cap 0^*$ is a unary language (a language over a unary alphabet, i.e., an alphabet of size $1$), Parikh's theorem states that it is context-free iff it is regular. As you mention, $L \cap 0^*$ isn't regular, and so $L$ can't be context-free.

• More generally, the set of lengths of words in a context-free language is eventually periodic. This is proved in much the same way, and is perhaps also sometimes referred to as Parikh's theorem. – Yuval Filmus Mar 20 '14 at 18:07