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

CC BY-SA 2.5
2011-01-11T22:14:08.883Z
Yep--you're absolutely right. Sorry about that! Let me change the question to reflect this.
alpoge
CC BY-SA 2.5
2011-01-12T06:25:00.710Z
isn't the question answered at this point ?
Suresh Venkat
CC BY-SA 2.5
2011-01-12T18:39:28.223Z
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
CC BY-SA 2.5
2011-01-11T21:51:23.537Z
2011-01-11T21:51:23.537Z
Dominik D. Freydenberger
<p>Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? <del>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.</del> 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.</p>

CC BY-SA 3.0
2012-02-23T02:35:36.413Z
[A related question on MO](http://mathoverflow.net/questions/89142).
Kaveh
<fl.formal-languages><automata-theory><context-free>
The class CFL\cap co-CFL
alpoge
# The class CFL\cap co-CFL

(Asked by: username_0 on 2011-01-11)

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.

**Tags:** fl.formal-languages, automata-theory, context-free

> **Comments:**
> **username_1**: [A related question on MO](http://mathoverflow.net/questions/89142).  

---

## 1 answers

### Answer by username_2 on 2011-01-11. Score: 12 | Accepted answer

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

> **Comments:**
> **username_0**: Yep--you're absolutely right. Sorry about that! Let me change the question to reflect this.  
> **username_3**: isn't the question answered at this point ?  
> **username_0**: 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!  

---

