Automata Theory 简明教程

Non-deterministic Finite Automaton

在 NDFA 中，对于特定的输入符号，机器可以移动到机器中的任何状态组合。换句话说，无法确定机器移动到的确切状态。因此，它称为 Non-deterministic Automaton 。由于它有有限数量的状态，因此机器称为 Non-deterministic Finite Machine 或 Non-deterministic Finite Automaton 。

Formal Definition of an NDFA

NDFA 可以用 5 元组 (Q, ∑, δ, q0, F) 表示，其中−

  1. Q 是一个有限的状态集。

  2. ∑ 是称为字母的符号的有限集合。

  3. δ 是过渡函数，其中 δ: Q × ∑ → 2Q（这里取 Q 的幂集 (2Q)，因为在 NDFA 的情况下，从一个状态到另一个状态，可以转换为 Q 状态的任何组合）

  4. q0 是处理任何输入的初始状态 (q0 ∈ Q)。

  5. F 是 Q 的一组终态/状态 (F ⊆ Q)。

Graphical Representation of an NDFA: (same as DFA)

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

  1. 顶点表示状态。

  2. 带有输入字母标签的弧线表示转换。

  3. 初始状态由一条空传入弧线表示。

  4. 终态由双圆圈表示。

Example

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

  1. Q = {a, b, c}

  2. ∑ = {0, 1}

  3. q0 = {a}

  4. F = {c}

过渡函数 δ 如下所示−

Present State

输入 0 时的下一状态

输入 1 时的下一状态

a

a,

b

b

c

a, c

c

b,

c

它的图形表示如下−

ndfa graphical representation

DFA vs NDFA

下表列出了 DFA 和 NDFA 之间的差异。

DFA

NDFA

一个状态的转换对于每个输入符号来说都是到一个单一的特定下一个状态。因此，它称为确定性的。

一个状态的转换对于每个输入符号来说都可以到多个下一个状态。因此，它称为非确定性的。

空字符串转换在 DFA 中看不到。

NDFA 允许空字符串转换。

可以在 DFA 中进行回溯。

在 NDFA 中，并不总是可以进行回溯。

Requires more space.

Requires less space.

如果一个字符串转换到一个最终状态，它就会被 DFA 接受。

如果所有可能的转换中至少有一个结束于最终状态，一个字符串就会被 NDFA 接受。

Acceptors, Classifiers, and Transducers

Acceptor (Recognizer)

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

Classifier

一个 classifier 有多于两个最终状态，并且在终止时给出单个输出。

Transducer

基于当前输入和/或先前状态生成输出的自动机称为 transducer 。转换器可以是两种类型：

  1. Mealy Machine - 输出既取决于当前状态又取决于当前输入。

  2. Moore Machine - 输出仅取决于当前状态。

Acceptability by DFA and NDFA

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

字符串 S 被 DFA/NDFA (Q, ∑, δ, q0, F) 接受，当且仅当

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

Example

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

acceptability of strings by dfa

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

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