I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows:



--> NFA:


--> Turing machine:


I haven't found any explanation/tutorial on how to do this. So, a final solution containing a state diagram with an explanation on what steps were followed would be great.

  • 4
    $\begingroup$ Every DFA is already an NFA. $\endgroup$ – Raphael May 28 '15 at 18:46

A DFA is simply a Turing machine that moves the head to the right on every transition until it reaches the first blank tape cell.

Thanks to Ryan for a comment that clarified this answer.

  • 1
    $\begingroup$ It is obvious, but the OP should note that this should say "to the right on every transition if the cell is non-blank". $\endgroup$ – Ryan May 28 '15 at 18:51
  • $\begingroup$ So it is exactly the same state diagram? I need a complete answer quickly please. $\endgroup$ – iMe May 28 '15 at 19:09
  • 4
    $\begingroup$ We're not a do-my-homework service! $\endgroup$ – Yuval Filmus May 28 '15 at 19:10
  • $\begingroup$ @iMe I've already given you practically the whole answer. If you understand what a DFA is and what a Turing machine is, you should be able to finish it. If not, ask your course instructor for help. I can't write it down as a Turing machine because I don't know what notation you use and because I think I've already done enough of your homework for you. $\endgroup$ – David Richerby May 28 '15 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.