How a DFA Decides Membership: Transition Tables and the Extended Transition Function

A deterministic finite automaton is the smallest machine for which the question “does this string belong to this language” has a complete, mechanical answer. It reads the input once, left to right, keeps a single state in a register, and never looks back. That description is also the whole correctness argument: after reading a prefix, the state must encode everything about that prefix that the future can depend on.

The formal object is a five-tuple M = (Q, Σ, δ, q₀, F). Q is a finite nonempty set of states, Σ a finite alphabet, δ a function from Q × Σ to Q, q₀ the start state, and F ⊆ Q the accepting states. Each component is a decision with consequences, and the consequences show up directly in code.

The five-tuple, and which component costs memory

Q and Σ are the two sizes that matter. The transition function is a table with |Q| · |Σ| entries, one per state-symbol pair. For a lexer over raw bytes, |Σ| is 256; for a 1,000-state machine that is 256,000 entries. Stored as 16-bit state indices, the table is 512 KB, which exceeds the 256 KB data cache common on older x86 cores. Flattening the table to 8-bit indices fits it in 256 KB, but then the machine is limited to 256 states.

δ is required to be total: every pair has a target. Implementations routinely relax this and use a partial table with an implicit dead state, which is a representational choice, not a change of theory. The distinction matters when the automaton is complemented, because complementing a partial machine requires adding the dead state first. The product constructions that combine two machines inherit the same obligation.

F is a predicate on states, so it is usually a bit vector of |Q| bits rather than a set. A membership test is then a shift and a mask, not a hash lookup.

Lifting δ from one symbol to a whole string

δ says what one symbol does. The machine needs to know what a string does, so the definition introduces the extended transition function δ*: Q × Σ* → Q by recursion on the length of the input:

• δ*(q, ε) = q for the empty string.
• δ*(q, wa) = δ(δ*(q, w), a) for a string w and a symbol a.

This is the only induction in the definition, and it is where determinism earns its name. Because δ*(q, w) is a single state rather than a set, the recursion collapses to a fold over the input: there is exactly one intermediate value at every step. Acceptance is then δ*(q₀, w) ∈ F.

The recursion also fixes the evaluation order. δ*(q, wa) applies the symbol a last, so the fold is left-to-right, and no lookahead is needed. A machine that had to inspect the end of the string before deciding what the beginning meant could not be simulated with a fixed-size register.

/* Dense table: row per state, column per symbol. Returns 1 if s is accepted. */
int dfa_accepts(const uint16_t *delta, size_t nstates, size_t nsym,
                uint16_t start, const uint8_t *accept,
                const uint8_t *s, size_t len)
{
    uint16_t q = start;
    for (size_t i = 0; i < len; i++) {
        if (s[i] >= nsym) return 0;              /* byte outside the declared alphabet */
        q = delta[(size_t)q * nsym + s[i]];
    }
    return accept[q];                            /* also correct when len == 0 */
}

Three details in that loop are load-bearing. The index expression multiplies by nsym rather than shifting, because the alphabet size is not a power of two in general. The alphabet check is explicit because the definition assumes Σ contains the whole input; a real byte stream can contain symbols the machine was never built for, and the two honest options are to reject or to route them to a dead state. And the return happens after the loop, so the empty string is accepted exactly when q₀ ∈ F.

A table layout that survives dependent loads

The loop above has a serial dependency: the address of the next load depends on the value of the current load. No amount of instruction-level parallelism hides that, so the machine runs at memory latency, not at arithmetic throughput. Two layout decisions reduce the latency.

The first is to keep a row pointer instead of recomputing the offset:

const uint16_t *row = delta + (size_t)start * nsym;
for (size_t i = 0; i < len; i++) {
    if (s[i] >= nsym) return 0;
    row = delta + (size_t)row[s[i]] * nsym;      /* one multiply, hoisted out of the load */
}

This hoists the base offset out of the loop and leaves a single load per symbol. Each iteration still multiplies the loaded state index by nsym to form the next row address, so the multiply is not eliminated, only moved off the start of the loop. The remaining cost is the load itself: a table that fits in the first-level data cache costs a few cycles per byte, a table that lands in a second-level cache costs more, and a table that misses to DRAM stalls for the full miss latency. Since the access pattern is data-dependent, prefetching does not help.

The second is to shrink the alphabet. Lexer generators routinely compute equivalence classes of input characters: two bytes are equivalent when every state transitions to the same target on both. For a programming-language lexer the number of distinct columns is usually far below 256, and a table with 64 columns is a quarter of the size. The mapping from byte to class is one extra load per input symbol, which is why it is only worth doing when the reduction moves the table into a smaller cache level.

Sparse representations are the other option. A compressed row stores only the transitions that do not go to the dead state, with a per-state default. That trades a second indirection and a bounds check for a much smaller footprint, which is the right trade when the automaton is large and most states transition to dead on most symbols.

Boundary conditions that break naive simulators

The empty string is the first one. A simulator that reads a symbol before testing acceptance, or that requires the loop to execute at least once, will reject ε even when q₀ is accepting. This is not a theoretical nicety: every regular expression that can match the empty string produces such a machine.

Signed characters are the second. In C, char may be signed, and a byte value of 0x80 or above converted to int is negative. Using it as a table index reads memory before the array. The fix is to do the arithmetic in unsigned char or uint8_t, which is why the loop above takes const uint8_t *.

The third is the mismatch between state identifiers and table positions. A DFA whose states are renumbered during minimization, but whose table was built with the old numbering, still runs and still halts on every input; it simply accepts a different language. There is no structural check that catches this, which is why the transition table and the accepting-state vector should be generated together from one description.

The fourth is a partial table that silently treats a missing entry as “stay in the current state” rather than “go to dead”. Both behaviours are implementable and they define different languages. The five-tuple rules out the ambiguity by demanding totality, and any compressed representation has to document which convention it encodes.

What determinism buys and what it charges

The purchase is a membership test that is O(n) in time and O(1) in working memory, with a constant of one dependent load per symbol. Streaming is free: the machine can emit a verdict for a prefix at any point, and the state after a prefix is a complete summary of that prefix. That property is what makes DFAs the right model for network protocol parsers, lexical analyzers, and any input that arrives in pieces.

The charge is size. Determinism can require exponentially more states than a nondeterministic machine for the same language, and the subset construction that closes the gap can produce 2^n states from an n-state NFA. Building the table is also a whole-program operation: adding one pattern to a lexer means recomputing the automaton, not appending a rule. The alternatives to that rebuild cost are covered by the on-the-fly subset simulation in simulating an NFA without determinizing and by derivative-based construction, which rebuilds lazily.

The table itself is the artifact. It is finite, it is total, and its size is the product of two numbers that a designer controls: how many distinctions the language requires, and how coarse the alphabet can be made without losing them.