0
$\begingroup$

I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I cannot wrap my head around this argument.

What I know about a CFL(say L) is that the complement of this CFL(say L') need not necessarily be a CFL. This creates fair bit of skepticism about nature of such a complement in my head and makes me feel that there is a possibility this complement L' could fly off anywhere in Chomsky Hierarchy as long as it is not a CFL. Why would it be restricted to REC?

In my head, I find myself coming up with arguments like following: "Every CFL is in RE and complement of an RE need not necessarily be RE and thus need not necessarily be REC! Thus there could be CFLs whose complements are not in REC. " or "Complement of a CFL may fall under RE and there are RE languages which are NOT REC. Thus there is a possibility that a certain complement may not be in REC"

Thread like : What is complement of Context-free languages? did not answer my question.

$\endgroup$
  • $\begingroup$ What problem do you have with the argument outlined in your first paragraph? Nothing in your second paragraph contradicts it. $\endgroup$ – David Richerby Jan 10 at 17:34
0
$\begingroup$

We have $\text{CFL} \subset \text{R} \subset \text{RE}$. As you have mentioned, $\text{RE}$ is not closed under complementation, but $\text{R}$ is. Hence, the complement of a CFL is also in $\text{R}$ (though not necessarily another CFL).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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