3.3. 最小化 DFA 中的状态数¶
3.3.1. 最小化 DFA 中的状态数¶
我们为什么需要这样做？
如果你有一个含 \(n\) 个状态的 NFA，那么经转换得到的等价 DFA 最多可能有多少个状态？\(2^n\)
算法
找出不可区分的状态
这些状态在最小化后的机器中合并为一个新状态。
定义： 如果对于所有 \(w \in \Sigma^*\) 以下条件成立，那么两个状态 \(p\) 和 \(q\) 是不可区分的
定义： 如果存在 \(\exists\ w \in \Sigma^*\) 使得以下条件成立，那么两个状态 \(p\) 和 \(q\) 是可区分的
接受器所关心的只是接受还是拒绝字符串。
任选一对状态 \(p\) 和 \(q\) 。
如果在两种情况下它们接受/拒绝的字符串集合完全相同，那么二者之间就没有差别。
因此，我们可以把它们合并。
可区分性是一种等价关系。我们试图把全部状态的集合划分为若干等价子集。
示例：
Figure 3.3.1: 最小化 1¶
考察 A 在 \(a\) 、\(ab\) 上的行为：
\(a\) 到达非终态，\(ab\) 到达终态
考察 F 在 \(a\) 、\(ab\) 上的行为：
\(a\) 到达非终态，\(ab\) 到达非终态
考察 D 在 \(a\) 、\(ab\) 上的行为：
\(a\) 到达非终态，\(ab\) 到达终态
因此，我们知道 F 必须与 A 和 D 处于不同的等价子集中。 A 和 D 最终可能是等价的，也可能不是，我们目前还没有足够的证据来判定。
不幸的是，这显然还不是一个算法，因为我们无法真正在所有的输入字符串上进行测试。
但请记住 \(\delta^*(p, w)\) 的定义。可以这样理解：它告诉我们，对于带着剩余输入到达当前状态之前的那些历史，我们并不关心。
因此，我们可以考察所考虑的两个子集各自出发的每条转移，并确认它们通向"等价"的位置（这与通向非最小化机器中的同一个状态不是一回事）。
我们先把尽可能多合并在一起的状态当作一个候选的等价类，然后在考察各种转移的过程中，看看能否找到迫使我们把它们拆开的证据。
我们将构建一棵树，其根包含原机器中的全部状态。第一步总是把状态拆分为非终态子集与终态子集，因此它们成为根的子节点。然后我们考察树中当前的每一个叶结点，检查该叶中每个状态出发的转移。我们对这个子集中的状态测试一个给定的字符，看它们是否都到达同一个子集。当它们没有到达同一个地方时，就把它们拆开。
下面的幻灯片逐步展示了最小化该 DFA 的过程。
另一个示例：
Figure 3.3.2: 最小化 2¶
