元数据卡
- 前置知识：第1章（形式语言与自动机概述）
- 预计时间：50 分钟
- 核心难度：进阶
- 阅读模式：高度专注（建议 50 分钟+）
- 完成标志：能手画 DFA/NFA 并相互转换，能通过正则表达式构建 NFA
咒术高塔的第二层：墙上画满了箭头和圆圈，像一张巨大的路径图。你发现每条路径都对应一类"咒语模板"——只要咒语匹配某个模板，就能自动触发对应的效果。这一层教你的，正是如何设计这种"模板匹配"的机器。
你的进度
上一章你掌握了"一种语言就是一个字符串集合"的观点。但你是手工在验证——把一串字符拿进来，对着规则逐一核验。这个工作太慢了，而且容易出错。你需要一只能自动识别咒语的机器。
你的任务
这一章，你从两种自动机——确定有限自动机（DFA）和非确定有限自动机（NFA）——入手，解决"如何机械地判断一个串是否属于某正则语言"的问题。你会先学会 DFA 的构造，然后看到 NFA 对"人设计规则"的便利性，最后用 Thompson 构造法将正则表达式转化为 NFA——这是编译器词法分析器的理论基础。
破局 · 溯源
你面前有两条咒语规则：
规则 A：以 a 开头，后跟任意个 b，以 b 结尾 规则 B：包含至少一个 a 和至少一个 b，且 a 必须在 b 之前
你对着规则逐条核对每句咒语，很快晕头转向了。因为规则 B 中说"包含至少一个 a 和至少一个 b"——你不能确定正在读的串是否已经包含了这些字符。
D（-）你需要的是一种"有记忆"的检查流程：它不需要记住整个串，只需要知道当前处于哪种模式。这正是状态的用途。
DFA：确定有限自动机
一个 DFA 由五部分组成：
- Q：有限状态集合
- ∑：输入字母表
- δ：转移函数 Q x ∑ -> Q（每个状态 + 每个字符，恰好有一条出路）
- q0：起始状态
- F：接受状态集合
DFA 的"确定"体现在：给定当前状态和下一个字符，下一步是唯一的。这就像一条单向通道，每个路口只有一个方向标。
下面是一个检查"c 语言整数标识符（以数字开头）"的 DFA——实际 C 标准中标识符不能以数字开头，这里我们只演示自动机：
状态集合：Q = {q0, q1}
字母表：∑ = {d（数字）, o（其他）}
转移函数：
δ(q0, d) = q1
δ(q0, o) = q0
δ(q1, d) = q1
δ(q1, o) = q0
起始状态：q0
接受状态：{q0, q1}（所有状态都是接受状态，因为任何包含数字的串都被接受）这个 DFA 一次从左到右扫描输入，每个字符推一次状态。时间 O(n)，空间 O(1)。你调不出更快的算法了，因为每组输入你至少要看一遍才知道它是什么。
NFA：非确定有限自动机
现在改用更灵活的方式。NFA 和 DFA 的唯一区别是：从同一个状态读同一个字符，可以有多条出路，甚至是"空转移"（不需要读字符就跳状态）。
NFA 示例：识别 "以 a 开头、以 b 结尾"
状态图：q0 --a--> q1 --b--> q2 (接受)
q1 --a--> q1
q1 --b--> q1
对输入 "aab"：
从 q0 读 a -> q1
读 a -> q1（可以走自环）
读 b -> q1 或 q2（两条路）NFA 的"非确定"听起来不靠谱——机器怎么走多条路？在理论上，NFA 会"尝试所有可能路径"，只要有一条到达接受状态就算接受。在工程上，我们绝不用 NFA 作为执行模型，而是把它当成"设计中间体"。
NFA 是给人设计的。DFA 是给机器执行的。
NFA -> DFA：子集构造法
把 NFA 转换成 DFA 的算法叫作"子集构造法"，核心思想很简单：
DFA 的每个状态 = NFA 的多个状态的幂集（也就是 NFA 所有可能状态的集合）
具体步骤：
- 从 NFA 的起始状态出发，加上所有通过 ε（空）转移能到达的状态，作为 DFA 的起始状态
- 对这个状态集合，针对每个输入字符，算出 NFA 能到达的"下一个状态集合"
- 把每个不同的"状态集合"当作 DFA 的一个新状态
- 重复直到没有新状态产生
这个转换最坏会导致指数级的状态增长（DFA 的状态数可能是 NFA 的 2 的 n 次方倍），但在实际的正则表达式场景中，DFA 状态数通常可控。
正则表达式 -> NFA：Thompson 构造法
这是你在词法分析中最常用的操作：拿到一个正则表达式，自动构造对应的 NFA。Ken Thompson 在 1968 年给出了这组构造规则：
基本规则：
字符 a -> q0 --a--> q1
空串 -> q0 （空转移连到 q1）
复合规则：
连接 AB ：把 A 的接受状态通过空转移连到 B 的起始
选择 A|B ：从新起始状态并发空转移到 A 和 B 的起始
重复 A* ：在 A 的首尾之间加空转移自环你不需要记忆细节，但应该理解它的精神：正则表达式的每种语法结构——连接、选择、重复——都有对应的 NFA 片段，这些片段可以用空转移拼成完整的 NFA。这个构造法是线性大小的，不会导致指数爆炸。
第一层：够用——手画 DFA 识别简单 token
你在一台 C 编译器的词法分析器里需要识别三种 token：关键字 if、标识符（字母开头后跟字母数字）、数字常量。你为每种写一个正则表达式，然后构造对应的 DFA，最后把它们合并成一个大型的 DFA——每个 DFA 的最终状态贴上对应的 token 类型标签。词法分析器扫描输入时，就走在这样一个大 DFA 上，走到哪步就发射哪个 token。
正则：
if -> "if"
标识符 -> [a-zA-Z][a-zA-Z0-9]*
数字 -> [0-9]+
合并 DFA 的一部分：
q0 --i--> q1 --f--> qif（发射 IF token）
q0 --字母--> qid --字母/数字--> qid（发射 ID token）
q0 --数字--> qnum --数字--> qnum（发射 NUM token）第二层：深入——为什么 NFA 比 DFA 更"高级"但工程上更弱
DFA 的执行效率是无敌的：每个输入字符一次查表，状态固定。但 DFA 的构造代价高——对于复杂的正则表达式，DFA 状态会爆炸（比如 (a|b)*a(a|b)(a|b) 这种中等复杂度的模式，DFA 状态数已经是 NFA 的几倍了）。更糟糕的是，某些正则表达式对应的 DFA 大小是正则表达式长度的指数级。
所以现代词法分析器（如 flex、re2c）的典型做法是：用 NFA 作为内部表示做构造，但在最终产物中分解或缓存 DFA 状态。有些用"NFA 模拟"（直接跟踪 NFA 的当前状态集合），牺牲一点速度换取构造时间和内存。
大多数时候你不需要自己实现这些——lex/flex 或者手写的词法分析器调用现成的正则库就够了。但这层理解让你知道：你的词法分析器在使用最可能快的工具来处理最表层的语言结构。
常见陷阱
陷阱1：认为 NFA 比 DFA 功能更强。 NFA 和 DFA 在表达能力上是完全等价的——它们都描述正则语言。任何 NFA 都有等价的 DFA，反之亦然。区别是大小和构造难度，不是表达能力。
陷阱2：子集构造法中不理解"空闭包"。 NFA 中的 ε 转移可能导致一个状态不需要任何输入就能跳到下一状态。在子集构造中，一个状态集合必须包含所有能通过 ε 转移到达的状态。漏了这一步，你的 DFA 就会漏识别。
陷阱3：混淆词法分析器使用的"最长匹配"规则。 即使有了 DFA，词法分析器在应对 if 关键字和 ifx 这样的标识符时，会用"最长匹配"规则——它持续读入字符直到 DFA 无路可走，然后回退到最后一次处于接受状态的位置。这不是 DFA 本身的行为，是词法分析器的工程策略。
通关挑战
热身（5分钟）： 手画一个 DFA，识别由 a 和 b 组成且 "a 的数量为奇数" 的所有串。状态只有两个（偶数个 a、奇数个 a）。
挑战（30分钟）： 给定正则表达式
(a|b)*abb，用 Thompson 构造法画出 NFA，再用子集构造法转换为 DFA。验证aabb和abba能否分别被识别。观察： 打开 Linux 终端，运行
man regex查看 POSIX 正则表达式的七种子表达式。看看哪些结构可以用 Thompson 构造法直接映射，哪些需要扩展（比如[a-z]范围匹配、反向引用等——后者已经超出了正则语言的范围）。
旅人笔记
DFA 是静态的高效执行者，NFA 是灵活的设计中间体；正则表达式通过 Thompson 构造法转化为 NFA，再由子集构造法转化为 DFA——这就是词法分析的理论骨架。
下一站预告
正则语言只能描述"平坦"的字符串结构。下一章，你需要更强的文法来处理嵌套和递归——比如括号匹配。那将是上下文无关文法和下推自动机的舞台。