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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.