# Closure property and undecidability

I know that if a language class is closed under operation X then the problem is decidable.

for eg: "Intersection of two CSL is CSL"? this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation. for eg: problem: Is intersection of two CFL is CFL or not?

as CFL/DCFL is not closed under intersection. then is this true saying that not following closure opertion implies Undecidable problem?

My approach:This problem is same as saying that "A given CSL is CFL or not?" because intersection of two CFL's is CSL for sure. as every CSL is RE then can we also say this problem as "A RE is CFL or not"? if my last statement is true then by using rice theorem this problem must be undecidable and even not RE.

how to approach these type of question when a language is not closed under the given operation?

• Which problem is decidable or not? Make it clear. Also, what do you mean by language is closed under operation X? Perhaps you meant language class? – Yuval Filmus Jul 31 '17 at 20:52

However, it is in fact undecidable to decide whether the intersection of two context-free languages (say given as context-free grammars) is context-free, essentially since you can encode the computation of a Turing machine as the intersection of two context-free languages. See Theorem 1 in a writeup of Hendrik Jan (a bit of work is required to get this particular result from the theorem: construct grammars for $L(G_1) \flat \{a^nb^n c^m\}$ and $L(G_2) \flat \{a^nb^mc^m\}$; the intersection of these context-free languages is non-context-free iff $L(G_1) \cap L(G_2)$ is non-empty).
I don't think closure property implies decidability. Consider r.e. languages and intersection. R.e. languages are closed under intersection, e.g., if $L_1$ and $L_2$ are r.e. languages then $L_1 \cap L_2$ is also r.e. but may be undecidable.
On the other hands, CFLs are not closed under intersection. However, a language which is intersection of two CFLs is not CF but may be decidable. For example $L_1=\{a^ib^ia^j |i,j \geq 1 \}$, $L_2=\{a^ib^ja^j |i,j \geq 1 \}$ are both CF, however $L_1 \cap L_2 = \{ a^ib^ic^i | i,j \geq 1\}$ is not CF, but it is still decidable.