DFA Minimization — Myhill–Nerode Theorem Visualizer

1 Foundations

What is a DFA?

A Deterministic Finite Automaton (DFA) is one of the simplest models of computation. Think of it as a machine that reads a string of characters one-by-one and decides — does this string belong to my language?

It has a fixed set of states, starts in one state, reads characters, and transitions to a new state for each character. If it ends in an accept state, the string is accepted.

Q — States

A finite set of states the machine can be in

Σ — Alphabet

Input symbols the machine reads (e.g. {0, 1})

δ — Transitions

Given a state + symbol, tells you the next state

q₀ — Start State

Where the machine begins reading

F — Accept States

Ending here means the string is accepted

2 Motivation

What is a Minimized DFA?

A DFA can have redundant states — states that behave identically. Two states might accept exactly the same future strings, making one unnecessary.

A Minimized DFA is the smallest DFA that recognizes the exact same language. No redundant states. Every state is unique. It's the canonical representation — two DFAs accept the same language if and only if their minimized forms are identical.

        Key idea: If two states respond to every possible future input in the exact same way,
        they are equivalent and can be merged into one.
      

3 The Theory

Myhill–Nerode Theorem

This theorem gives us a precise way to determine which states are equivalent. It defines an equivalence relation:

📐 Theorem Statement

Two states p and q are Myhill–Nerode equivalent (p ≡ q) if and only if for every suffix string w:

p ≡ q ⟺ ∀w ∈ Σ* : δ*(p, w) ∈ F ↔ δ*(q, w) ∈ F

In plain English: states p and q are equivalent if no string can tell them apart. No matter what you append, both states agree — they either both accept or both reject. If even one string distinguishes them, they must remain separate states.

Algorithm Steps — Table-Filling Method

We use the Table-Filling Algorithm to systematically find all distinguishable pairs:

Remove unreachable states — Discard any state that can never be reached from the start state.
Base case (ε-distinguishability) — Mark every pair (p, q) where one is accept and the other is not. They're distinguished by the empty string ε.
Propagation — For each unmarked pair (p, q), check each symbol a. If (δ(p,a), δ(q,a)) is already marked, mark (p, q) too. Repeat until stable.
Equivalence classes — Unmarked pairs are equivalent. Group states into classes — each class = one state in the minimized DFA.
Build minimized DFA — Create a new DFA whose states are the equivalence classes. Define transitions between classes. Done!

4 Example

Example DFA

Below is a DFA with 6 states. Some states behave identically and can be merged. Let's minimize it.

Original DFA

Transition Table δ

🎚 Animation Speed Medium

Detailed Fast

5 Walkthrough

Step-by-Step Minimization

Watch the algorithm work through each step automatically. The table fills cell-by-cell, showing every comparison.

— / —

6 Result

Minimized DFA

The minimized DFA compared with the original. Equivalent states have been merged.

–

Original

–

Minimized

–

Classes

–

Reduction

Original DFA

Minimized DFA

Equivalence Classes

Minimized DFA — Transition Table δ'