3.2.1. NFA：非确定性有限自动机¶

定义：

将 NFA 定义为 \((Q, \Sigma, \delta, q_0, F)\) ，其中

• \(Q\) 是一个有限的状态集

• \(\Sigma\) 是输入字母表（一个有限集）

• \(q_0\) 是初始状态（ \(q_0 \in Q\) ）

• \(F \subseteq Q\) 是一组终态

• \(\delta: Q \times(\Sigma \cup \{\lambda\}) \rightarrow 2^Q\) （此处 \(2^Q\) 表示 \(Q\) 的幂集）

与 DFA 的具体区别在于，DFA 的 \(\delta\) 结果是某个状态 \(q \in Q\) ，而 NFA 的 \(\delta\) 结果是 \(Q\) 的任意子集。

非确定性 表示它允许选择。从某个状态在输入 \(b\) 时， \(\delta\) 可能包含转移到多个状态的转换。

示例：

在此示例中， \(\delta(q_0, a) = \{q_1, q_2\}\) 。（因此， \(\delta\) 不再满足函数的数学定义！）

希望这个容易理解：我们有两个不相交的路径，实际上给出了两个语言的并集： \(L = \{aa\} \cup \{ab^nb \mid n \ge 0\}\) 。

示例：

\(L = \{(ab)^n \mid n>0\} \cup \{a^nb \mid n>0\}\) 。

定义： \(q_j \in {\delta}^{*}(q_i,w)\) 当且仅当存在一条从 \(q_i\) 到 \(q_j\) 、标记为 \(w\) 的路径。

从前面的示例：

\(\delta^{*}(q_0, ab) = \{q_5, q_6, q_1\}\) 。

\(\delta^{*}(q_0, aba) = \{q_3\}\) 。

定义：对于 NFA \(M\) ， \(L(M)= \{w \in {\Sigma}^{*} \mid \delta^{*}(q_0,w) \cap F \neq \emptyset \}\)

这意味着什么？这意味着该自动机接受所有来自由字母表 \(\Sigma\) 生成的所有可能字符串集合中的字符串 \(w\) ，条件是：从起始状态（ \(q_0\) ）出发，在读入 \(w\) 后可达的状态集合与终态集合的交集非空。

注意，存在 \(w\) 可能出错的路径并不重要。重要的是，至少存在一种方式使 \(w\) 正确。

为什么需要非确定性？它使得描述有限自动机更加容易。“更容易”意味着什么？它可能意味着在观察时更易于理解。或者可能对开发者而言更易于编写。或者可能规模更小（就状态数量而言）。或者可能更高效（但大概并非如此，因为模拟非确定性可能开销很大）。从性能角度来看，确定一个字符串是否被接受可能需要很长时间来尝试所有可能性。但是，我们现在关心的只是存在性，而非性能。

3.2.2. NFA 与 DFA：哪一个更强大？¶

考虑以下 NFA。

这个 NFA 能转换为 DFA 吗？

是的，因为这里就有一个。请注意，状态的命名是为了帮助理解它们与原始 NFA 的关系。

直觉：给定 \(M_N\) 中的一个状态和一个字符，你可以到达 \(M_N\) 中状态的某个子集。将 该子集 视为 \(M_D\) 中的一个状态。 \(M_N\) 个状态的集合只有有限多个子集：它们将是 \(M_D\) 个状态的幂集的成员。

示例：

让我们从起始状态开始。 \(M_N\) 中的 Closure( \(q_0\) ) 是 \(\{q_0, q_1, q_2\}\) 。因此这就是起始状态。

例如：从 \(M_D\) 状态 \(q_0,q_1,q_2\) 出发，确定从这些状态中的任意一个在输入字母 \(a\) 上可达的状态子集。该子集即为 \(q_3,q_4\) 。

答案：

Settings

Saving...
Server Error
Resubmit

结论：NFA 并未增加新的能力。那么为何还要引入这一概念？

• 首先，它们是否相同并不显而易见。NFA 是一个有用的概念。

• NFA 往往比等价的 DFA“更小”且“更简单”。（至少在状态数和转换数方面是这样。但或许 NFA 所描述的语言对人来说更难理解。）

• 在整个学期中，我们将大量进行从一种机器类型到另一种机器类型的转换。当目标机器是 NFA 时，转换过程可能更容易理解，而且我们知道这总是可以进一步转换为 DFA。