正规式ab*a描述的是以a开头、中间有任意多个b（包括零个）、最后再以a结尾的字符串，即形如aa,aba,abba,abbba等。在词法分析中，这类正规式常用于识别特定模式的标识符或关键字结构。
为了将该正规式转化为可执行的自动机模型，通常经历以下步骤：
正规式 → NFA（通过 Thompson 构造法）
对ab*a构造对应的 NFA：- 使用 ε-转移 表示选择和连接；
b*部分构造为一个带自环的 ε-NFA；- 整体结构为：
a后接(b)*，再接a； - 得到的状态机允许从初始状态经 ε 转移到达多个路径，具有非确定性。
NFA → DFA（子集构造法 / 子集法）
核心思想是将 NFA 中可能同时处于的多个状态组合成一个集合，作为 DFA 的单个状态。设 NFA 状态编号如下（常见构造）：
- 0: 初始状态
- 1: 第一个
a的终点 - 2→3 是
b*的循环结构（含 ε-转移） - 4: 第二个
a的起点前的跳转点 - 5: 接受状态
实际编号依具体构造略有不同，但关键步骤如下：
计算初始状态的 ε-闭包：
ε-CLOSURE({0}) = {0} → 记作 DFA 的初态q₀按输入符号进行状态转移：
- 在
q₀下输入a：转移到 NFA 中由a导致的所有状态，并取其 ε-闭包 → 假设得到 {1,2,4} → 记作q₁ - 输入
b：若当前状态集中存在可响应b的状态，则推进并闭包 → 如q₁经b可能仍停留在{1,2,4}内部循环 - 若输入
a再次触发最终接受路径，则进入接受状态集 → 记作q₂
- 在
构建完整的 DFA 状态转移表：
当前状态 输入 a 输入 b q₀ q₁ ∅ q₁ q₂ (接受态) q₁ q₂ ∅ ∅
此时得到的 DFA 已无非确定性，每个状态对应原 NFA 的一个状态子集。
DFA 最小化（划分法 / Hopcroft 算法 或 Moore 算法）
目标：合并等价状态，消除冗余。步骤简述：
- 初始划分为两个集合：接受状态 vs 非接受状态；
- 迭代检查每个集合内的状态是否对所有输入符号转移到同一类集合；
- 若分裂发生，继续划分直到稳定；
- 每个最终划分块代表最小 DFA 中的一个状态。
应用于上述 DFA：
q₂是唯一的接受状态；q₀和q₁行为不同（q₀仅在a下转移，q₁在a下进接受态、b下自循环），不可合并；- 因此最小 DFA 与原 DFA 状态数一致（本例较小，未必能进一步压缩）；
图 2-11 所示最小化 DFA 即为此结果，结构清晰，适合代码实现。
实际意义
- NFA易于从正规式构造，便于理论分析；
- DFA可直接编码为状态转移表或 switch-case 逻辑，运行效率高；
- 最小化 DFA减少内存占用与判断开销，提升词法分析器性能。