Question

Let S = {<M> | M is a DFA that accepts wR whenever it accepts w}. Show that S is decidable. Let S = {<M> | M is a DFA that accepts wR whenever it accepts w}. Show that S is decidable.

Answer 1

To shown "S" is decidable, Construct Decider "D" for S as follows :-

Let (T) be the Turning Machine(TM) that makes a decision Equivalent to DFA (denoted as ):

D = On Input <M> ,

1. Construct a Non-deterministic Finite Automaton(NFA) M′ such that L(M′) = { | W ∈ L(M) }
2. Convert M' into an equal Deterministic Finite Automaton(DFA) M''
3. Use T to compare/evaluate L(M'') andL(M)
4. If L(M'') = L(M), accept it. else, reject it.

In the above Turning Machine (TM),

Step 1 may be achieved via way of means of converting M into M' in finite steps.

The concept is to

(i) opposite the directions of all transition arrows in M

(ii) create a new state q' in M', and connects q' to every unique very last states of M with ε-transitions, and

(iii) make the unique begin state of M final state of M'.

It is simple to check that L(M') = | W ∈ L(M'') > w∈ L(M).

Also, both Step two and Step three may be achieved in finite steps

D runs in finite steps and is for this reason a decider