当前位置：首页 > news >正文

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

news 2026/5/12 15:45:10

正规式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 即为此结果，结构清晰，适合代码实现。