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.


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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