6. NFA：非确定性有限自动机¶
6.1. 非确定性有限自动机¶
我们经常需要做出决策。有时，一旦做出决定，我们就无法撤销它。有时，我们可以回头，改变主意，做出另一种选择。但即便如此，我们仍然不得不花费时间去探究那条错误的路径。
想象一下，当我们来到一个决策点时，我们可以克隆自己，同时遵循两条路径，然后“变成”那个结果更好的版本。这难道不是对我们生活的巨大升级吗？
这在现实生活中会涉及一些相当复杂的哲学问题。但在有限自动机的世界里， 非确定性 的概念其实可以被具体化。在本模块中，我们将研究使 FA 非确定性意味着什么，以及这最终是否真的重要。
6.2. NFA 与 DFA：哪个更强大？¶
现在我们准备好迎接主要内容：证明每个 NFA 都可以转换为 DFA，因此这两种机器类型具有同等的能力。我们通过构造性证明来完成这一点：这里有一个算法可以将任何 NFA 转换为等价的 DFA。
直观理解：给定 \(M_N\) 中的一个状态和一个字符，你可以到达 \(M_N\) 中状态的某个子集。将 该子集 视为 \(M_D\) 中的一个状态。 \(M_N\) 状态集合的子集数量是有限的：即 \(M_D\) 状态集合的幂集的成员。
6.3. NFA 到 DFA 转换示例¶
6.4. 结论¶
为 DFA 添加非确定性能力并不会带来接受语言的新能力。NFA 能接受的语言集合与 DFA 能接受的语言集合完全相同。我们通过构造性方法证明了这一点：每个 DFA 自动就是一个没有非确定性的 NFA，因此 DFA 显然不能接受 NFA 无法接受的语言。而任何 NFA 都可以通过算法转换为 DFA。所以 NFA 也不能接受 DFA 无法接受的语言。由于 DFA 类能接受的语言集合与 NFA 类能接受的语言集合完全相同，我们说这两者是 等价 。
那么，NFA 是一个有用的概念吗？为什么要引入它们呢？首先，起初并不明显的是，它们在可接受的新语言方面并没有增加新的能力。（有时非确定性在其他上下文中会产生功能上的差异。）因此，我们必须通过推导来说服自己这是真的。其次，NFA 往往比等价的 DFA 更“简单”易懂。查看转换示例的结果，并自行判断哪一个更容易让你推导出对应的语言。或者，尝试从头开始为该语言编写一个 DFA。第三，在本学期中我们将介绍一些其他转换算法，如果目标是 NFA 而不是 DFA，这些算法会更容易理解。第四，非确定性是一个有用的概念，有助于简化我们稍后将涵盖的其他概念。一个很好的例子将是所谓 NP 完全 问题的研究（其中 NP 代表非确定性多项式）。
