Take the 2-minute tour ×
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.

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

1 Answer 1

up vote 11 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|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
1  
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
1  
@user432 $\text{coCFL} \neq \overline{\text{CFL}}$! –  Raphael Dec 4 '12 at 16:51
1  
@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
1  
Actually, let me change the notation according to your suggestion, it'll make more sense. –  Ran G. Dec 5 '12 at 2:19

Your Answer

 
discard

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.