2.3 DFA 与 DFA 最小化
确定性有限自动机，也就是 DFA，是正则语言判定过程的可执行形式。它每次读取一个输入符号，维护一个当前状态，沿着唯一转移前进，并在输入结束时根据最终状态接受或拒绝。正是这种简单性让 DFA 在词法分析中非常有价值：扫描器（scanner）可以用一个紧凑循环处理字符流。
形式化地，DFA 是一个五元组：
(Q, Σ, δ, q0, F)其中：
Q是有限状态集合。Σ是有限输入字母表。δ是转移函数（transition function）。q0是开始状态。F是接受状态集合。
转移函数是确定性的核心。对于每个状态和输入符号，DFA 都有一个下一状态。有些定义要求转移函数是完全（total）的；所有缺失转移都显式指向陷阱状态（trap state）。编译器实现里常使用表格，“没有转移”可能表示当前词法单元（token）尝试失败。
识别包含 001 的 DFA
令 Σ = {0, 1}，目标语言是 ，也就是所有包含子串（substring）001 的二进制串。一个有效的状态设计是：记住已经读过内容的最长后缀，并且这个后缀同时是 001 的前缀。
q0: 当前没有匹配到有用前缀
q1: 最近后缀是 "0"
q2: 最近后缀是 "00"
q3: 已经看到 substring "001"转移表如下：
| 当前状态 | 输入 0 | 输入 1 |
|---|---|---|
| q0 | q1 | q0 |
| q1 | q2 | q0 |
| q2 | q2 | q3 |
| q3 | q3 | q3 |
开始状态是 q0，唯一接受状态是 q3。一旦自动机到达 q3，它会一直停留在那里，因为这个串已经包含 001；后续字符无法撤销这个事实。
像词法分析器一样运行 DFA
表驱动扫描器（table-driven scanner）的概念结构通常像这样：
state = start
for each character c:
state = transition[state, class(c)]
if state is accepting:
remember this position and token kind扫描器可能维护不止一个信息：当前状态、最近一次接受状态、最近一次接受位置、源码偏移（offset）、行列号和词法单元优先级。但自动机本身仍然很简单。每个输入字符都会更新当前状态。
这种风格速度很快，因为运行时工作很规则：分类字符，查询转移，更新状态，必要时记录接受位置。词法分析器生成器（lexer generator）会优化表布局、合并字符类、压缩稀疏行，或者直接生成代码，但概念模型仍然是 DFA。
等价状态
两个 DFA 状态如果无法被任何未来输入区分，就称它们等价。更精确地说，如果对于每个字符串 w，从状态 p 读入 w 的接受结果与从状态 q 读入 w 的接受结果完全相同，那么 p 和 q 等价。
这个定义比“名字相似”或“都是非接受状态”强得多。接受/非接受状态提供第一轮明显拆分，但最终分区由转移行为决定。
例如，假设两个状态在输入 0 时都转移到某个接受分区，在输入 1 时都转移到同一个非接受分区，并且它们自己的接受状态也相同，它们可能等价。但如果其中一个状态能通过未来输入 01 到达接受状态，而另一个不能，它们就必须分开。
分区细化最小化
DFA 最小化（DFA minimization）会构造一个识别同一语言的最小 DFA，除了状态重命名之外它是唯一的。常见算法使用分区细化（partition refinement）：
1. 如果需要，先移除不可达状态。 2. 把状态按接受和非接受分成两组。 3. 重复拆分那些在某个输入符号下转移到不同分区的组。 4. 当没有组能继续拆分时停止。 5. 每个最终分组变成最小 DFA 的一个状态。
这个算法是机械的，但直觉很清楚：如果两个状态在某些未来输入上行为不同，就一定有办法区分它们。如果没有任何未来输入能区分它们，它们就是同一行为的冗余副本。
最小化对生成扫描器很重要，因为很多词法单元 regex 会被合并成一个自动机。子集构造（subset construction）生成的原始 DFA 可能包含很多状态。最小化和表压缩可以减少内存占用，改善缓存（cache）行为，也让生成代码更容易推理。
状态表示信息，不表示画图风格
识别 001 时，状态保存“已读串中同时是模式前缀（pattern prefix）的最长后缀”。读到 00 后再读 0，有用后缀仍是 00，因此 q2 自循环；读到 001 后性质永久成立，q3 是吸收状态（absorbing state）。这种设计能推广到关键字、定界符和字符串匹配。
最小化先删不可达状态，再用见证后缀（witness suffix）区分状态：若追加 w 后一边接受一边拒绝，w 证明不能合并。分区细化时记录每次拆分的符号，能解释生成扫描器的行为变更。
词法分析器现实
词法单元 DFA 通常记录最后接受状态/偏移。它可穿过非接受状态后回退到最后接受位置，因此能区分 = 与 == 而不提前返回 =。