Is a DFA required to have transitions on each input symbol from each state defined? If there isn't a path from state q1 to another state on input a for example, does that invalidate the DFA itself. I'd think it simply means that if the machine reads 'a' when in q1, it doesn't have a corresponding transition defined and hence rejects the input string. The definition of a DFA only requires it not to have multiple transition, per input symbol per state, does that also mean it has to have exactly one transition per input symbol per state?

  • $\begingroup$ It all depends on your definition of DFA, but it doesn't particularly matter, because the two notions of DFA are fairly easily proven equivalent. $\endgroup$ – Cam McLeman Feb 24 '12 at 20:16
  • $\begingroup$ @CamMcLeman: The word “equivalent” in your comment has to be interpreted with caution, because people care about the difference between, say, DFA and NFA, although they are fairly easily proven “equivalent” under some standard terminology. $\endgroup$ – Tsuyoshi Ito Feb 24 '12 at 23:17
  • $\begingroup$ Certainly, agreed. For example, if you were in a situation where you cared about the number of states you used, then you'd want to be more careful (though as in Henning's answer, a single extra state is enough in this case). $\endgroup$ – Cam McLeman Feb 25 '12 at 0:24

That depends on the precise definitions you're working with.

It's not uncommon to allow states where not all input symbols have a transition. The standard semantics is then that the automaton will reject any input string that would need one of the missing transitions.

On the other hand, it is trivial to convert such an automaton to one where all symbols always have a transition, just by adding a single global non-accepting state where all of the new transitions will end up, and which has transitions to itself for every symbol.

The convention where transitions can be missing is nearly always used when drawing automata, for obvious reasons of avoiding irrelevant, visually distracting clutter in the diagram. On the other hand, it is useful when proving theorems about automata to assume that there's always a relevant transition. In actual implementations, either of the conventions may end up being the most convenient.

In general, you're assumed to be able to pass from one representation to the other without much thought.


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.