<p>About the last question, the usual undecidability proof for universality could be adapted.</p>

<p>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&gt;0\wedge\forall 0&lt;i\leq n.a_i\in\Sigma\}$$ and $$L_v=\{a_1\cdots a_n(v(a_1\cdots a_n))^R\mid n&gt;0\wedge\forall 0&lt;i\leq n.a_i\in\Sigma\}$$&mdash;where $w^R$ denotes the reversal of word $w$&mdash;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.</p>

<p>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$.</p>

<p>Hence $L$ is closed under permutation iff it is universal iff the original PCP instance was negative.</p>

CC BY-SA 3.0
2014-01-25T15:00:50.573Z
2014-01-25T15:00:50.573Z
Sylvain
<p>CFL is the class of context-free languages; co-CFL the languages whose complements are context-free.  So CFL $\neq$ co-CFL.</p>

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

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

<ol>
<li>DCFL $\subseteq$ CFL $\cap$ co-CFL.</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2014-01-25T16:11:33.690Z
Related post: http://cstheory.stackexchange.com/q/4263/1800
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-01-26T01:39:18.213Z
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.
Makoto Kanazawa
CC BY-SA 3.0
2014-01-26T18:36:42.430Z
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?
Shane Steinert-Threlkeld
CC BY-SA 3.0
2014-02-02T21:22:02.053Z
@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?
Sylvain
<context-free><decidability>
What is known about $CFL \cap coCFL$?
Shane Steinert-Threlkeld
# What is known about $CFL \cap coCFL$?

(Asked by: username_0 on 2014-01-24)

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?

**Tags:** context-free, decidability
> **Comments:**
> **username_1**: Related post: http://cstheory.stackexchange.com/q/4263/1800  
> **username_2**: 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.  
> **username_0**: 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?  
> **username_3**: @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?  

---

## 1 answers

### Answer by username_3 on 2014-01-25. Score: 6 | Accepted answer

About the last question, the usual undecidability proof for universality could be adapted.

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 00\wedge\forall 0

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.


---

