Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
    
A related question on MO. –  Kaveh Feb 23 '12 at 2:35
add comment

1 Answer

up vote 9 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|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
4  
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
add comment

Your Answer

 
discard

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.