正规式与有限自动机等价

等价性定理

定理：正规式 $\leftrightarrow$ 有限自动机等价。

即对任一正规式 $r$，存在 FA 识别 $L(r)$；对任一 FA，存在正规式描述其语言。

充分性：NFA → 正规式（替换法）

含弧表达式的 NFA，使用三条替换规则逐步消去状态，最终得到正规式：

规则	替换前	替换后
串联	$q_i\stackrel{r_1}{\to }{q}_j$ 且 $q_j\stackrel{r_2}{\to }{q}_k$	中间状态 $q_j$ 可删除，加弧 $q_i\stackrel{r_1{r}_2}{\to }{q}_k$
并联	$q_i\stackrel{r_1}{\to }{q}_j$ 且 $q_i\stackrel{r_2}{\to }{q}_j$	合并为 $q_i \xrightarrow{r_1
自环	$q_i\stackrel{r_1}{\to }{q}_i$ 且 $q_i\stackrel{r_2}{\to }{q}_j$	自环转为 $q_i\stackrel{r_1^{\ast }{r}_2}{\to }{q}_j$

反复应用规则消去非初态非终态的中间状态，最终形式为 $S\stackrel{r}{\to }Z$，$r$ 即所求正规式。

重点 NFA→正规式的三条替换规则。

状态消去完整示例

将以下 DFA（识别含 “00” 的二进制串）转换为正规式：

状态: 0(初态), 1, 2(终态)
边: 0-0→0, 0-1→1, 1-0→2, 1-1→1, 2-0→2, 2-1→2

步骤 1：消去状态 1

• 自环 1：$1\stackrel{1}{\to }1$ → 串联规则：从 0 经 1 到 2 的路径为 $1\cdot 1^{\ast }\cdot 0$
• 并联规则：0 到 2 原有的路径 $0\stackrel{0}{\to }2$（不存在），仅剩 $0\stackrel{1}{\to }1\stackrel{0}{\to }2$ 消去后为 $11^{\ast }0$
• 0 的自环：原 $0\stackrel{0}{\to }0$ 并联 $0\stackrel{1}{\to }1\stackrel{1}{\to }0$（经 1 返回 0）→ $0|11^{\ast }0$
• 0 到 2 的新弧：$11^{\ast }0$

步骤 2：消去状态 0（此时只剩初态 0’ 和终态 2）

• 自环 0：$0|11^{\ast }0$ → 自环规则：$0\stackrel{(0|11^{\ast }0{)}^{\ast }\cdot 11^{\ast }0}{\to }2$
• 2 的自环和到 2 的路径保留：$2\stackrel{0|1}{\to }2$

步骤 3：消去状态 2（只剩初态→终态单弧）

• 自环 2：$0|1$ → 最终正规式：$(0|11^{\ast }0{)}^{\ast }\cdot 11^{\ast }0\cdot (0|1{)}^{\ast }$

即含 “00” 的二进制串正规式为 $(0|11^{\ast }0{)}^{\ast }11^{\ast }0(0|1{)}^{\ast }$，与直观形式 $(0|1{)}^{\ast }00(0|1{)}^{\ast }$ 等价。

必要性：正规式 → NFA

递归构造，对基本正规式构造基 NFA，再按正规式归纳构造：

• 基 NFA：

  • $\varnothing$：两个孤立状态，无边
  • $\epsilon$：初态 $\to$ 终态（$\epsilon$ 边）
  • $a$：初态 $\stackrel{a}{\to }$ 终态

• 归纳构造：

  • $r|s$：引入新初态（$\epsilon$ 分支到两个子 NFA）和新终态
  • $r\cdot s$：$r$ 的终态连 $\epsilon$ 到 $s$ 的初态
  • $r^{\ast }$：自环 $\epsilon$ 边绕回

重点 正规式→NFA 的递归构造方法。

完整应用流程

$$\text{正规式}\stackrel{\text{递归构造}}{\to }\text{NFA}\stackrel{\text{子集构造法}}{\to }\text{DFA}\stackrel{\text{划分法}}{\to }\text{最小化 DFA}$$

正规式 和 有限自动机 通过此流程建立等价关系，是词法分析器自动生成的理论基础。