How to convert a DFA to a Turing machine?
Having the diagram of a DFA, how can I convert it to a Turing Machine? Do I have to find the language that the DFA accepts and then create the Turing Machine? Or is there a direct way?
Thank you.
Answer
Each transition in a DFA reads a character of input, follows a transition, then moves to the next character of input. Once all input has been read, the DFA accepts if it's in an accepting state and rejects otherwise.
You can directly simulate this with a Turing machine. Build the finite state control of the Turing machine by creating one state for each state in the DFA. For each transition in the DFA on the character c, replace that transition in the TM with one that, on reading character c, writes back some arbitrary character to the tape (it doesn't matter what) and then moving the tape head right (to the next spot on the tape). Then, for each state, introduce a transition on the blank symbol from that state either to the accept state of the TM or the reject state of the TM (based on whether that state is accepting or rejecting). This TM effectively runs the DFA by stepping manually across the input string and finally deciding whether to accept or reject at the end of the run.
Hope this helps!