DFA minimization：合并行为一样的 state

subset construction 造出的 DFA 常有冗余：两个状态若对任何后续输入的接受与拒绝结局都完全一致，它们就是等价的，留一个即可。把所有等价状态各自合成一个，得到的最小 DFA 在同构意义下唯一，这是有限自动机里少见的「标准答案」。

1 · 划分细化

找出等价状态的做法是划分细化（partition refinement），从粗到细：

• 先分两大组，accept 与非 accept。前者接受空串而后者不接受，因此不可能等价。
• 反复细分：同一组里的两个状态，若存在某个字符 $c$ 使它们读 $c$ 后落进不同的组，则行为有别，拆开。
• 直到没有任何组还能再拆，此时每组内部行为完全一致。

2 · 合并后的最小 DFA

每个颜色组捏成一个状态，记作 $g_0$、$g_1$ 等；转移取组内任一代表状态的转移即可，同组内部一致保证了这样取不会有歧义。

细化一定停止：每一轮组数只增不减，而组数被状态数封顶。停下时的划分恰好是 Myhill–Nerode 等价类，与从哪一步、按什么顺序拆无关，最小 DFA 因此唯一。这条性质让 DFA 可被规范化：判断两个 regex 是否等价，只需比较各自最小 DFA 是否同构。