NFA (非确定有限自动机)

• NFA 代表非确定有限自动机。对于给定的正则语言，构造 NFA 比 DFA 更容易。
• 当存在从当前状态到下一状态的特定输入的多个路径时，有限自动机被称为 NFA。
• 每个 NFA 并非都是 DFA，但每个 NFA 都可以转换为 DFA。
• NFA 的定义方式与 DFA 相同，但有两个例外，它包含多个下一状态，并且它包含 ε 转换。

在下图中，我们可以看到，对于输入 a，从状态 q0 开始，有两个下一状态 q1 和 q2，类似地，对于输入 b，从 q0 开始，下一状态是 q0 和 q1。因此，对于特定的输入，下一个状态无法确定或确定。因此，这种 FA 称为非确定有限自动机。

NFA 的形式定义

NFA 也有五个状态，与 DFA 相同，但具有不同的转换函数，如下所示

δ: Q x ∑ →2Q

其中，

NFA 的图形表示

NFA 可以用称为状态图的有向图表示。其中

1. 状态由顶点表示。
2. 标有输入字符的弧显示转换。
3. 初始状态用箭头标记。
4. 最终状态用双圆圈表示。

示例 1

解决方案

转换图

转移表

在上面的图中，我们可以看到，当当前状态是 q0 时，在输入 0 时，下一个状态将是 q0 或 q1，在输入 1 时，下一个状态将是 q1。当当前状态是 q1 时，在输入 0 时，下一个状态将是 q2，在输入 1 时，下一个状态将是 q0。当当前状态是 q2 时，在输入 0 时，下一个状态是 q2，在输入 1 时，下一个状态将是 q1 或 q2。

示例 2

∑ = {0, 1} 的 NFA 接受所有包含 01 的字符串。

解决方案

转移表

示例 3

∑ = {0, 1} 且接受长度至少为 2 的所有字符串的 NFA。

解决方案

转移表