DFA minimization

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.

For each regular language, there also exists a minimal automaton that accepts it, that is, 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 three classes of states that can be removed or merged from the original DFA without affecting the language it accepts.

DFA minimization is usually done in three steps:

The state ${\displaystyle p}$ of a deterministic finite automaton ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$ is unreachable if no string ${\displaystyle w}$ in ${\displaystyle \Sigma ^{*}}$ exists for which ${\displaystyle p=\delta ^{*}(q_{0},w)}$. In this definition, ${\displaystyle Q}$ is the set of states, ${\displaystyle \Sigma }$ is the set of input symbols, ${\displaystyle \delta }$ is the transition function (mapping a state and an input symbol to a set of states), ${\displaystyle \delta ^{*}}$ is its extension to strings (also known as extended transition function), ${\displaystyle q_{0}}$ is the initial state, and ${\displaystyle F}$ is the set of accepting (also known as final) states. Reachable states can be obtained with the following algorithm:

Assuming an efficient implementation of the state sets (e.g. new_states) and operations on them (such as adding a state or checking whether it is present), this algorithm can be implemented with time complexity ${\displaystyle O(n+m)}$, where ${\displaystyle n}$ is the number of states and ${\displaystyle m}$ is the number of transitions of the input automaton.

Unreachable states can be removed from the DFA without affecting the language that it accepts.

The following algorithms present various approaches to merging nondistinguishable states.