World's most popular travel blog for travel bloggers.

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

, , No Comments
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.

Asked By : vzn
Answered By : Denis

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

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback