2
$\begingroup$

Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an exiting arrow for input 0 from this nonaccepting state, which is just redundant. Why not draw no arrows at all for 0?

$\endgroup$
  • $\begingroup$ Why clutter a formal definition with "optimizations" that add no real benefit? $\endgroup$ – chepner Jul 16 at 16:06
9
$\begingroup$

This is part of the (usual) definition of DFAs. It's hard to argue with a definition.

While it's hard to argue with a definition, one can ask why the object was defined in a certain way. Here one answer is that we want our automaton to always be at a particular state, whatever happens. In other words, we want the transition function to be a function rather than just a partial function. It is a matter of taste.

Some people allow the transition function to be partial, and still call the resulting model DFA, though this is probably less common than Sipser's definition. The two definitions are almost equivalent – accommodating a partial transition function takes at most one additional "sink" state.

$\endgroup$
-1
$\begingroup$

In addition to what Yuval Filmus wrote, let me remark that the transition "function" not actually being a function but, rather, a partial function may impair the elegance of some proofs (or make them unnecessarily harder). Consider, for instance, the proof of the pumping lemma; in the usual definition, you let $p$ be the number of states and then take a word $w$ which the DFA accepts and is longer than $p$. The argument then is that, when you consider the trace of states which the automaton takes to accept $w$, there is at least one state that comes up twice (by the pidgeonhole principle). This is then used to derive a loop and, hence, pump the "middle" part of $w$.

This argument falls flat on its face when the transition function is partial. Then there is no guarantee the DFA does not stop and accept $w$ previously to running into the loop.

(Of course, here I am talking about the DFA accepting early whereas you were possibly referring to only nonaccepting states having incomplete transitions, but I am sure you get the idea.)

$\endgroup$
  • $\begingroup$ I've never heard of a definition of DFA that uses partial functions and says that a word is accepted when it is not completely read. The partiality is only in rejecting early. If one such definition exists and is actually used somewhere then yes that could cause issues in certain instances, but the "usual definition of DFA using partial functions" has no problem with the pumping lemma proof. $\endgroup$ – Giacomo Alzetta Jul 16 at 8:03
  • $\begingroup$ Note the remark in the last sentence. I am only giving an example for how this style of proof is broken by having only partial transitions (and I only chose the pumping lemma because the proof should be familiar or simple enough to most). That we are considering a $w$ which is accepted is only incidental (because of the pumping lemma's statement); it is quite conceivable we could be in some other context, proving a claim in which it is irrelevant whether $w$ is accepted or not, and run into problems because $w$ does not have a full trace. $\endgroup$ – dkaeae Jul 16 at 8:35
  • 1
    $\begingroup$ Your pumping lemma example is broken. Suppose the automatom accepts some long word. Then, because it accepts, it cannot have got stuck. Therefore, it must have made as many transitions as the length of the word. By the pigeonhole principle, it must have visited the same state twice. That loop doesn't get stuck, so you can pump it as many times as you want and still accept. The transition function being partial makes almost no difference. $\endgroup$ – David Richerby Jul 16 at 10:21
  • $\begingroup$ Perhaps a more interesting example is the Hopcroft minimization algorithm, which requires a complete transition function. Obviously this doesn't affect validity; it's possible to add the sink state before running the algorithm. However, adding that state can add a lot of transitions, which changes the complexity of the algorithm as a function of the size of the original (partial) function. $\endgroup$ – rici Jul 16 at 14:39

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.