patternModerate
What is complement of Context-free languages?
Viewed 0 times
whatfreelanguagescontextcomplement
Problem
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 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).
Solution
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?
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?
Context
StackExchange Computer Science Q#7144, answer score: 19
Revisions (0)
No revisions yet.