Question

Explain how a Turing Machine can simulate an arbitrary DFA. Use a 2-tape Turing Machine. It can be done with a 1-Tape Turing Machine, but 2-tape will likely make the explanation more intuitive.

Answer 1

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