A trie stops halfway

Take the dictionary

bat
bats
cat
cats

A flat sorted array stores all fourteen characters. A trie stores each distinct prefix once. Counting the root, its states are

ε, b, ba, bat, bats, c, ca, cat, cats

so it has nine states and eight transitions. This is already useful. Membership in a word of length $m$ follows at most $m$ labeled transitions instead of comparing against every dictionary entry.

But look at the subtrees after b and c. From either state, the accepted remaining strings are exactly

at
ats

The two states have different histories and identical futures. A tree cannot share them because every node has one parent. An automaton can.

Before reading on, decide which pair is safe to merge.

Name the future

Let $L$ be the finite dictionary language. For any prefix $p$, define its right language

$$p^{-1}L = \{x : px \in L\}.$$

It is the set of suffixes that complete $p$ into a dictionary word. For the four-word example:

Every row may become one automaton state. The root keeps two transitions, b and c, but both lead to the same state. From there one a transition leads to the shared future for ba and ca, then t reaches an accepting state, and s reaches the final accepting state.

The result has five states and five transitions, yet accepts exactly the same four words.

Work from the leaves upward

For an acyclic dictionary, a state's future is determined by two facts:

• whether the state itself accepts the empty suffix;
• for each outgoing character, which future state that transition reaches.

Once every child has already been minimized, use the pair

$$\sigma(q) = (\operatorname{final}(q), [(a_1,q_1),\ldots,(a_r,q_r)])$$

as a canonical signature. Outgoing labels are ordered, and each $q_i$ is the already chosen representative of its equivalence class. Equal signatures mean equal right languages.

MINIMIZE-DICTIONARY-TRIE(root)
Input:  root of a finite trie with labeled transitions and final-state marks
Output: root of a minimal deterministic acyclic automaton for the same words

register ← empty dictionary from signatures to representative states
return MINIMIZE-STATE(root, register)

MINIMIZE-STATE(q, register)
Input:  trie state q and a register of canonical minimized states
Output: canonical representative of q's right language

for each outgoing label a of q in increasing order
    child ← MINIMIZE-STATE(q.CHILD(a), register)
    q.REDIRECT(a, child)
signature ← (q.IS-FINAL, q.ORDERED-LABELED-CHILDREN)
if register contains signature
    return register[signature]
register[signature] ← q
return q

Trace the example from the leaves:

1. bats and cats are final leaves. Their signatures are both (final, []), so they merge.
2. bat and cat are final and both have an s transition to that merged leaf. They merge.
3. ba and ca are nonfinal and both have a t transition to the merged state. They merge.
4. b and c are nonfinal and both have an a transition to the merged state. They merge.
5. The root remains distinct: its right language is the whole dictionary.

Working bottom-up is essential. Before children have canonical representatives, two equal futures can still appear to point at different trie nodes.

Why it accepts exactly the dictionary

Merging states with equal signatures preserves the language by structural induction on their height.

At height zero, a state has no outgoing transitions. Its right language is either $\{\epsilon\}$ when final or $\varnothing$ when nonfinal, exactly what the final bit records.

Assume canonical child representatives denote equal right languages whenever they are equal. Two parent signatures match only if their final bits match and they have the same outgoing labels to the same child representatives. They therefore agree on the empty suffix, and for any nonempty suffix $ax$, both accept it exactly when their a transition exists and its child accepts $x$. Their right languages are equal. Redirecting either parent to one representative cannot add or remove an accepted suffix.

Applying that argument to every merge preserves the root's right language, which is $L$.

Why five states are necessary

Language preservation does not yet prove minimality. Perhaps a cleverer automaton uses four states.

The five rows in the right-language table are pairwise different. For any two rows, some suffix belongs to one and not the other; that suffix distinguishes the corresponding prefixes. For example, at distinguishes b from ba, while the empty suffix distinguishes bat from ba.

The Myhill–Nerode theorem says that each distinct right language requires a distinct state in every deterministic automaton for $L$. Our construction has one state for each of the five classes, so no equivalent deterministic automaton has fewer states. The minimal automaton is unique up to renaming its states.

Construction cost

Let $N$ be the number of trie states and $E$ its transitions. A postorder walk visits every state and transition once. With a hash register over canonical signatures, expected construction time is $O(N+E)$ plus the cost of hashing the outgoing transitions, and auxiliary space is $O(N+E)$. With an ordered register, lookup adds a logarithmic factor. Membership remains $O(m)$ transitions for a query word of length $m$.

The batch algorithm first builds the trie, so its peak memory includes both the unminimized structure and the register. Daciuk, Mihov, Watson, and Watson showed how to construct the minimal automaton incrementally from lexicographically sorted words, minimizing the previous word's unchecked suffix as soon as the next word proves it can no longer receive a child. That reduces unnecessary intermediate structure; it does not change the equivalence relation.

For the tiny example:

Those counts illustrate state minimization, not byte size. Pointers, object headers, transition encodings, alignment, labels, and compression may dominate the physical representation.

Meet the misspelling machine

An edit-distance automaton recognizes all strings within an admitted distance of the query. The dictionary automaton recognizes only stored words. Their intersection recognizes dictionary words that also satisfy the edit bound.

The traversal state is a pair

$$(q_D, q_E),$$

where $q_D$ is a dictionary state and $q_E$ is an edit-machine state. Follow a character only when both machines have a compatible transition. This avoids enumerating every dictionary word and then measuring it. Shared dictionary futures also share fuzzy-search work.

But the product frontier can still grow. A short common prefix, a generous edit budget, or a highly branching dictionary may visit many paired states. The number of typed characters is therefore not a sufficient work bound. That is the next chapter's problem.

Five wrong turns

Lessons

• A trie shares prefixes; a minimal automaton also shares identical futures.
• The right language of a prefix is the set of suffixes that complete it into an accepted word.
• Bottom-up signatures make right-language equivalence mechanically testable for an acyclic dictionary.
• Distinct right languages need distinct deterministic states, which proves minimality rather than merely language preservation.
• Minimum states does not imply minimum bytes, fastest lookup, or cheapest update.

Practice

1. Retrieval. Define the right language $p^{-1}L$ without using the word “automaton.”
2. Construction. Build the trie for {tap, taps, top, tops} and list every pair of states merged by bottom-up minimization.
3. Proof. Give a distinguishing suffix for every pair among the states after t, ta, and tap.
4. Discrimination. Describe a workload where a flat sorted dictionary is a better engineering choice than a minimal DAFSA.
5. Transfer. Find two states in a workflow, parser, or protocol with different histories but identical allowed futures. State what would make merging them unsafe.

The automaton has made the dictionary smaller, but it has not made every query equally cheap. The Cost of a Query Is Not Its Length replaces character count with the branching frontier and the number of product states actually visited.

References

1. Daciuk, Mihov, Watson, Watson. “Incremental Construction of Minimal Acyclic Finite-State Automata.” Computational Linguistics 26(1), 2000. — primary source for the epigraph, register method, sorted and unsorted incremental construction, and terminology
2. Edward Fredkin. “Trie Memory.” Communications of the ACM 3(9), 1960. — introduces the term trie and its retrieval motivation
3. Anil Nerode. “Linear Automaton Transformations.” Proceedings of the American Mathematical Society 9(4), 1958. — primary theorem lineage for finite-state equivalence and minimality; the conventional name also credits John Myhill's related formulation