有限自动机与正规式之间的相互转换是形式语言与自动机理论中的核心内容，广泛应用于编译器设计中的词法分析阶段

有限自动机与正规式之间的相互转换是形式语言与自动机理论中的核心内容，广泛应用于编译器设计中的词法分析阶段。以下是对两个转换方向的系统化总结和说明：

1.有限自动机转换为正规式（NFA → 正规式）

目标：给定一个 NFA $ M $，求一个正规式 $ R $，使得 $ L® = L(M) $。

步骤详解：

1. 扩展状态图：

   • 添加一个新的初始状态 $ x $ 和一个新的终止状态 $ y $。
   • 从 $ x $ 到原初态引一条 $ \varepsilon $-转移弧。
   • 从每一个原终态到 $ y $ 引一条 $ \varepsilon $-转移弧。
   • 确保整个自动机只有一个初态 $ x $ 和一个终态 $ y $。

2. 逐步消除中间状态：

   • 每次选择一个非 $ x $、非 $ y $ 的状态 $ q $ 进行消除。
   • 对于所有进入 $ q $ 的弧（如 $ p \xrightarrow{R_1} q $）和所有从 $ q $ 出发的弧（如 $ q \xrightarrow{R_2} r $），以及 $ q $ 上可能存在的自环 $ R_3 $：
     • 在 $ p $ 和 $ r $ 之间添加新弧：$ p \xrightarrow{R_1 R_3^* R_2} r $。
   • 若已有从 $ p $ 到 $ r $ 的路径，则使用“选择”运算合并：$ R_{\text{new}} = R_{\text{old}} | R_1 R_3^* R_2 $。
   • 删除状态 $ q $ 及其所有关联的边。

3. 最终结果：

   • 当只剩 $ x $ 和 $ y $ 时，若存在 $ x \xrightarrow{R} y $，则 $ R $ 即为所求正规式。
   • 如果没有路径，则正规式为 $ \varnothing $。

消除规则归纳：

• 串联：$ a \xrightarrow{R_1} b \xrightarrow{R_2} c $ → $ a \xrightarrow{R_1R_2} c $
• 并联：$ a \xleftarrow[R_2]{R_1} b $ → $ a \xrightarrow{R_1|R_2} b $
• 自环处理：涉及状态 $ b $ 有自环 $ R_2 $，前后分别为 $ R_1, R_3 $，则变为 $ a \xrightarrow{R_1 R_2^* R_3} c $

2.正规式转换为有限自动机（正规式 → NFA）

目标：给定正规式 $ R $，构造等价的 NFA $ M $，满足 $ L(M) = L® $。

方法：通常采用Thompson 构造法。

步骤详解：

1. 初始结构：

   • 构造一个仅含两个状态的状态图：初态 $ x $、终态 $ y $，中间以标记为 $ R $ 的弧连接：$ x \xrightarrow{R} y $。

2. 递归分解正规式结构：

   • 根据正规式的三种基本运算进行拆分：

（1）连接运算 $ R = R_1 R_2 $：

• 原结构：$ x \xrightarrow{R_1 R_2} y $
• 拆分方式：引入中间状态 $ k $
• 新结构：$ x \xrightarrow{R_1} k \xrightarrow{R_2} y $

（2）选择运算 $ R = R_1 | R_2 $：

• 原结构：$ x \xrightarrow{R_1 | R_2} y $
• 拆分方式：从 $ x $ 分两条路径分别经 $ R_1、、、R_2 $ 到达 $ y $
• 或引入辅助状态，通过 $ \varepsilon $-转移实现分支

（3）闭包运算 $ R = R_1^$*：

• 原结构：$ x \xrightarrow{R_1^*} y $

• 拆分方式：引入新状态 $ k $

• 结构：
  $ x \xrightarrow{\varepsilon} k $,
  $ k \xrightarrow{R_1} k $（自环）,
  $ k \xrightarrow{\varepsilon} y $

• 实现零次或多次匹配。

3. 重复上述过程，直到所有弧上的标记都变成单个字符或 $ \varepsilon $，此时得到的就是合法的 NFA。

4. 输出 NFA：该 NFA 接受的语言与原始正规式相同。

✅ 应用场景与意义（知识点用途）

• 词法分析器自动生成：
  • 编程语言的关键字、标识符、常量等词汇模式可用正规式描述。
  • 工具（如 Lex）将这些正规式转换为 NFA → 转换为 DFA → 最小化 → 生成词法分析代码。
• 正则表达式引擎实现基础：
  • 多数现代编程语言中regex的底层机制基于自动机构造。
• 形式化验证与模式匹配系统：
  • 如网络入侵检测、文本编辑器搜索功能等。