0
$\begingroup$

The first one seems like a DFA. Could someone explain why this is a NFA?

enter image description here

$\endgroup$
3
  • 2
    $\begingroup$ Every DFA is a NFA by definition (though not every NFA is a DFA). $\endgroup$ – Steven Jan 26 at 20:01
  • $\begingroup$ The first one is not a DFA as the final state doesn't have a transition on $0$. $\endgroup$ – Jamāl Jan 26 at 20:11
  • 1
    $\begingroup$ @Jamāl, it is standard to omit transitions from DFAs with the intended meaning that any unspecified transition goes to an additional non-final state $q$ (and all transitions from $q$ go to $q$ itself). $\endgroup$ – Steven Jan 27 at 13:55
2
$\begingroup$

Here is a similar question:

Which of the following are rational numbers: $$ 1, \frac{2}{3}, \sqrt{2}. $$

The correct answer is that both $1$ and $\frac{2}{3}$ are rationals, despite the fact that $1$ is also an integer.

One thing which is confusing here is that none of the given examples are DFAs or NFAs. Rather, they are pictorial representations of automata. Most of these pictorial representations can be interpreted as NFAs, and some can also be interpreted as DFAs. There would be no ambiguity if the automata were given as tuples, since the transition function of a DFA has signature $Q \times \Sigma \to Q$, whereas the transition function of an NFA has signature $Q \times \Sigma \to 2^Q$.

$\endgroup$
3
  • $\begingroup$ Your answer got me thinking about the ambiguity of transition diagrams, because I am thinking, specially for very small diagrams such as the one in the question, it should be clear enough that the diagram when presented can be identified as an NFA or a DFA. Maybe your point is about having a formal definition? Or am I missing something? $\endgroup$ – Russel Jan 27 at 17:36
  • $\begingroup$ A diagram cannot be identified as an NFA or a DFA. Some diagrams can be interpreted as representing NFAs. Some can be interpreted as representing DFAs. The latter are a subset of the former. $\endgroup$ – Yuval Filmus Jan 27 at 17:38
  • 1
    $\begingroup$ Mmm, don't know about ambiguity. I would say that a NFA has a transition relation, a subset of $Q\times \Sigma\times Q$. Then the question whether every DFA is also an NFA is a matter of taste, whether you agree that a function is also a relation, but with special requirements. $\endgroup$ – Hendrik Jan Jan 28 at 13:30
1
$\begingroup$

There are two explanations that work:

  1. By definition every DFA is also a NFA (perhaps the question meant to ask which are NFAs but not DFAs and which are DFAs).
  2. In a DFA, each state must have transitions (outgoing edges) defined for each element of the alphabet (commonly referred to as $\Sigma$).

If you look at the first one, states S1 and S2 don't have a transition for 1, and for state S3, there is no transition for 0. One of the comments mentions that it is common to ignore some transitions in a DFA and have them go to a dead state, but by definition, a DFA must be fully specified. Omitting transitions is just a convenience for some people, but isn't universal.

$\endgroup$
1
  • $\begingroup$ (1) This depends on the definition, see my answer. (2) Again, this depends on the definitions. Some definitions of DFA allow the transition function to be partial. $\endgroup$ – Yuval Filmus Jan 27 at 17:39
0
$\begingroup$

The first automaton is not a DFA because it has missing transitions. Indeed, the states $s_1, s_2$ have no outgoing transitions labeled with 1, also, the state $s_3$ has not outgoing transition labeled with 0. As you've noted, intuitively, this automaton does not really look nondeterministic because you don't have a guess (the automaton has at most one run on a given input word) and you can easily direct all missing transitions to a rejecting sink to get a complete deterministic transition function ($\delta$ is defined for every state and letter). I agree, and some people consider such automata to be deterministic (this has been explained thoroughly here), but probably, the way you defined it in class does not allow missing transitions.

$\endgroup$

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.