编译原理冲刺 · 第 03 课 ⏱ 冲刺模式 · ≤1周

正规式 ↔ NFA ↔ DFA

词法分析的数学工具，最爱考的机械题之一。对应教材第 3 章 3.3。

🎯 本课唯一目标

会把正规式画成 NFA，再用子集构造法把 NFA 确定化成 DFA（会列子集转换表）。

为什么学它？　这是全景图里"词法分析"格子的核心。考试几乎必有一道"给正规式 → 构造 DFA"的题，纯机械套路，练熟就是满分。

一、三个主角

正规式：用 ε、单字符、|（或）、连接、*（闭包） 描述一个字符串集合。优先级 * > 连接 > |。
有限自动机 FA = (S, Σ, δ, s₀, F)：状态集 S、输入字母表 Σ、转移 δ、初态 s₀、终态集 F。
DFA（确定）：无 ε 边，每个(状态,输入)唯一下一状态。NFA（不确定）：可有 ε 边，一个输入可到多个状态。

三者等价：描述同一类语言（正规语言）。正规式 → NFA → DFA 是标准流水线。

二、正规式 → NFA（Thompson 构造）

把正规式拆成 5 种基本块，每种给一小段 NFA，再拼起来^[1]：

ε ：    →(○)─ε→(◎)
单字符a：→(○)─a→(◎)
r | s ：新初态 ─ε→ r 的NFA ；─ε→ s 的NFA ；两者终态 ─ε→ 新终态
r s   ：r 的终态 ─ε→ s 的初态（首尾相接）
r *   ：新初态 ─ε→ r初态、─ε→ 新终态；r终态 ─ε→ r初态(循环)、─ε→ 新终态

三、NFA → DFA：子集构造法

核心思想：DFA 的一个状态 = NFA 的一组状态（子集）。两个工具函数：

ε-closure(I)：从 I 里的状态出发，只沿 ε 边能到达的所有状态（含 I 自身）。
move(I, a)：I 里的状态沿一条标 a 的边到达的状态集合。

⚑ 子集构造法步骤

① DFA 初态 = ε-closure({s₀})，命名为 A。

② 对每个已得子集 T、每个输入符 a：算 U = ε-closure(move(T,a))。

③ U 若是新子集就加进来（命名 B、C…），并在转换表里登记 T --a--> U。

④ 直到没有新子集。含原 NFA 终态的子集 = DFA 终态。

四、老师示范一题（经典）

例题　构造与正规式 (a|b)*abb 等价的 DFA。

第 1 步　Thompson 构造 NFA，给状态编号 0–10（10 为终态）：

0 ─ε→ 1, 7      1 ─ε→ 2, 4      2 ─a→ 3      4 ─b→ 5
3 ─ε→ 6         5 ─ε→ 6         6 ─ε→ 1, 7
7 ─a→ 8         8 ─b→ 9         9 ─b→ 10(终)

第 2 步　子集构造。初态 A = ε-closure({0}) = {0,1,2,4,7}。逐个求 ε-closure(move(·,a/b))：

DFA状态	= NFA 子集	输入 a	输入 b
A	{0,1,2,4,7}	B	C
B	{1,2,3,4,6,7,8}	B	D
C	{1,2,4,5,6,7}	B	C
D	{1,2,4,5,6,7,9}	B	E
E（终）	{1,2,4,5,6,7,10}	B	C

DFA状态

= NFA 子集

输入 a

输入 b

{0,1,2,4,7}

{1,2,3,4,6,7,8}

{1,2,4,5,6,7}

{1,2,4,5,6,7,9}

E（终）

{1,2,4,5,6,7,10}

第 3 步　E 含原终态 10，故 E 为终态。得 DFA（5 个状态）：

     a        b
A ─→ B    A ─→ C
B ─→ B    B ─→ D
C ─→ B    C ─→ C
D ─→ B    D ─→ E ★终态
E ─→ B    E ─→ C

💡 检验：看 abb 这条路 A —a→ B —b→ D —b→ E（终态），✓ 被接受。下一课我们把这个 DFA 再最小化。

五、你来做

1. 正规式运算中，优先级最高的是？

2. NFA 区别于 DFA 的关键在于，NFA 一个输入符可以？

3. 子集构造法中，DFA 的一个状态对应 NFA 的什么？

4. 计算 ε-closure(I) 时，从 I 出发只能沿什么走？

5. 正规式、NFA、DFA 三者的关系是？

得分：0 / 5

正规式 →(Thompson)→ NFA →(子集法)→ DFA
DFA一状态 = NFA一子集；含原终态的子集 = 新终态

📺 主源推荐　哈工大《编译原理》词法分析相关讲 — 中国大学MOOC；子集构造法权威步骤可参斯坦福龙书讲义^[1]。

🙋 子集表的某一步算不出来？把你卡住的子集发我，我一步步带你算。也可以要我再出一道 (0|1)*01 之类的练手题。

[1] 正规式/NFA/DFA 定义、Thompson 构造、子集构造法：陈火旺《程序设计语言编译原理》3.3；交叉印证龙书（Aho 等）配套讲义。(a|b)*abb 为龙书经典例。