Question

Let Show that S is decidable.

Short answer

S is decidable.

Step-by-step solution

Explain DFA

DFA refers to deterministic finite automata. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time.

Show that S is decidable.

Consider the Turing Machine T, On input M, that is DFA. Construct the DFA N , which accepts the reverse of a string accepted by M. Submit it to the decider for $E{Q}_{DFA}$. If it accepts, accept and if it rejects, reject.

Construct DFA M^R that reverses all the transitions as follows,

1. The new accepting state is the initial state of the previous turing machine.
2. New initial state is created with $\epsilon$- transition.
3. Construct DFA from the NFA.

A DFA constructed accepts only the particular languages. T decides M depends on the recognition of the strings.

Hence, the output of M is decidable by S.

Therefore, it has been proved that the S is decidable.