Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$.

What is known about $|\bar L_n|$?

Note that it is known that $|L_n|$ is either polynomial (if $L$ is bounded$~$), or grows exponentially. I wonder if anything similar might be true about $|\bar L_n|$. Warning, $L$ is allowed to be ambiguous!


From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations of an accepting nondeterministic TM, is the complement of a context-free language. So $|\overline{L}_n|$ can basically be any computable function less than exponential.

  • 2
    $\begingroup$ Thanks. I fixed it. $\endgroup$ – Lance Fortnow Jan 12 at 21:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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