1
$\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.

Improve this question
$\endgroup$
1
  • 1
    $\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, 2019 at 17:34

3 Answers 3

Reset to default
5
$\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).

Improve this answer
$\endgroup$
2
$\begingroup$

The problem with the Chomsky Hierarchy is that it says nothing at all about the class of recursive languages. Honestly, that's the most important class of all, since it corresponds to the things that computers can do, at least in principle.

The key point here is that every context-free language is recursive: you can simulate a PDA (even a nondeterministic one) on a computer (formally, a Turing machine). If you can do something on a computer, you can also do that thing and then negate the answer, so recursive languages are closed under complementation. So the complement of a CFL is still some kind of recursive language.

You're right that the complement of an RE language isn't necessarily RE. But a CFL isn't just any RE language: it's a very, very special kind of RE language and its complement is still RE and, furthermore, recursive.

Improve this answer
$\endgroup$
0
$\begingroup$

Putting similar arguments as above answers in a slightly different way :

All context free languages can be decidable by a Halting Turing Machine. (Those would be a piece of cake for the Machine). Now even if we complement such a language, Halting TM can still decide whether it is accepted or not.

The Complement of CFL still lies under the power of Halting TM, hence cannot go beyond the RE boundary in Chomsky Hierarchy.

Improve this answer
$\endgroup$

Your Answer

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

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