Deterministic Finite Automata (DFA)

a total transition function

To say a DFA's transition function is total means it is defined everywhere: for every state q and every symbol a in the alphabet, δ(q, a) names a next state. There are no gaps, no 'and what if...' situations the machine has not planned for. Whatever symbol arrives while you are in whatever state, the machine always has an arrow to follow.

Why insist on this? Because it guarantees a DFA never gets stuck. A run reads every symbol of the input and always reaches a well-defined final state, so acceptance or rejection is decided for every possible string — there is no third outcome like 'undefined' or 'error'. If the table has S states and an alphabet of k symbols, totality means all S times k cells are filled, exactly one state per cell.

In practice, totality is what trap states are for. When a specification implies that some move 'should not happen' or 'should fail', you do not delete that transition; you point it at a (non-accepting) trap state and keep the machine running to the end, where it correctly rejects. Many textbook diagrams hide the trap and its arrows to reduce clutter, relying on the convention 'any missing transition goes to an implicit dead state' — but the underlying DFA still has a total δ.

Over alphabet {a, b} with 3 states, a total δ has 3 x 2 = 6 entries, all filled. If you sketch a machine for 'contains aa' and forget what happens on b from the start state, the δ is not total yet — you must add that transition (often a self-loop) before it is a legal DFA.

Total = every (state, symbol) has a defined next state; a DFA can never get stuck.

Totality is part of the standard DFA definition. Some books allow 'partial DFAs' with missing transitions as shorthand, but they are understood as a total DFA with an implicit dead state.

Also called
totalityfully defined transition function全定義轉移函數全函數性