有限自动机最小化 | Codeboy's Blog

形式陈述

给定完整 DFA $M=(Q,\Sigma,\delta,q_0,F)$ ，在状态上定义等价关系

p\sim q \quad\Longleftrightarrow\quad \forall w\in\Sigma^*,\; \delta^*(p,w)\in F\iff\delta^*(q,w)\in F.

等价状态具有相同右语言，可以合并。DFA 最小化先删除从 $q_0$ 不可达的状态，再计算 $\sim$ 的等价类，并以商集构造商自动机

Q_{\min}=Q/{\sim},\qquad \delta_{\min}([q],a)=[\delta(q,a)].

接受块是与 $F$ 相交的块。由于 $\sim$ 对转移稳定，商转移不依赖代表元；所得 DFA 识别原语言，状态数最少，并在状态重命名意义下唯一。这一结论的语义依据是Myhill–Nerode 定理。

Hopcroft 分割细化算法可按以下步骤求这些类：

以非空块 $F$ 与 $Q\setminus F$ 初始化分割 $P$ ，并令待处理分割器集合 $W=P$ （所有非空初始块）；
从 $W$ 取块 $A$ 。对每个 $a\in\Sigma$ ，求所有以 $a$ 转入 $A$ 的状态 $X=\{q:\delta(q,a)\in A\}$ ；
对每个同时与 $X$ 及其补集相交的块 $Y\in P$ ，用 $Y\cap X$ 和 $Y\setminus X$ 替换 $Y$ ；
若 $Y$ 原在 $W$ 中，就删去旧块 $Y$ 并把两个新块都加入；否则只把较小的新块加入；重复至 $W$ 为空。

初始分割保证接受态不会与拒绝态合并。一次拆分意味着字符 $a$ 后会进入已知行为不同的块，所以新分开的状态可被形如 $av$ 的后缀区分。终止时分割对每个字符稳定，同块状态永远同步落入同一块，因而对所有后缀等价。该稳定分割是细化初始接受分割的最粗右不变分割，正好等于 $\sim$ 。

设删去不可达状态后有 $m$ 个状态、 $k$ 个显式字符。达到 $O(km\log\max\{2,m\})$ 时间、 $O(km)$ 空间还需要具体的数据结构：预先建立每个字符、目标状态的逆边表，记录每个状态所属块及块内位置，并从 $X$ 的成员收集受影响的块，只访问这些块、移动被拆出的成员。不能每次求出 $X$ 后再扫描所有块、所有状态，并仍声称同一个界。

较小块规则让每条逆边只为所属目标状态的对数次有效细化付费；已经排队的块被拆开时，以两个子块替换只是分摊原来的待处理任务，不是无条件新增两份全量工作。初始两块也只产生线性扫描。若字母表采用区间或符号表示，成本必须按实际表示重新核算。下文手算使用更直接的 Moore 同步细化，用来展示划分变化，不冒充 Hopcroft 工作队列的执行轨迹。

直觉

两个状态是否长得相似、编号相邻或当前同为接受态都不是最终标准。唯一标准是：从这里开始，任何可能的后缀会不会让它们给出不同答案。若永远不会，保留两个状态只是重复存储同一份未来行为；若存在一个区分后缀，哪怕很长，也绝不能合并。

分割细化从最粗的可观察差异开始。空后缀已经能区分接受态与拒绝态，所以先分成两块；随后检查每个字符会把状态送往哪一块，发现不一致就继续拆分。短区分后缀先暴露，长区分后缀通过多轮传播逐渐显现。算法不需要枚举无限多个后缀，因为有限状态会让这个过程达到稳定点。

“只把较小半块加入工作集”不改变数学分割，只减少重复扫描。每当一个状态落入被选择的小半块，其所在块大小至少减半；同一状态只能经历对数次这样的事件。这是 Hopcroft 复杂度界的关键，而不是一条可有可无的实现技巧。

例子与边界

从五个子集压缩为四种未来行为

沿用子集构造得到的五态完整 DFA： $A=\{s\}$ 、 $B=\{p,q\}$ 、 $C=\{f,g\}$ 、 $D=\{h\}$ 、 $E=\varnothing$ ，其中 $C,D$ 接受。语言是 $a^*b(\varepsilon\mid b)$ 。确定化保留了 NFA 前沿的差别；此处要判断哪些差别已经不影响任何后续判断。

先按接受位分割，记拒绝块为 $N$ 、接受块为 $T$ ：

P_0=\{\{A,B,E\},\{C,D\}\}.

一轮 Moore 细化同时记录“当前块、 $a$ 后继块、 $b$ 后继块”。当前块必须保留，否则可能把已经分开的接受态与拒绝态重新混合。

状态	相对于 $P_0$ 的签名	细化后所在块
$A,B$	$(N,N,T)$	$\{A,B\}$
$E$	$(N,N,N)$	$\{E\}$
$C$	$(T,N,T)$	$\{C\}$
$D$	$(T,N,N)$	$\{D\}$

所以 $P_1=\{\{A,B\},\{C\},\{D\},\{E\}\}$ 。再检查一次，不会出现新拆分：唯一的多元素块 $\{A,B\}$ 中，两态的 $a$ 后继都是 $B$ ， $b$ 后继都是 $C$ 。它们当前都拒绝；对后缀长度归纳，每一步又具有相同后继，因此对所有后缀答案相同。这里得到的是等价证明，不能用“试了几个词都一样”替代。

令 $U=[A]=[B]$ 、 $V=[C]$ 、 $W=[D]$ 、 $X=[E]$ ，取初态 $U$ ，得到完整商表：

商状态	仍能接受的后缀	读 $a$	读 $b$	接受
$U$	$a^*b(\varepsilon\mid b)$	$U$	$V$	否
$V$	$\{\varepsilon,b\}$	$X$	$W$	是
$W$	$\{\varepsilon\}$	$X$	$X$	是
$X$	$\varnothing$	$X$	$X$	否

这张表有四个状态、八条字符转移。分割稳定保证无论用 $A$ 还是 $B$ 作为 $U$ 的代表，商转移都相同；对输入长度归纳，原运行所在块始终等于商运行所在状态，所以语言不变。例如 $aaabb$ 的商运行是 $U,U,U,U,V,W$ ，读完时接受。

压缩后各块都可由 $\varepsilon,b,bb,ba$ 到达。为了确认没有更小的完整 DFA，还需证明这四块的未来行为两两不同：接受位区分大部分状态对，后缀 $b$ 区分 $U,X$ 以及 $V,W$ 。Myhill–Nerode 定理页把这六对证书写成完整输入字，并据此给出四态下界。商构造提供上界，区分证书提供下界，两者合起来才确定最小状态数。

Moore 算法也能用于一般机器：从接受分割出发，不断按完整后继签名细化。至多发生 $m-1$ 次真正增加块数的细化；每轮扫描 $km$ 项并用线性规模的整数签名分组，可得 $O(km^2)$ 的直接实现。它和 Hopcroft 求的是同一关系，区别在于如何安排工作以及避免重复扫描。

观察语义与表示边界

从关键词集合 {cat, car} 直接建立前缀树 DFA，会得到分别对应完整前缀 cat 与 car 的两个接受态。若机器只回答“是不是这两个词之一”，这两个状态在任意后续字符上都会进入同一个死状态，对空后缀都接受，因此未来行为完全相同，可以合并。前缀 ca 不能与它们合并，因为空后缀会区分接受与拒绝。

若词法分析器还要返回不同 token，例如 cat 对应 ANIMAL、car 对应 VEHICLE，问题就不再是二值语言接受。此时状态的可观察输出不同，初始分割必须按输出标签而不只是接受/拒绝划分；把两态合并会丢失调用者明确需要的信息。最小化总是相对于声明的观察语义。

不可达状态应在细化前删除。它们不会被任何输入前缀访问，却可能拥有独特未来行为；若保留，商自动机仍可识别同一语言，但不一定在所有 DFA 中状态最少，也不再给出规范结果。对缺边的“部分 DFA”，则应先补入共享死状态，或在算法中把缺边一致地解释为该状态。

$F=\varnothing$ 或 $F=Q$ 时，初始分割只有一个非空块，算法立即得到单状态拒绝机或接受机；不要为了维持“两块”而保留空块。表填充算法和 Moore 算法也能求同一等价关系，只是在选择区分证据与复杂度上不同。

对 NFA，具有相同右语言的状态可以安全合并：某状态在字符 $a$ 后可接受的后缀，等于所有 $a$ 后继右语言的并；同右语言状态给出同一个并，对字长归纳可知合并保持语言。但这种压缩未必得到最少状态的 NFA，也没有这里的唯一规范形式。DFA 的单后继块签名与最粗稳定分割算法不能直接宣称解决最小 NFA 问题；先确定化再执行本页算法，得到的是最小 DFA。

本例还说明状态数必须说明计数约定。删掉 $X$ 及所有指向它的边，并约定缺边立即拒绝，可以用三态部分 DFA 表示同一语言；完整 DFA 则确实需要四态。空残余在前者由缺失运行表示，在后者由显式状态表示。取补前必须补全，不能直接翻转这个三态图的接受标记。

推论与应用

最小 DFA 是正则语言的规范指纹。两个完整 DFA 删除不可达状态并最小化后，只需检查是否存在保持初态、字符转移和接受性的状态同构；更直接的等价算法也可在状态对图中搜索区分字，两者都建立在相同未来行为上。

词法分析器生成、模式数据库去重和硬件控制综合都可从状态合并中获益。最小状态数还是不可压缩性的度量：若应用需要区分 $k$ 种 Nerode 残余，任何精确 DFA 实现都至少保留 $k$ 个控制状态，换一种画图或状态编码不会消除这项信息需求。

LALR 状态合并采用另一个标准：合并 LR(1) 项目核心相同的状态，并把向前看集合取并。它可能引入新的归约冲突；该页的四词文法由14态合成13态后，固定优先某条归约会丢掉两个合法词。本页合并的则是所有未来后缀接受行为相同的 DFA 状态，语言保持由等价关系保证。两种状态压缩不能共用同一正确性结论。

参考资料

John E. Hopcroft, STAN-CS-71-190, January 1971，报告正文第 2–5 页：逆转移、工作表与实现成本分析。以下出版版本与这份已核对的技术报告分别列出。
John E. Hopcroft, “An $n\log n$ Algorithm for Minimizing States in a Finite Automaton,” in Theory of Machines and Computations, Academic Press, 1971, pp. 189–196.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, §4.4.
Jean-Éric Pin, Mathematical Foundations of Automata Theory, 2022, Chapter II.

形式陈述 ​

从五个子集压缩为四种未来行为 ​

观察语义与表示边界 ​

反向链接

形式陈述

从五个子集压缩为四种未来行为

观察语义与表示边界