The question and its answer is given below:

Let $S = \{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.


For any language $A$, let $A^{\mathcal{R}} = \{w^{\mathcal{R}} \mid w \in A\}$. If $\langle M \rangle \in S$, then $L(M) = L(M)^{\mathcal{R}}$. The following $\textsf{TM}$ $T$ decides $S$.

$T = $ “On input $\langle M \rangle$, where $M$ is a $\textsf{DFA}$:

  1. Construct $\textsf{DFA}$ $N$ that recognizes $L(M)^{\mathcal{R}}$.
  2. Run $\textsf{TM}$ $F$ from Theorem 4.5 on $\langle M,N \rangle$, where $F$ is the Turing machine deciding $EQ_{\textsf{DFA}}$.
  3. If $F$ accepts, accept. If $F$ rejects, reject.”

But I do not understand in the first line of the answer, in the second statement why does it say that $L(M) = L(M)^{\mathcal{R}}$, could anyone explain this for me please?

  • 1
    $\begingroup$ What does the definition of $S$ tell you about $M$? What does it tell you about $L(M)$? $\endgroup$
    – D.W.
    Commented Jun 1, 2018 at 6:39
  • $\begingroup$ OK ... is $L(M^R) = L(M)^R$? @D.W. $\endgroup$
    – Intuition
    Commented Jun 1, 2018 at 6:55
  • 1
    $\begingroup$ Not at all, if you mean $\langle M\rangle^R$. That reverses the description of $M$, so likely wouldn't even be the description of any DFA. $\endgroup$ Commented Jun 1, 2018 at 14:11

1 Answer 1


For a language $L$, we define the reverse language $L^{\mathcal{R}}$ by $$ L^{\mathcal{R}} = \{ x^{\mathcal{R}} : x \in L \}. $$ In words, $L^{\mathcal{R}}$ is obtained from $L$ by reversing all words.

It follows that $L = L^{\mathcal{R}}$ if and only if, for each word $x$, we have $x \in L \Leftrightarrow x^{\mathcal{R}} \in L$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.