正规式 `ab*a` 描述的是以 `a` 开头、中间有任意多个 `b`（包括零个）、最后再以 `a` 结尾的字符串，即形如 `aa`, `aba`, `abba`, `abbba`

正规式ab*a描述的是以a开头、中间有任意多个b（包括零个）、最后再以a结尾的字符串，即形如aa,aba,abba,abbba等。在词法分析中，这类正规式常用于识别特定模式的标识符或关键字结构。

为了将该正规式转化为可执行的自动机模型，通常经历以下步骤：

1. 正规式 → NFA（通过 Thompson 构造法）
   对ab*a构造对应的 NFA：

   • 使用 ε-转移 表示选择和连接；
   • b*部分构造为一个带自环的 ε-NFA；
   • 整体结构为：a后接(b)*，再接a；
   • 得到的状态机允许从初始状态经 ε 转移到达多个路径，具有非确定性。

2. 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 的一个状态子集。

3. DFA 最小化（划分法 / Hopcroft 算法 或 Moore 算法）
   目标：合并等价状态，消除冗余。

   步骤简述：

   • 初始划分为两个集合：接受状态 vs 非接受状态；
   • 迭代检查每个集合内的状态是否对所有输入符号转移到同一类集合；
   • 若分裂发生，继续划分直到稳定；
   • 每个最终划分块代表最小 DFA 中的一个状态。

   应用于上述 DFA：

   • q₂是唯一的接受状态；
   • q₀和q₁行为不同（q₀仅在a下转移，q₁在a下进接受态、b下自循环），不可合并；
   • 因此最小 DFA 与原 DFA 状态数一致（本例较小，未必能进一步压缩）；

   图 2-11 所示最小化 DFA 即为此结果，结构清晰，适合代码实现。

---

实际意义

• NFA易于从正规式构造，便于理论分析；
• DFA可直接编码为状态转移表或 switch-case 逻辑，运行效率高；
• 最小化 DFA减少内存占用与判断开销，提升词法分析器性能。