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.


1 Answer 1


For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.

  • $\begingroup$ Yep--you're absolutely right. Sorry about that! Let me change the question to reflect this. $\endgroup$
    – alpoge
    Commented Jan 11, 2011 at 22:14
  • 4
    $\begingroup$ isn't the question answered at this point ? $\endgroup$ Commented 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$
    – alpoge
    Commented Jan 12, 2011 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.