# Minimization

Given a DFA, we want to construct from it a DFA for the same language, but with as few (reachable) states as possible.

The strategy will be to eliminate redundant states by "merging" them. When are two states considered to be redundant?

## Equivalence of states

:::info
**Definition.** Let $\mathcal A = (Q,\Sigma,\delta,q_0,F)$ be a DFA and $p,q \in Q$ be states. We call $p$ and $q$ **equivalent** iff:
for all $w \in \Sigma^*$ either $\widehat{\delta}(p,w)$ and $\widehat{\delta}(q,w)$ are both accepting or both rejecting. In this case, we write $p \sim_{\mathcal A} q$ or simply $p \sim q$.
:::

In fact, equivalence of states defines an [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation).

We observe: if $w = \varepsilon$ then $p \sim q$ entails that both $p$ and $q$ themselves have to be either both accepting or both rejecting. This is a *necessary*, but in general not a *sufficient* condition for them to be equivalent.

## Minimization

DFA minimization will consist of merging distinguishable states with each other (and removing nonreachable states if there are any). Formally, this is done via taking as states *equivalence classes* of states, and defining the rest of the structure accordingly:
:::info
**Construction.** Let $\mathcal A = (Q,\Sigma,\delta,q_0,F)$ be a DFA. Consider the DFA $\mathcal A^{\mathrm{min}} = (Q^{\mathrm{min}}, \Sigma, \delta^{\mathrm{min}}, q_0^{\mathrm{min}}, F^{\mathrm{min}})$ defined by:
* $Q^{\mathrm{min}} := \{[q]_\sim \; | \; q \in Q\}$
* $\delta^{\mathrm{min}}([q],a) := [\delta(q,a)]$
* $q_0^{\mathrm{min}} := [q_0]$
* $F^{\mathrm{min}} := \{[q] \; | \; q \in F\}$
:::

:::success
**Theorem.** Let $\mathcal A$ be a DFA with all states reachable. Then $\mathcal A^{\mathrm{min}}$ is the (essentially unique) DFA with the same language as $\mathcal A$ and the minimal number of states.
:::

## Example.

Consider the following DFA $\mathcal A$ that has $8$ states, $7$ of which are reachable:

We distinguish states via a table as follows, marking distinguishable states with '$\times$', and equivalent (i.e., non-distinguishable) states with '$\square$':

| | | || | | | |
| -------- | -------- | -------- | -------- | -------- | -------- |-------- | -------- |
| $B$ | $\times$ | | | | | | |
| $C$ | $\times$ | $\times$ | | | | | |
| $D$ | $\times$ | $\times$ | $\times$ | | | | |
| $E$ | $\square$ | $\times$ | $\times$ | $\times$ | | | |
| $F$ | $\times$ | $\times$ | $\times$ | $\square$ | $\times$ | | |
| $G$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | |
| $H$ | $\times$ | $\square$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ |
| | $A$ | $B$ |$C$ | $D$ | $E$ |$F$ | $G$ |

This gives us the following minimized DFA $\mathcal A^{\mathrm{min}}$, which has $5 \leq 7$ states:
Note that the nonreachable state $D$ has been merged with the reachable state $F$. We could have removed $D$ in $\mathcal A$ since that does not change the language.