非确定有限自动机

---

---

在 NDFA 中，对于特定的输入符号，机器可以移动到机器中任何状态的组合。换句话说，无法确定机器移动到的确切状态。因此，它被称为非确定自动机。因为它具有有限数量的状态，所以该机器被称为非确定有限机或非确定有限自动机。

NDFA 的形式化定义

NDFA 可以用 5 元组 (Q, ∑, δ, q₀, F) 表示，其中 -

• Q 是一个有限的状态集。

• ∑ 是一个有限的符号集，称为字母表。

• δ 是转移函数，其中 δ: Q × ∑ → 2^Q

  (这里取 Q 的幂集 (2^Q)，因为在 NDFA 的情况下，从一个状态可以发生到 Q 状态的任何组合的转移)

• q₀ 是处理任何输入的初始状态 (q₀ ∈ Q)。

• F 是 Q 的最终状态集 (F ⊆ Q)。

NDFA 的图形表示：（与 DFA 相同）

NDFA 用称为状态图的有向图表示。

• 顶点表示状态。
• 用输入字母标记的弧表示转移。
• 初始状态用空单个传入弧表示。
• 最终状态用双圆圈表示。

示例

令一个非确定性有限自动机为 →

• Q = {a, b, c}
• ∑ = {0, 1}
• q₀ = {a}
• F = {c}

转移函数 δ 如下所示 -

它的图形表示如下所示 -

DFA 与 NDFA

下表列出了 DFA 和 NDFA 之间的区别。

接受器、分类器和变换器

接受器（识别器）

计算布尔函数的自动机称为接受器。接受器的所有状态要么接受要么拒绝给它的输入。

分类器

分类器具有两个以上的最终状态，并且在终止时给出单个输出。

变换器

根据当前输入和/或先前状态产生输出的自动机称为变换器。变换器可以分为两种类型 -

• 米利机 - 输出取决于当前状态和当前输入。

• 穆尔机 - 输出仅取决于当前状态。

DFA 和 NDFA 的可接受性

当且仅当 DFA/NDFA 从初始状态开始，在完全读取字符串后结束于接受状态（任何最终状态）时，DFA/NDFA 接受一个字符串。

如果 DFA/NDFA (Q, ∑, δ, q₀, F) 接受字符串 S，则

δ*(q₀, S) ∈ F

DFA/NDFA 接受的语言L 是

{S | S ∈ ∑* 且 δ*(q₀, S) ∈ F}

如果 DFA/NDFA (Q, ∑, δ, q₀, F) 不接受字符串 S′，则

δ*(q₀, S′) ∉ F

DFA/NDFA 不接受的语言 L′（接受语言 L 的补集）是

{S | S ∈ ∑* 且 δ*(q₀, S) ∉ F}

示例

让我们考虑图 1.3 中所示的 DFA。从 DFA 中，可以导出可接受的字符串。

上述 DFA 接受的字符串：{0, 00, 11, 010, 101, ...........}

上述 DFA 不接受的字符串：{1, 011, 111, ........}