6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Related post: cstheory.stackexchange.com/q/4263/1800 $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 25 '14 at 16:11
  • 3
    $\begingroup$ 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. $\endgroup$ – Makoto Kanazawa Jan 26 '14 at 1:39
  • $\begingroup$ 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? $\endgroup$ – Shane Steinert-Threlkeld Jan 26 '14 at 18:36
  • $\begingroup$ @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? $\endgroup$ – Sylvain Feb 2 '14 at 21:22
6
$\begingroup$

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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