Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I can say that complement of CFL is included in P(right?). There is still a question whether complement of CFL is proper subset of P or the whole P. I would appreciate any ideas on how to show that complement of CFL is the whole P(if that's the case of course).

share|cite|improve this question
I was going to post this as an answer, but it doesn't answer your whole question: the complement of any CFL is R (recursive), since recursive languages are closed under complement and all CFLs are R. – Eric Dec 4 '12 at 2:48
up vote 14 down vote accepted

One can understand your question in two ways, according to the definition of "the complement of CFL".

case A: Complement of CFL is the class of all the languages that are not in CFL. Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$ In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc. But maybe that's not what you meant.

case B: Define the complement-CFL class as $$co{CFL} = \{ \bar{L} \mid L \in CFL\},$$ in words, the set of all languages $L$, such that $L$'s complement is context free.

In that case, what you wrote makes sense: $CFL \subsetneq P$ (by the CYK algorithm), and also $co{CFL} \subseteq P$ (run the same algorithm, output the opposite answer), and since $CFL \neq co{CFL}$, then it should be immediate that $co{CFL}\subsetneq P$, right?

share|cite|improve this answer
definition of CFK as far as I understand it: language L is in coCFK if and only if complement of L is in CFK. By complement of L I mean all possible strings except strings in L. The problem I think is that complement cannot be defined as "run the same algorithm and reverse the answer" For example: L=(x^i y^i z^i) is not CFL, but I don't know what algorithm I can run to get the (negative) answer. – user432 Dec 4 '12 at 4:08
so you are referring to case B. Note that the complement of a CFL $L$ might not be CFL, but it doesn't mean that the CYK algorithm doesn't work on it the same.. I mean, we run the CYK on $\overline L$, which is CFL, and get an answer for every $x$ whether or not it is in $\overline L$. the opposite of that is the answer to the question whether or not that $x$ is in $L$, even though $L$ might be non-CFL. – Ran G. Dec 4 '12 at 4:14
@user432 $\text{coCFL} \neq \overline{\text{CFL}}$! – Raphael Dec 4 '12 at 16:51
@RanG is your notation standard here? I would expect $coCFL = \{ L : \bar{L} \in CFL\}$ and $\overline{CFL} = $ the class of languages $L$ such that $L \not \in CFL$. – usul Dec 4 '12 at 22:09
Actually, let me change the notation according to your suggestion, it'll make more sense. – Ran G. Dec 5 '12 at 2:19

A robust class that contains both CFL and coCFL is LOGCFL, which contains all languages logspace-reducible to a context-free language. This class is intermediate between NL and AC1, and has some natural complete problems. It can also be defined in terms of restricted AC1 circuits. LOGCFL is closed under complement (this is an extension of the argument used to show that NL=coNL).

share|cite|improve this answer

Complement of CFL could possibly be CFL but not necessarily is. Complement of CFL is both recursive (R) and recursively enumerable (RE). Why? All CFLs are both R and RE. R languages are closed under complement (but RE are not). In that context, complement of CFL is R which is inherently RE.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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