8. 最小化 DFA 的状态数¶
8.1. 最小化 DFA 的状态数¶
回想一下，我们现在已经有了一个把任意 NFA 转换为等价 DFA 的算法。这个算法的问题是： 它的最坏情况是，从一个具有 \(n\) 个结点的 NFA 构造出的 DFA 最多可达 \(2^n\) 个结点。这为什么是个问题呢？如果我们想做的只是回答"NFA 是否比 DFA 更强大？"这个抽象问题，那确实无所谓——有这个算法就足以回答这个问题了。但就 DFA 作为有用的计算模型而言，这就重要了。
事实上，DFA 在现实生活中正是有用的计算模型。从历史上看，许多带控制机构的物理机器都是在硬件中实现的，其控制行为正是基于用 DFA 建模。像自动售货机、微波炉这类设备，都可以在概念上用状态机的思想来建模。回想一下，设计者有时会发现，先用 NFA 来设计是最省事的。但我们并不希望把最终得到的系统实现为 NFA，而是希望先把它改造成 DFA。然而这样一来，我们也不希望为一个过于复杂的 DFA 配备那么多多余的硬件。这正是需要对 DFA 的状态进行最小化的用武之地。
你可能已经或多或少熟悉正则表达式（regular expression）了，毕竟有那么多程序员一直在使用它们。即使你还不熟悉也没关系，我们很快会讲到。这里要说明的是，NFA（以及由此得到的、最小化后的 DFA）的另一个现实应用，在于使用正则表达式的工具会以它们作为底层实现。所以，这些有穷自动机确实有实际用途。
遗憾的是，这种方法并不能算作算法： 当语言是无穷的时候，我们不可能对所有输入串逐一测试。
但请记住 \(\delta^*(p, w)\) 的定义。换个角度看： 它告诉我们，在带着输入剩余部分到达当前状态之后，我们并不关心在此之前的历史。
因此，我们可以考察从所考虑的两个子集出发的每条转移，并验证这些转移是否引向"等价"的位置（这并不等同于在未最小化的机器中引向同一状态）。
我们将从尽可能大的状态合并开始，把它视为一个潜在的等价类；在考察各种转移的过程中，看看是否能找到迫使我们把它们拆开的证据。
我们将构造一棵树，根结点包含原机器中的所有状态。第一步总是把状态划分为非终态子集与终态子集，它们就是根结点的孩子。然后我们考察树中某个当前的叶结点，检查该叶结点中各个状态出发的转移。我们用给定的字符去测试该子集中的各个状态，看它们是否都转移到同一个子集；当它们没有转移到同一位置时，就把它们拆开。
8.2. 最小化示例 1¶
下列幻灯片逐步演示最小化一个 DFA 的过程。
8.3. 最小化示例 2¶
下列幻灯片以另一个例子逐步演示最小化 DFA 的过程。
8.4. 可判定性¶
给定两个 DFA，它们接受的是同一种语言吗？一般来说，是否有可能对任意两个 DFA 回答这个问题？这类问题属于计算机科学中被称为 可计算性 理论的范畴。所用的术语是： 两个 DFA 是否接受同一种语言，这是否 可判定的 ？
事实证明，有些系统能回答这个问题，有些系统则不能。我们现在就可以告诉你： 一般来说，无法判断两个计算机程序是否计算同一个函数（也就是说，两个程序对任何给定输入是否总是给出相同输出）。这是 停机问题 的一个变体，我们后面会讲到。
相反，事实证明，我们 可以 判定两个 DFA 是否接受同一种语言。证明这一点，你可能会在可计算性课程中学习。现在，我们只提出这个思路供你思考： 对两个 DFA 分别进行最小化。如果得到的机器结点数相同，并且它们的图同构（也就是说，结构以及转移的标记完全相同），那么它们必然接受同一种语言。 .. odsascript:: DataStructures/FLA/FA.js .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/FA/DFAMinFS.js .. odsascript:: lib/underscore.js .. odsascript:: DataStructures/FLA/AddQuestions.js .. odsascript:: AV/PIFLA/FA/DFAMinEx1FS.js .. odsascript:: AV/PIFLA/FA/DFAMinEx2FS.js
