Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?

  • 1
    $\begingroup$ Yes: just consider for each transition that the next state is to be read as a singleton set of states with that state as unique element. To be very formal, each DFA is isomorphic to a NFA with singleton sets for the next states. $\endgroup$ – babou Mar 24 '14 at 17:41
  • $\begingroup$ Quick question - what does the picture have to do with the question? $\endgroup$ – Patrick87 Mar 24 '14 at 18:57
  • $\begingroup$ The answer should be clear from the formal definition you've got, and is impossible to answer without. $\endgroup$ – Raphael Mar 24 '14 at 21:26

That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique arrow exiting every state for every character in the alphabet, and there are no $\epsilon$ transitions.

Syntactically speaking, it depends on your definition: the transition function could be encoded differently, so that the transition function of a DFA might not be "legible" for an NFA simulator.

I would not worry too much about the syntactic viewpoint.

| cite | improve this answer | |
  • 1
    $\begingroup$ I don't see how morals factor in here. ;) Also, their professor may very want them to worry in the exam. Unfortunate, but still. $\endgroup$ – Raphael Mar 24 '14 at 21:27

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.