6
$\begingroup$

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?

$\endgroup$
3
  • 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, 2014 at 17:41
  • $\begingroup$ Quick question - what does the picture have to do with the question? $\endgroup$
    – Patrick87
    Mar 24, 2014 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, 2014 at 21:26

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
1
  • 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, 2014 at 21:27
-1
$\begingroup$

if you write a DFA that generates lets say sigma star it wont be possible on an NFA some languages can not be converted efficiently or youll be just adding epsilons everywhere

$\endgroup$

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.