DFA 与 NFA

一、前言

FA（Finite Automata，有穷状态自动机）是在有限个输入的情况下，在这些状态中转移并期望最终达到终止状态。有穷状态自动机根据确定性可以分为“确定有穷状态自动机”（DFA - Deterministic finite automaton）和“非确定有穷自动机”（NFA - Non-deterministic finite automaton）。

DFA 通俗点就是一个输入一个输出；NFA 通俗点就是一个输入多个输出。

二、解释

DFA 状态机由一个5-tuple 组成(Q, ∑, δ, q0, F) ，它们的解释如下：

• Q 是一组有限的状态集合
• ∑ 是一组有限的符号，称为字母表
• δ 是转换函数，其中 δ：Q × ∑ → Q
• q0 是任何输入的初始状态 (q0 ∈ Q)，即初始状态。
• F 是 Q (F ⊆ Q) 的一组最终状态，即终止状态。

DFA 的图形表示如下：
DFA 由称为状态图的有向图表示。

• 顶点代表状态。
• 标有输入字母表的弧线显示了转换。
• 初始状态由一个空的单个传入弧表示。
• 最终状态由双圆圈表示。

举个例子：
我们设定一个 DFA 如下 →

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

并且转换函数δ如下表所示 -

Present State	Next State for Input 0	Next State for Input 1
a	a	b
b	c	a
c	b	c

它的图形表示如下 -

DFA转换图

三、代码

其实实际工作中，一堆 状态机转换，只是我们没那么严谨罢了，没有把它对应到 DFA 上。