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).
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ 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. $\endgroup$– CatDec 4, 2012 at 2:48
-
$\begingroup$ CFL not being closed under complementation does not mean that a 'L' being in CFL means it's complement is not in CFL. It just means that there exists a 'L' in CFL such that it's complement is not in CFL $\endgroup$– SHREYANSHU THAKURMar 13, 2019 at 20:05
-
$\begingroup$ @Eric The asker already knows that the complement of any CFL is recursive. They've made the much stronger statement that the complement of any CFL is in P. $\endgroup$– David RicherbyMar 14, 2019 at 10:12
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
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?
-
$\begingroup$ 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. $\endgroup$– user432Dec 4, 2012 at 4:08
-
1$\begingroup$ 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. $\endgroup$– Ran G.Dec 4, 2012 at 4:14
-
1$\begingroup$ @user432 $\text{coCFL} \neq \overline{\text{CFL}}$! $\endgroup$– Raphael ♦Dec 4, 2012 at 16:51
-
1$\begingroup$ @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$. $\endgroup$– usulDec 4, 2012 at 22:09
-
1$\begingroup$ Actually, let me change the notation according to your suggestion, it'll make more sense. $\endgroup$– Ran G.Dec 5, 2012 at 2:19
$\begingroup$
$\endgroup$
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).
answered Jan 23, 2016 at 17:22
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ The asker has already said that they know that the complement of any CFP is in P. That's a much stronger statement than that it's recursive or RE. It's like the asker has mentioned a person who can't walk and you've responded with a proof that he can't run at the speed of sound. $\endgroup$ Mar 14, 2019 at 10:15