# Why is universality of CFG undecidable?

Let $$\text{ALL-CFG} = \{\left \mid G\text{ is a CFG and } L(G) = \Sigma^*\}$$.

I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not appropriate.

Let $$C$$ be a CFG. Then $$\bar{C}$$ is a CFG by closure under complement. Since the emptiness of CFG is decidable, we can use it to decide whether $$\bar{C}$$ is empty and therefore whether $$C$$ is universal.

This problem has confused me a lot. Really appreciate your help. Thanks!!!

The context-free languages are not closed under complement. For example, $$\overline{\{a^nb^nc^n : n \geq 0\}}$$ is context-free, but its complement isn't.
• @いいな, Moreover, even if it were closed under complement, it wouldn't mean that you could find $\bar C$ for a given $C$. Also, since this answer answers your question, please consider accepting it. – Dmitry Oct 23 at 14:32