2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 20 '14 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.