形式陈述

给定 DFA $M=(Q,\Sigma,\delta,q_0,F)$$M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$，最小化先删除从 $q_0$$q_0$ 不可达的状态，再把状态按“未来行为”划分：$p\equiv q$$p\equiv q$ 当且仅当对所有 $w\in\Sigma^*$$w\in {\mathrm{\Sigma }}^{\ast }$，$\delta^*(p,w)\in F$${\delta }^{\ast }(p,w)\in F$ 与 $\delta^*(q,w)\in F$${\delta }^{\ast }(q,w)\in F$ 同真同假。该等价关系与转移相容，商自动机的状态是等价类。由 Myhill–Nerode 定理，所得可达 DFA 在状态数上最小，并在保持字母表与语言时唯一到同构。

直觉

两个状态若面对任何后续输入都作出同样的接受判断，就没有可观察差别，可以合并；只比较当前是否接受远远不够，必须比较所有未来。

例子与边界

识别二进制串中 1 的个数奇偶性的 DFA 需要“偶数”和“奇数”两个可区分状态，因为空后缀已经区分其接受性。表填充算法从“一个接受、一个不接受”的状态对开始传播可区分性；Hopcroft 算法则反复细化分块，典型复杂度为 $O(|\Sigma||Q|\log |Q|)$$O(|\mathrm{\Sigma }||Q|\log |Q|)$。最小化不等于正则表达式最短化，也不把 NFA 直接变成最小 NFA；最小 NFA 一般更困难且未必唯一。

推论与应用

最小 DFA 减少词法分析器、协议监控器和模型检查器的状态空间，也给出两个正则语言等价性的判定方法：最小化后比较，或在乘积自动机中搜索可区分状态。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。