I'm working on a proof for following question

$L=\{(R,S)\mid \text{R,S are regular expressions and } L(R)\subset L(S)\}$. Show that this language is/isn't decidable.

A language is decidable iff we have a Turing machine that halts for all input strings. If $L$ is regular, we can construct a DFA and therefore a Turing machine. Now we just have to show that this DFA/TM accepts/declines every input.

At least that's what I was told. But isn't it sufficient to show that $L$ is regular? Since reg. languages have a DFA and im pretty sure a DFA is decidable (because it can be converted to a TM and is finite)?

Since $L(R)\subset L(S) \Rightarrow L(R)\cap L(S) = L(R)$ we get that $L=L(R) \Rightarrow L$ regular?


Your Answer

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

Browse other questions tagged or ask your own question.