0
$\begingroup$

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:

DFA:

DFA

--> NFA:

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.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Every DFA is already an NFA. $\endgroup$
    – Raphael
    Commented May 28, 2015 at 18:46

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 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 Dougherty
    Commented May 28, 2015 at 18:51
  • $\begingroup$ So it is exactly the same state diagram? I need a complete answer quickly please. $\endgroup$
    – iMe
    Commented May 28, 2015 at 19:09
  • 4
    $\begingroup$ We're not a do-my-homework service! $\endgroup$
    – Yuval Filmus
    Commented May 28, 2015 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
    Commented May 28, 2015 at 19:48
  • $\begingroup$ the question asks about a NFA though $\endgroup$
    – Rainb
    Commented Feb 26 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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