How to convert DFA to a Turing machine?

Having a DFA diagram, how can I convert it to a Turing machine? Should I find a language that DFA accepts, and then create a Turing machine? Or is there a direct path?

Thanks.

+6
source share
1 answer

Each transition in the DFA reads an input character, a transition follows, then moves on to the next input character. Once all the input has been read, the DFA accepts if it is in the receiving state and rejects otherwise.

You can directly simulate this using a Turing machine. Build the end state management of a Turing machine by creating one state for each state in the DFA. For each transition in the DFA on symbol c, replace this transition in the TM with one that, when reading the symbol c, writes any arbitrary symbol to the tape (no matter what), and then moves the tape to the right (to the next place on the tape). Then, for each state, enter a transition to an empty symbol from this state either to the TM acceptance state or to the TM reject state (depending on whether this state accepts or rejects). This TM effectively starts the DFA by manually entering through the input line and finally deciding whether to accept or reject at the end of the run.

Hope this helps!

+8
source

All Articles