World's most popular travel blog for travel bloggers.

# Decidability of fullness of intersection of a CSL with a regular language

, ,
Problem Detail:

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.

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).