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!!!

1 Answer

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.

• Sorry for my silly question. Thank you very much! Commented Oct 23, 2020 at 13:05
• @いいな, 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.
– user114966
Commented Oct 23, 2020 at 14:32
• @Dmitry, You are right. I mistook CFL for DCFL just now. Thank you for reminding me. Commented Oct 23, 2020 at 14:52