Drawtomata / DFA minimization
DFA minimization
Draw a DFA above and press Minimize. Drawtomata removes unreachable states, then shows the marking table pass by pass and the π₀, π₁, … partitions, and draws the minimal DFA.
Table-filling (mark) method
- Remove states that cannot be reached from the start state.
- Mark every pair (p, q) where one state is final and the other is not.
- Repeat: mark (p, q) if for some symbol a the pair (δ(p, a), δ(q, a)) is already marked.
- Pairs that are never marked are equivalent. Merge them.
Partition method
Start with π₀ = {final states, non-final states}. Split a group whenever two of its states go to different groups on some symbol. Stop when a pass splits nothing: each group is one state of the minimal DFA.
Example
Pick DFA with equivalent states from the Examples menu above. It has five states, q0 to q4, over {a, b}. q0 and q2 can never be told apart, so they merge and the minimal DFA has four states. It accepts the strings that end in abb.
Questions
Does the DFA need to be complete?
For the textbook methods, yes. Missing moves are sent to a trap state first, and the tool shows it when it is needed.
Is the minimal DFA unique?
Yes. Every DFA for a regular language minimizes to the same machine, up to the names of the states.