Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?

• 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. – babou Mar 24 '14 at 17:41
• Quick question - what does the picture have to do with the question? – Patrick87 Mar 24 '14 at 18:57
• The answer should be clear from the formal definition you've got, and is impossible to answer without. – 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.

• I don't see how morals factor in here. ;) Also, their professor may very want them to worry in the exam. Unfortunate, but still. – Raphael Mar 24 '14 at 21:27