CFL not closed under intersection while Turing Decidable are

Question

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not.

Does not Turing Decidable engulf all CFLs?

Answer 1

Yes, all CFLs are Turing-decidable but a subset of an intersection-closed class of languages is not necessarily intersection-closed. CFLs and Turing-decidable languages are just one example of this. In fact, this is not an unusual situation:

Theorem. Let $\mathcal{L}$ be an intersection-closed class of languages containing languages $L_1$ and $L_2$ such that $L_1\cap L_2\neq L_1$ and $L_1\cap L_2\neq L_2$. There is a class $\mathcal{L}'\subset\mathcal{L}$ that is not intersection-closed.

Proof. Just take $\mathcal{L}' = \mathcal{L}\setminus \{L_1\cap L_2\}$. $\mathcal{L}'$ contains $L_1$ and $L_2$ but does not contain their intersection, by construction. $\quad\Box$

The simplest possible example is the class of languages $C = \big\{\emptyset, \{a\}, \{b\}\big\}$. This is closed under intersection but the subclass $C' = \big\{\{a\}, \{b\}\big\}$ is not, since $\{a\}\cap\{b\}=\emptyset\notin C'$.

Conversely, a superset of an intersection-closed class of languages is not necessarily intersection-closed. Here's an example. Let $\mathcal{R}$ be the class of all Turing-decidable languages. Fix some coding of Turing machines and let $H$ be the language of codings of all Turing machines that halt when given empty input. It is well known that $H$ is undecidable, so $H\notin\mathcal{R}$. I claim that $\mathcal{R}' = \mathcal{R}\cup\{H\}$ is not closed under intersections. To see this, let $h$ be any string in $H$ (for example, $h$ could be the coding of some program that just loops for all input). The language $L = \{w\mid w\neq h\}$ is clearly in $\mathcal{R}$. $L\cap H\neq H$, since $h\in H$ but $h\notin L\cap H$. And $L\cap H\notin\mathcal{R}$ since the language of all Turing machines except for $h$ that halt when given empty input is also undecidable. Therefore, $\mathcal{R}'$ is not closed under intersections, since $L\in\mathcal{R}'$, $H\in\mathcal{R}'$ but $L\cap H\notin\mathcal{R}'$.