# What is complement of Context-free languages?

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).

-
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

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?

-
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