Question Detail: 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).
Asked By : user432
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7144
Answered By : Ran G.
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 Lnotin 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?
