Problem Detail: 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$
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
