DFA minimization
In automata theory (a branch of 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.
For each regular language that can be accepted by a DFA, there exists a minimal automaton, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names.) The minimal DFA ensures minimal computational cost for tasks such as pattern matching.
There are two classes of states that can be removed/merged from the original DFA without affecting the language it accepts to minimize it.
DFA minimization is usually done in three steps, corresponding to the removal/merger of the relevant states. Since the elimination of nondistinguishable states is computationally the most expensive one, it is usually done as the last step.
The state p of DFA M=(Q, Σ, δ, q0, F) is unreachable if no such string w in Σ* exists for which p=δ(q0, w). Reachable states can be obtained with the following algorithm:
Unreachable states can be removed from the DFA without affecting the language that it accepts.
One algorithm for merging the nondistinguishable states of a DFA, due to Hopcroft (1971), is based on partition refinement, partitioning the DFA states into groups by their behavior. These groups represent equivalence classes of the Myhill–Nerode equivalence relation, whereby every two states of the same partition are equivalent if they have the same behavior for all the input sequences. That is, for every two states p1 and p2 that belong to the same equivalence class within the partition P, and every input word w, the transitions determined by w should always take states p1 and p2 to equal states, states that both accept, or states that both reject. It should not be possible for w to take p1 to an accepting state and p2 to a rejecting state or vice versa.
...
Wikipedia