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

CC BY-SA 4.0
2019-01-12T13:42:34.610Z
2019-01-12T21:56:13.617Z
2019-01-12T21:56:13.617Z
Lance Fortnow
<p>Let <span class="math-container">$L$</span> be a context-free language, <span class="math-container">$\bar L$</span> be its complement and <span class="math-container">$\bar L_n$</span> be the length <span class="math-container">$n$</span> words in <span class="math-container">$\bar L_n$</span>.</p>

<blockquote>
  <p>What is known about <span class="math-container">$|\bar L_n|$</span>?</p>
</blockquote>

<p>Note that <a href="https://cstheory.stackexchange.com/questions/41878/number-of-words-of-length-n-in-a-context-free-language?rq=1">it is known</a> that <span class="math-container">$|L_n|$</span> is either polynomial (if <span class="math-container">$L$</span> is bounded<span class="math-container">$~$</span>), or grows exponentially.
I wonder if anything similar might be true about <span class="math-container">$|\bar L_n|$</span>.
Warning, <span class="math-container">$L$</span> is allowed to be ambiguous!</p>

<fl.formal-languages><context-free>
Size of complement of context-free language
domotorp
# Size of complement of context-free language

(Asked by: username_0 on 2019-01-12)

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](https://cstheory.stackexchange.com/questions/41878/number-of-words-of-length-n-in-a-context-free-language?rq=1) 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!

**Tags:** fl.formal-languages, context-free

---

## 1 answers

### Answer by username_1 on 2019-01-12. Score: 11 | Accepted answer

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.


---

