What is complement of Context-free languages?

Question

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

Answer 1

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?

Answer 2

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

Answer 3

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.