3
$\begingroup$

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$
$\endgroup$
1

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ to me these answers while quite helpful are not so "well known" or "obvious" because there seem to be no simple lists/surveys of decidable vs undecidable language problems & they are not always mentioned in automata/computability books that do cover related areas... eg these do not seem to be listed on wikipedia nor do there seem to be other "reference questions" for it on this site. freq have to look hard online to find refs to undecidable language properties.... seems the (un)decidable boundaries can be subtle/nuanced at times... $\endgroup$
    – vzn
    Jun 8, 2014 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.