6
$\begingroup$

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!

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

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.