2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}'$.

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