有穷自动机（上）：DFA、NFA 与等价转换

有穷自动机（Finite Automaton）是编译原理中词法分析的理论基石。它用有限个状态和状态之间的转移，刻画了一类被称为「正规语言」的计算模型。本文从确定的 DFA 出发，引入不确定的 NFA，再通过子集构造法和分割法，打通 NFA → DFA → 最简 DFA 的完整转换链路。

---

一、DFA：确定的计算模型

确定的有穷自动机（Deterministic Finite Automaton，DFA）之所以「确定」，是因为在任意状态下，面对任意输入符号，下一步转移到哪个状态是唯一确定的。

形式化定义

一个 DFA 由五元组 M = (Q, Σ, δ, q₀, F) 定义：

符号	含义	本例取值
Q	有穷状态集合	{q₀, q₁, q₂}
Σ	输入字母表	{a, b}
δ	状态转移函数 Q × Σ → Q	见下表
q₀	初始状态	q₀
F	终态集合	{q₂}

例题：设计一个 DFA，接受所有以 abb 结尾的字符串。

转移表：

状态	a	b
→ q₀	q₁	q₀
q₁	q₁	q₂
*q₂	q₁	q₀

DFA 的识别过程非常直观：从初态出发，逐个读入输入符号，沿转移边移动。读完所有符号后，若当前状态属于终态集合 F，则接受该字符串；否则拒绝。

---

二、NFA：引入不确定性的动机

DFA 虽然简洁，但直接从语言描述设计 DFA 往往很困难。不确定的有穷自动机（Nondeterministic Finite Automaton，NFA）放宽了限制，允许：

1. 同一状态对同一输入符号有多条转移（甚至零条）
2. ε 转移：不消耗任何输入符号即可转移

形式化定义

NFA 同样由五元组 M = (Q, Σ, δ, q₀, F) 定义，但转移函数变为 δ: Q × (Σ ∪ {ε}) → 2^Q——即转移到状态集合而非单个状态。

DFA vs NFA 核心差异

维度	DFA	NFA
转移目标	单个状态	状态集合
ε 转移	无	有
设计难度	高（需直接想到所有状态）	低（局部拼接即可）
识别效率	O(n)	需回溯或并行模拟
表达能力	等价于 NFA	等价于 DFA

例题：设计一个 NFA，接受语言 a*bb（零个或多个 a 后跟两个 b）。

这个 NFA 只有 4 个状态，设计思路是：q₀ 上的 a 自环处理 a*，ε 转移到 q₁ 表示「随时可以开始匹配 bb」。这种「局部拼接」的思维方式，正是 NFA 比 DFA 更容易设计的根本原因。

---

三、从 NFA 到 DFA——子集构造法

子集构造法的核心思想：将 NFA 在某一时刻可能处于的所有状态打包成一个集合，这个集合就是 DFA 的一个状态。NFA 的不确定性被「状态集合」这个更高层的抽象所消解。

算法步骤

1. 计算初态 q₀ 的 ε-闭包（从 q₀ 出发仅通过 ε 转移能到达的所有状态），作为 DFA 的初态
2. 对于每个已生成的 DFA 状态（即 NFA 状态集合）和每个输入符号 a：
   • 计算该集合中每个状态经 a 能到达的状态集合
   • 再取该集合的 ε-闭包
   • 得到一个新的 DFA 状态
3. 重复步骤 2，直到不再产生新状态
4. 包含 NFA 终态的 DFA 状态即为 DFA 的终态

例题：将上节的 NFA 转换为 DFA

NFA 回顾：Q = {0, 1, 2, 3}，Σ = {a, b}，初态 0，终态 {3}。

转移关系：

• 0 --a--> 0
• 0 --ε--> 1
• 1 --b--> 2
• 2 --b--> 3

第一步：计算 ε-closure(0)。

从 0 出发，经 ε 转移可到 1。因此 ε-closure(0) = {0, 1}，记为 DFA 状态 A。

第二步：从 A = {0, 1} 出发。

• 输入 a：δ(0, a) = {0}，δ(1, a) = ∅。合并得 {0}，ε-closure({0}) = {0, 1} = A。
• 输入 b：δ(0, b) = ∅，δ(1, b) = {2}。合并得 {2}，ε-closure({2}) = {2}，记为 B。

第三步：从 B = {2} 出发。

• 输入 a：δ(2, a) = ∅ → ∅，记为死状态 D。
• 输入 b：δ(2, b) = {3}，ε-closure({3}) = {3}，记为 C（终态）。

第四步：从 C = {3} 出发。

• 输入 a 和 b 均无转移 → 均到 D。

第五步：从 D = ∅ 出发。

• 输入 a 和 b 均到 D。

子集构造完成。DFA 状态转移表：

DFA 状态	NFA 状态集	a	b
→ A	{0, 1}	A	B
B	{2}	D	C
*C	{3}	D	D
D	∅	D	D

DFA 状态图：注意状态 A 上的 a 自环——它来自原 NFA 中 q₀ 的 a 自环。

---

四、DFA 的最小化——分割法

子集法得到的 DFA 可能包含冗余状态（如上例中的死状态 D 在某些场景下可与其它状态合并）。分割法（也称 Hopcroft 算法）能将 DFA 化简为状态数最少的等价 DFA。

核心思想

1. 初始划分：将所有状态分为两组——终态组和非终态组
2. 逐步细分：对于当前划分中的每一组，检查组内各状态对每个输入符号的转移是否落入同一目标组。若某状态「掉队」（转移到不同组），则将其拆分出去
3. 重复直到没有组可以再细分

例题：化简上节得到的 DFA

DFA 状态：A（初态）, B, C（终态）, D（死状态）。

初始划分：Π₀ = { {C}, {A, B, D} }

第一轮：检查非终态组 {A, B, D}。

状态	δ(·, a) 落入	δ(·, b) 落入
A	A（非终态组）	B（非终态组）
B	D（非终态组）	C（终态组）
D	D（非终态组）	D（非终态组）

B 在 b 上的转移落入了终态组，而 A 和 D 都落入非终态组。B 被拆分。

Π₁ = { {C}, {B}, {A, D} }

第二轮：检查 {A, D}。

状态	δ(·, a) 落入	δ(·, b) 落入
A	A（{A,D} 组）	B（{B} 组）
D	D（{A,D} 组）	D（{A,D} 组）

D 在 b 上落入 {A,D} 组，而 A 落入 {B} 组。A 和 D 被拆分。

Π₂ = { {C}, {B}, {A}, {D} }

所有组均为单元素，无法再细分。该 DFA 已是最简。

子集法与分割法的对称性

维度	子集构造法	分割法
方向	NFA → DFA（膨胀）	DFA → 最简 DFA（压缩）
操作对象	NFA 状态集合 → DFA 状态	DFA 状态集合 → 等价类
核心操作	ε-closure + 转移合并	按转移目标分组 + 逐步细分
结果	确定性（消除不确定性）	最小性（消除冗余）

子集法将不确定性「摊开」为更多状态，分割法将冗余状态「压回」等价类——两者一胀一缩，恰好构成 NFA 到最简 DFA 的完整变换链。

---

五、总结

维度	DFA	NFA
转移确定性	确定	不确定（多转移 + ε）
状态数	可能指数级	通常较少
识别效率	O(n)，单遍扫描	需回溯或并行
设计难度	高	低
表达能力	等价	等价

从 NFA 到最简 DFA 的完整路径：

NFA  →  子集构造法  →  DFA  →  分割法  →  最简 DFA
(易设计)   (膨胀)      (确定)    (压缩)      (最小)

上半章我们走通了 NFA → DFA → 最简 DFA 的转换链路。但 NFA 本身从何而来？在编译器的词法分析中，我们首先用正规式描述词法规则，再通过 Thompson 构造法自动生成 NFA。下半章将聚焦正规式与有穷自动机的等价性，并以一条完整的例题走通「正规式 → NFA → DFA → 最简 DFA」的全流程。