2.3 DFA and DFA Minimization

A deterministic finite automaton, or DFA, is the executable form of a regular-language decision procedure. It reads one input symbol at a time, keeps one current state, follows one transition, and finally accepts or rejects depending on the ending state. This simplicity is exactly why DFAs are so valuable in lexical analysis: a scanner can process a file with a tight loop over characters.

Formally, a DFA is a five-tuple:

(Q, Σ, δ, q0, F)

where:

• Q is a finite set of states.
• Σ is a finite input alphabet.
• δ is the transition function.
• q0 is the start state.
• F is the set of accepting states.

The transition function is the heart of determinism. For each state and input symbol, the DFA has one next state. Some definitions require the transition function to be total; every missing transition is made explicit by a trap state. Compiler implementations often use tables where "no transition" means failure for the current token attempt.

A DFA for Containing 001

Let Σ = {0, 1} and let the target language be $Σ^*001Σ^*$, all binary strings that contain substring 001. A useful state design is to remember the longest suffix of what we have read that is also a prefix of 001.

q0: no useful prefix currently matched
q1: recent suffix is "0"
q2: recent suffix is "00"
q3: substring "001" has been seen

The transition table is:

The start state is q0, and the only accepting state is q3. Once the automaton reaches q3, it remains there because the string already contains 001; later characters cannot undo that fact.

Running a DFA Like a Lexer

A table-driven scanner often looks conceptually like this:

state = start
for each character c:
    state = transition[state, class(c)]
    if state is accepting:
        remember this position and token kind

The scanner may keep more than one piece of information: current state, last accepting state, last accepting position, source offset, line and column, and token priority. But the automaton itself remains simple. Every input character updates the current state.

This style is fast because the runtime work is regular: classify a character, look up a transition, update a state, maybe record an accepting position. Lexer generators optimize the table layout, merge character classes, compress sparse rows, or emit direct code, but the conceptual model is still a DFA.

Equivalent States

Two DFA states are equivalent if no possible future input can distinguish them. More precisely, states p and q are equivalent if for every string w, starting from p on w accepts exactly when starting from q on w accepts.

This definition is stronger than "the states have similar names" or "the states are both non-accepting." Accepting versus non-accepting gives the first obvious split, but transition behavior decides the final partition.

For example, suppose two states both transition on 0 to an accepting block and on 1 to the same non-accepting block. If they also share the same acceptance status, they may be equivalent. But if one state can reach an accepting state with future input 01 and the other cannot, they must remain separate.

Partition Refinement Minimization

DFA minimization constructs the smallest DFA that recognizes the same language, up to renaming states. A common algorithm uses partition refinement:

1. Remove unreachable states if necessary. 2. Split states into accepting and non-accepting groups. 3. Repeatedly split any group whose states transition into different groups for some input symbol. 4. Stop when no group can be split further. 5. Each final group becomes one state in the minimized DFA.

The algorithm is mechanical, but the intuition is sharp: if two states behave differently on some future input, there must be a way to separate them. If no future input can separate them, they are redundant copies of the same behavior.

Minimization matters for generated scanners because many token regexes are combined into one automaton. The raw DFA produced by subset construction can contain many states. Minimization and table compression can reduce memory footprint, improve cache behavior, and make generated code easier to reason about.

Derive States From Information, Not From Drawing Style

For a recognizer of 001, each state encodes exactly the useful suffix: after 00 and another 0, the useful suffix is still 00, so the transition loops at q2; after 001, the property is permanently true, so q3 is absorbing. This “longest suffix that is also a pattern prefix” technique generalizes to keyword and delimiter recognizers and is closely related to string-matching automata.

Before minimizing, remove unreachable states. Then distinguish states by a witness suffix: if appending w accepts from one state but rejects from another, w proves they cannot merge. During partition refinement, record the symbol that caused each split. That record explains the minimized machine and is invaluable when a generated scanner unexpectedly changes behavior.

Lexer Reality Check

A token DFA normally remembers the last accepting state and input offset. It may pass through non-accepting states while extending a candidate token, then fall back to the last accepted position. That is how a lexer can distinguish = from == without prematurely returning =.