# How the closure properties of the formal languages dictate decidability of their problem

Consider the following problem:

Is $L_1 * L_2$ is of $LType$?

where we know that both $L_1$ and $L_2$ are of type $LType$ and $LType$ is closed under $*$ operation.

Above, by $LType$, I mean any type of language that is known to belong to any type of Chomsky hierarchy. So it may be regular (Chomsky Type 3), CFL or DCFL (Chomsky Type 2) etc. Also by operation $*$, I mean any binary operation that results in another language, say intersection $\cap$, union $\cup$, difference $-$ etc.

Given all these pre-information of the type of languages and their closure under the specified operation, is the above problem decidable? For example

Does the problem:

"Given that $R_1$ and $R_2$ are regular, is $R_1 \cap R_2$ too a regular language?"

is decidable, especially when we know that regular languages are closed under intersection?

Also can we comment in the same manner about undecidability of operation when we know that the type of operand languages is not closed under that operation? That is

Does the problem

Is $L_1*L_2$ is of $LType$?

is undecidable?, especially when we know that $LType$ is not closed under the operation $*$ and that $L_1$ and $L_2$ are of type $LType$?

For example

Does the problem

Is $CFL_1\cap CFL_2$ is CFL?

is undecidable?, especially when we know that CFLs are not closed under intersection.

I feel both of above facts are correct/obvious/intuitive. But I am confused because no book on the theory of automata states it clearly.

If a family $\mathcal F$ of languages is closed under some operation, say intersection, then you are right that it is decidable whether the intersection of any two particular languages from $\mathcal F$ also belongs to $\mathcal F$. The answer is always Yes.
The converse, however, isn't true. Consider the family $\mathcal F_m$ of all regular languages which are accepted by some DFA having at most $m$ states, for some parameter $m$. When $m > 1$, this language family isn't closed under intersection, but given any two languages from $\mathcal F_m$ (in any reasonable encoding), it is decidable (depending on the encoding, efficiently) whether their intersection belongs to $\mathcal F_m$.
• If I am not interpreting it wrong, $\mathcal F_m=\mathcal R_1 \cup \mathcal R_2 \cup ...\cup \mathcal R_m$ and regular languages are closed under union. So, $\mathcal F_m$ should also be regular, thus $\mathcal F_m$ should also be closed under the intersection (as regular languages are closed under intersection). – anir123 Dec 24 '16 at 13:56
• Regarding $\mathcal{F}_m$, for $m > 1$ it is not closed under intersection. For example, $(aa)^*,(aaa)^* \in \mathcal{F}_3$ but $(aa)^* \cap (aaa)^* = (aaaaaa)^* \notin \mathcal{F}_3$. A more generic example is the language $L_{m,a}$ of all words in which the number of occurrences of the symbol $a$ is a multiple of $m$. Clearly $L_{m,a} \in \mathcal{F}_m$, but for $m>1$ and $a \neq b$, $L_{m,a} \cap L_{m,b} \notin \mathcal{F}_m$. A tight example over the unary alphabet is $a(a^{m-1})^*,(a^m)^* \in \mathcal{F}_m$, $a(a^{m-1})^* \cap (a^m)^* \notin \mathcal{F}_m$. – Yuval Filmus Dec 24 '16 at 20:16