0
$\begingroup$

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable?

  1. $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$
  2. $\Sigma^* \cap L_\text{csl} \stackrel{?}{=} L_r$
  3. $L_r \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$
  4. $\Sigma^* \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$

I understand that (1) implies the others. I am also looking for any "near variants" that might be decidable.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

It is well-known that universality of context-free language is undecidable, making all your items undecidable already for context-free languages, so a fortiori for context sensitive languages (the particular case $L_r=\Sigma^*$ is already undecidable in all items).

Improve this answer
$\endgroup$

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.