1
$\begingroup$

Let $\text{ALL-CFG} = \{\left<G\right> \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!!!

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for my silly question. Thank you very much! $\endgroup$ – Gary hui Oct 23 at 13:05
  • 1
    $\begingroup$ @いいな, 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. $\endgroup$ – Dmitry Oct 23 at 14:32
  • $\begingroup$ @Dmitry, You are right. I mistook CFL for DCFL just now. Thank you for reminding me. $\endgroup$ – Gary hui Oct 23 at 14:52

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.