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?
[Math] Properties of a valid DFA
automatacomputer science
Best Answer
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.