1
$\begingroup$

Let A = {(B,w) | B is an NFA that accepts w}. To prove that N is a decidable language,

M = "on input (B,w) where B is NFA and w is a string, simulate B on w. If B accepts w, accept. Otherwise, reject"

Is this a false proof? The proof from the textbook says that I have to convert NFA into equivalent DFA but I'm not sure why this would be necessary. Is it not possible to simulate NFA directly without conversion?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you know how to simulate a NFA on w? How would you do that? How would you determine whether it accepts or not? $\endgroup$ – D.W.♦ Dec 4 '17 at 3:35
  • $\begingroup$ I haven't thought about it but I guess if deterministic TM can implement non-deterministic TM, why not NFA? $\endgroup$ – Ted Dec 4 '17 at 19:30
2
$\begingroup$

The textbook probably suggests you convert into a DFA because it is easier to simulate a DFA than to simulate a NFA and determine whether the DFA accepts the word w. This is trickier on a NFA (but still possible, if you know how).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Also, does "simulating" something mean that the TM is going to run it (like provoking a function call inside a function), or TM is going to mimic the behaviour of that machine? $\endgroup$ – Ted Dec 4 '17 at 3:41

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.