Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
A related question on MO. – Kaveh Feb 23 '12 at 2:35
up vote 10 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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