Proof that a certain language is Turing Decidable

1.6k Views Asked by At

$$L_1 = \{\langle R,S \rangle \mid \text{$R$ and $S$ are regular expressions and }L(R) \subseteq L(S)\}$$

$$L_2 = \{\langle M\rangle\mid \text{$M$ is a DFA that accepts $w^r$ whenever it accepts $w$} \}$$

For $L_1$ to prove that it is a decidable language, all that I need to show is that $L(R) \cap L(S) = L(R)$, and since regular expressions are finite automatons basically, I already have a proven decider that decides whether two DFAs accept the same, so this can be shown. Is this a sufficient proof if I use that previous decider as a kind of "subroutine"?

Also now for $L_2$ I have no idea where to start with this, a hint for this one would be nice.

1

There are 1 best solutions below

2
On BEST ANSWER

Yes it should be fine if you use the previous proof/construction as a "subroutine".

For the second question, let's use ${rev}$ rather than $r$ as a superscript to denote the reverse operation on strings and languages. Note that the definition of $L_2$ amounts to $ \langle M \rangle\in L_2 \iff L(M)^{rev}\subseteq L(M). $

But in fact equality holds, because every string $w$ is the reverse of some string $v$: $w=v^{rev}$ (and then, $v=w^{rev}$): $$\langle M \rangle\in L_2 \iff L(M)=L(M)^{rev}.\tag{*} $$

You have an existing subroutine which takes two (encodings of) DFAs and decides whether they accept the same language.

Here's another subroutine: we can make a Turing machine which, given (an encoding of) a DFA $M$, constructs (the encoding of) another DFA $M_{\bf r}$ which accepts the reverse of the language $L(M)$ accepted by $M$. In other words, $L(M_{\bf r}) = L(M)^{rev}$.

A TM deciding $L_2$ can be described as follows:

  • On input $\langle M \rangle$, for $M$ a DFA, use the other subroutine above to obtain a DFA $M_{\bf r}$ which accepts $L(M)^{rev} = L(M_{\bf r})$.

  • By (*) and the nature of $M_{\bf r}$, $$\langle M \rangle\in L_2 \iff L(M) = L(M_{\bf r}).$$ So to decide membership in $L_2$, return what your existing subroutine returns when called with arguments $\langle M\rangle,\langle M_{\bf r}\rangle$.