Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment is obvious.)? I hope I'm not being stupid here--don't laugh at me too much if this is totally trivial. I ask this because I'm trying to pin down a commutative closure of a regular language over a binary alphabet, and it's clear that it lies inside this set, via a result showing that slip-languages over an alphabet of size two have context-free commutative closure.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ A related question on MO. $\endgroup$– KavehFeb 23, 2012 at 2:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.
answered Jan 11, 2011 at 21:51
-
$\begingroup$ Yep--you're absolutely right. Sorry about that! Let me change the question to reflect this. $\endgroup$– alpogeJan 11, 2011 at 22:14
-
4$\begingroup$ isn't the question answered at this point ? $\endgroup$ Jan 12, 2011 at 6:25
-
$\begingroup$ Indeed--I was hoping for some characterization of the class, but since I really originally asked whether it was DCFL, it's only fair to accept! $\endgroup$– alpogeJan 12, 2011 at 18:39