1
$\begingroup$

I'm trying to understand the difference of DFA from NFA I have this example in my coursebook enter image description here Are the empty symbols at the start necessary? or can we do away with them to have something like this enter image description here

$\endgroup$
3
$\begingroup$

Yes, in this example, your solution is fine.

Perhaps the example just wanted to show the use of epsilon transitions. Also, your approach would be more complicated in the case where one of the original initial states would have a loop. We cannot transfer that loop to the common initial state.

$\endgroup$
1
$\begingroup$

Whilst your answer correctly solves the tasks of recognising which strings belong to the regular expression, without the epsilon transitions the behaviour is entirely deterministic. This means that strictly speaking you have constructed a DFA, and not an NFA. It's a subtle difference and I would argue that this example probably isn't the best, but a strict professor would be justified in not giving full marks.

$\endgroup$
  • 5
    $\begingroup$ A DFA is a special case of an NFA. That is, all DFAs are NFAs. Therefore, if the question asks for an NFA and the student gives a correct DFA then the student has given a correct NFA. All functions are relations but not all relations are functions. $\endgroup$ – Bob Feb 23 at 23:29
  • 1
    $\begingroup$ I'd certainly say it depends on which definition you are using, I found this on wikipedia: "In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article." I would advise that OP check what is in use on their course. $\endgroup$ – Nick Feb 23 at 23:33

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.