Question

(10) Let L = { <D> | D is a DFA that accepts s^R whenever it accepts s } . Show that L is Turing-decidable.

Answer 1

Here i am providing the answer. Hope it helps. Please give me a like, it helps me a lot. If you have any doubts comment me. i will explain you,

Here is the question, Let L= {<D>〉 | D is a DFA that accepts sR whenever it accepts s}. Now, we have to
sshow that L is decidable.
(We know that sR is the reversal of s,
Answer: If D is a DFA, let DR be the DFA that accepts the reverse of all the strings that D accepts. Such a
DFA can be constructed by reverting each of the transitions in the DFA and by switching the initial and
the Ŝnal states. Notice that <D> ∈ L ⇔ L(D) = L(DR) ⇔ D, DR are equivalent. The membership of <D> can
be checked by using the equivalence checking algorithm of DFA.
WE can take another approach like, to show S is decidable, we construct a decider M for S as follows (Let
C be a TM
that decides EQDFA):
M = “On input <D>,
1. Construct an NFA D' such that L(D' ) = {w R | w ∈ L(D)}
2. Convert D' into an equivalent DFA D00
3. Use C to compare L(D') and L(D)
4. If L(D'') = L(D), accept. Else, reject.
In the above TM, Step 1 can be done by converting D into D' in finite steps. The idea is to (i) reverse the
directions of all transition arrows in D, (ii) create a new state q' in D', and connects q' to each original final
states of D with ε-transitions, and (iii) make the original start state of D a Ŝnal state of D'. It is easy to
check that L(D') = {w R | w ∈ L(D)}. Also, both Step 2 and Step 3 can be done in Ŝnite steps.
So, D runs in finite steps and is thus a decider.
Thank you, please like.