Which properties of context sensitive languages are decidable? There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable?


$L_1 = \emptyset$
$L_1 = \Sigma^*$
$L_1 \cap L_2 = \emptyset$
$\overline{L_1}$ is also a context-sensitive language.
$L_1 = L_2$
When considering questions like this you need to make explicit what representation you are using for your languages. In the following I will assume you are using context-sensitive grammars as input for your problems.

1) is a well known undecidable property of context-sensitive grammars.

2) as well as 3) and 5) are obviously undecidable as they are undecidable for a proper subclass of context-sensitive grammars, namely the context-free grammars.

4) is trivially decidable as the answer is always yes because the complement of a context-sensitive language is itself context-sensitive.