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$

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.

| cite | improve this answer | |
  • $\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 '14 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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