Im studying finite state machines, in particular the deterministic and the non-deterministic versions.

What i have not understood is :

why in a non-deterministic state machine it's allowed that from a state it's possible to go nowhere ?

This is not allewed in DSM. Why ?

  • $\begingroup$ It's just a matter of definition. Some people allow there to be no outgoing transitions even in DFAs. It's completely arbitrary. $\endgroup$ – Yuval Filmus Feb 20 '18 at 11:18
  • $\begingroup$ If a NDSM has an equivalent in a DSM, why all the definitions that involves P,NP,ecc.. uses uses the NDSM ? $\endgroup$ – Qwerto Feb 20 '18 at 11:27
  • $\begingroup$ Like Here $\endgroup$ – Qwerto Feb 20 '18 at 11:28
  • $\begingroup$ The definitions of P and NP use Turing machines, not finite state machines. $\endgroup$ – Yuval Filmus Feb 20 '18 at 11:32
  • 1
    $\begingroup$ Actually P is defined using deterministic Turing machines. NP can also be defined using only deterministic Turing machines (which are given access to a witness which they verify). See our reference question. $\endgroup$ – Yuval Filmus Feb 21 '18 at 12:35

Your Answer

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

Browse other questions tagged or ask your own question.