# What is known about $CFL \cap coCFL$?

CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL.

Are there any nice characterizations or other basic facts about CFL $\cap$ co-CFL?

Two easy examples of the kind of fact I have in mind (but one would like more precise information):

1. DCFL $\subseteq$ CFL $\cap$ co-CFL.
2. pCFL $\subseteq$ CFL $\cap$ co-CFL, where pCFL is the class of CFLs that are permutation-closed. It's closed under complement by Parikh's theorem and the fact that semilinear sets are definable in Presburger arithmetic.

Another related question: given a CFL $L$, it's undecidable whether $L \in$ DCFL. Is the same true for pCFL?

• Related post: cstheory.stackexchange.com/q/4263/1800 Jan 25 '14 at 16:11
• Shane, I don't think pCFL is closed under complement. The complement of MIX, i.e., the language $\{ w \in \{ a,b,c \}^* \mid \#_a(w) \neq \#_b(w) \} \cup \{ w \in \{ a,b,c \}^* \mid \#_b(w) \neq \#_c(w) \}$, is context-free, but MIX isn't. Jan 26 '14 at 1:39
• Makoto: that seems like a counter-example. Here's what I had in mind as a "proof". Let $L \in$ pCFL. Then $w \in L$ iff $\#(w) \in W_L$ where $W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L \}$ and $\Sigma = \{ a_1 , \dots , a_n \}$. In particular, $w \notin L$ iff $\#(w) \notin W_L$, i.e. $w \in \bar{L}$ iff $\#(w) \in \mathbb{N}^n \setminus W_L$. This latter set is semilinear since they are closed under complement. The problem is there's no converse of Parikh's theorem, so $\mathbb{N}^n \setminus W_L$ need not be the Parikh image of a CFL. Is that right? Jan 26 '14 at 18:36
• @ShaneSteinert-Threlkeld: yes, the complement of a pCFL is still semi-linear, but not necessarily context-free. Could you edit your question to reflect this fact? Feb 2 '14 at 21:22

Recall that in this proof, one considers an instance $\langle \Sigma,\Delta,u,v\rangle$ of Post's correspondence problem, where $\Sigma$ and $\Delta$ are two disjoint alphabets, and $u$ and $v$ are two homomorphisms from $\Sigma^\ast$ to $\Delta^\ast$. Then $$L_u=\{a_1\cdots a_n(u(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$ and $$L_v=\{a_1\cdots a_n(v(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$—where $w^R$ denotes the reversal of word $w$—are two DCFLs s.t. $L_u\cap L_v=\emptyset$ iff the original PCP instance was negative. Letting $$L=\overline{L_u}\cup\overline{L_v}\;,$$one thus defines a CFL (since DCFLs are effectively closed under complement and CFLs under union), which is universal, i.e. equal to $(\Sigma\cup\Delta)^\ast$, iff the original PCP instance was negative.
Now, if $L$ is universal, i.e. if $L=(\Sigma\cup\Delta)^\ast$, then $L$ is closed under permutations. Conversely, if $L$ is not universal, i.e. if $L_u\cap L_v\neq\emptyset$, there is at least one word $x$ of form $x=w(u(w))^R=w(v(w))^R$ for some $w$ in $\Sigma^+$. Then $x$ does not belong to $L$, but it's easy to find a permutation of $x$ that belongs to $L$: for instance, permute the last letter of $w$ (which is in $\Sigma$) with the first of $(u(w))^R$ (which is in $\Delta$) to obtain a word in $\Sigma^\ast\Delta\Sigma\Delta^\ast\subseteq L$.
Hence $L$ is closed under permutation iff it is universal iff the original PCP instance was negative.