2
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

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

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