非确定性有限自动机

---

在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 之间的差异。

接受器、分类器和转换器

接受器（识别器）

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

分类器

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

传感器

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

• Mealy Machine - 输出取决于当前状态和当前输入。

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

DFA 和 NDFA 的可接受性

如果从初始状态开始的 DFA/NDFA 在完全读取字符串后以接受状态（任何最终状态）结束，则字符串被 DFA/NDFA 接受。

字符串 S 被 DFA/NDFA 接受 (Q, Σ, δ, q ₀ , F), iff

δ*(q ₀ , S) ∈ F

DFA/NDFA接受的语言L是

{S | S ε Σ* 且 δ*(q ₀ , S) ε F}

DFA/NDFA 不接受字符串 S′ (Q, Σ, δ, q ₀ , F), iff

δ*(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, ........}