# Determining whether the language of a DFA is closed under reversal

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.

Answer:

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?

• What does the definition of $S$ tell you about $M$? What does it tell you about $L(M)$? – D.W. Jun 1 '18 at 6:39
• OK ... is $L(M^R) = L(M)^R$? @D.W. – Intuition Jun 1 '18 at 6:55
• 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. – Rick Decker Jun 1 '18 at 14:11

## 1 Answer

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