DFA minimization

Example DFA. If in state , it exhibits the same behavior for every input string as in state , or in state . Similarly, states and are nondistinguishable. The DFA has no unreachable states.
Equivalent minimal DFA. Nondistinguishable states have been merged into a single one.

In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.[1]

  1. ^ Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's".