非确定性有限自动机
在 NDFA 中，对于特定的输入符号，机器可以移动到机器中的任意状态组合。换句话说，无法确定机器移动到的确切状态。因此，它被称为非确定性自动机。由于它具有有限数量的状态，因此该机器被称为非确定性有限机器或非确定性有限自动机。
NDFA 的正式定义
NDFA 可以用 5 元组 (Q、∑、δ、q0、F) 表示，其中 −
Q 是一组有限的状态。
∑ 是一组称为字母表的有限符号。
δ 是转换函数，其中 δ: Q × ∑ → 2Q
（这里取 Q 的幂集 (2Q)，因为在 NDFA 的情况下，从一个状态可以转换到 Q 状态的任意组合）
q0 是处理任何输入的初始状态 (q0 ∈ Q)。
F 是 Q 的一组最终状态/状态 (F ⊆ Q)。
NDFA 的图形表示：（与 DFA 相同）
NDFA 由称为状态图的有向图表示。
- 顶点代表状态。
- 标有输入字母的弧表示转换。
- 初始状态用一个空的单传入弧表示。
- 最终状态用双圆圈表示。
示例
让非确定性有限自动机为 →
- Q = {a, b, c
- ∑ = {0, 1
- q0 = {a
- F = {c
转换函数 δ 如下所示 −
| 当前状态 | 输入 0 的下一个状态 | 输入 1 的下一个状态 |
|---|---|---|
| a | a, b | b |
| b | c | a, c |
| c | b, c | c |
其图形表示如下 −
DFA 与 NDFA
下表列出了 DFA 与 NDFA 之间的差异。
| DFA | NDFA |
|---|---|
| 从一个状态转换到每个输入符号的特定下一个状态。因此它被称为确定性。 | 从一个状态转换到每个输入符号的多个下一个状态。因此它被称为非确定性。 |
| DFA 中看不到空字符串转换。 | NDFA 允许空字符串转换。 |
| DFA 中允许回溯 | 在 NDFA 中，回溯并不总是可能的。 |
| 需要更多空间。 | 需要更少空间。 |
| 如果字符串转换到最终状态，则 DFA 接受该字符串。 | 如果所有可能的转换中至少有一个以最终状态结束，则 NDFA 接受该字符串。 |
接受器、分类器和传感器
接受器（识别器）
计算布尔函数的自动机称为接受器。接受器的所有状态都是接受或拒绝给予它的输入。
分类器
分类器具有两个以上的最终状态，并在终止时提供单个输出。
传感器
根据当前输入和/或先前状态产生输出的自动机称为传感器。传感器可以分为两种类型 −
Mealy 机 − 输出取决于当前状态和当前输入。
Moore 机 −输出仅取决于当前状态。
DFA 和 NDFA 的可接受性
当且仅当 DFA/NDFA 从初始状态开始，在完整读取字符串后以接受状态（任何最终状态）结束，则 DFA/NDFA 接受字符串。
当且仅当
δ*(q0, S) ∈ F
DFA/NDFA 接受的语言 L 是
{S | S ∈ ∑* 和 δ*(q0, S) ∈ F
字符串 S′ 不被 DFA/NDFA (Q, ∑, δ, q0, F) 接受，当且仅当
δ*(q0, S′) ∉ F
不被 DFA/NDFA 接受的语言 L′（接受语言 L 的补集）是
{S | S ∈ ∑* and δ*(q0, S) ∉ F
示例
让我们考虑图 1.3 中所示的 DFA。从 DFA 中，可以得出可接受的字符串。
上述 DFA 接受的字符串：{0, 00, 11, 010, 101, ...........>
上述 DFA 不接受的字符串：{1, 011, 111, ........>
