[Solved]: Which properties of context sensitive languages are decidable?

Problem Detail: 

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

1. $L_1 = \emptyset$
2. $L_1 = \Sigma^*$
3. $L_1 \cap L_2 = \emptyset$
4. $\overline{L_1}$ is also a context-sensitive language.
5. $L_1 = L_2$

Asked By : Bharat Kul Ratan

Answered By : Sam Jones

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4992