How to convert a DFA to a Turing machine?

Question

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.

Aimless

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.

Hope this helps!

Pale

When happens when a character c is read that does not result in a state transition? Is an arbitrary character written and the tape head moves right still? – Sokol

@Sokol Under most definitions of a DFA, the DFA must have a transition defined for each character and each state. Similarly, most TMs are defined in a way that lets you restrict what sorts of symbols can be fed in as input, and so you would never need to worry about this: any TM symbol that could be encountered would be something the DFA would have a transition defined for. Alternatively, if you don't have that restriction, just reject - the DFA's language is restricted to using only characters from its alphabet, so if you see a foreign character, you know the string isn't in the language. – Pale