有限自动机最小化

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

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

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

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

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

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

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

NFA 不可直接套用这套商状态算法。NFA 的接受取决于路径集合，局部状态具有相同右语言并不足以覆盖所有组合效应；最小等价 NFA 也不具有 DFA 那样的唯一规范形式。常见工作流因此是先确定化，再最小化得到最小 DFA，而不是宣称得到了最小 NFA。

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

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