适合读者：软考中级备考同学
阅读时间：4分钟
内容：正规式与FA等价性、正规式转NFA（Thompson构造法）、NFA转正规式（状态消去法）、例题
1. 为什么需要等价转换？
正规式（RE）和有限自动机（FA，包括NFA和DFA）都能描述正则语言，且二者等价：
- 每个正规式对应一个NFA（进而可转为DFA）
- 每个NFA/DFA对应的语言都可以用一个正规式表示
软考中常考查两种方向：
- 给定正规式，画出NFA状态图
- 给定DFA（或NFA），写出等价的正规式
掌握转换方法，可以灵活地在两种表示之间切换，便于词法分析器的设计。
2. 正规式 → NFA（Thompson构造法）
Thompson构造法通过递归地为每个子正规式构造局部NFA，再组合成整体NFA。基本规则如下：
2.1 基本规则
- 空串ε\varepsilonε：
→ (i) → (f)一条ε\varepsilonε边。 - 单个字符aaa：
→ (i) -a-> (f)
2.2 组合规则
设rrr和sss的子NFA分别为N(r)N(r)N(r)、N(s)N(s)N(s)，它们的初态和终态分别为ir,fri_r, f_rir,fr和is,fsi_s, f_sis,fs。
- 连接rsrsrs：将frf_rfr与isi_sis用ε\varepsilonε边连接，整体初态为iri_rir，终态为fsf_sfs。
- 选择r∣sr|sr∣s：新增一个初态iii和终态fff，从iii分别用ε\varepsilonε边连到iri_rir和isi_sis，再从frf_rfr和fsf_sfs用ε\varepsilonε边连到fff。
- 闭包r∗r^*r∗：新增初态iii和终态fff，添加四条ε\varepsilonε边：i→fi \to fi→f，i→iri \to i_ri→ir，fr→ff_r \to ffr→f，fr→irf_r \to i_rfr→ir（允许循环）。
2.3 示例
将正规式(a∣b)∗a(a|b)^*a(a∣b)∗a转换为NFA。
- 构造a∣ba|ba∣b：
- aaa的NFA：i0→a→f0
- bbb的NFA：i1→b→f1
- 选择构造：新初态I，新终态F，Iε→i0，Iε→i1，f0ε→F，f1ε→F。
- 对(a∣b)(a|b)(a∣b)做闭包∗*∗：新增初态I’和终态F’，添加ε边：I’→F’，I’→I，F→F’，F→I。
- 连接aaa：上一步的终态F’用ε连接到新a的NFA的初态，a的NFA的终态作为整体终态。
（图形省略，考试中通常只要求理解构造思路，不要求画出复杂图。）
3. NFA → 正规式（状态消去法）
思想：逐步消去NFA中的中间状态，同时用正规式标记转移边上的标签。最终只剩初态和终态，两者之间的边上的正规式即为所求。
3.1 步骤
- 添加一个新的初态XXX（用ε\varepsilonε边连接原初态）和一个新的终态YYY（用ε\varepsilonε边连接原终态），保证只有一个初态和一个终态。
- 反复选择一个内部状态（不是XXX也不是YYY）消去：
- 对于被消去状态qqq，考虑所有进入qqq的边（标记为RiR_iRi，来自状态pip_ipi）和所有从qqq离开的边（标记为SjS_jSj，去往状态rjr_jrj），以及qqq的自环边（标记为TTT）。
消去qqq后，为每对pi→rjp_i \to r_jpi→rj添加一条新边，标记为Ri⋅T∗⋅SjR_i \cdot T^* \cdot S_jRi⋅T∗⋅Sj。如果pip_ipi和rjr_jrj之间已有边，则用选择|合并。 - 删除qqq及其所有关联边。
- 对于被消去状态qqq，考虑所有进入qqq的边（标记为RiR_iRi，来自状态pip_ipi）和所有从qqq离开的边（标记为SjS_jSj，去往状态rjr_jrj），以及qqq的自环边（标记为TTT）。
- 重复直到只剩XXX和YYY。
- 如果存在从XXX到YYY的边，标记为RRR，则正规式为RRR；如果有多条平行边，用
|合并。
3.2 简化规则
- 若XXX有自环，可忽略（因为开始前不输入任何字符）。
- 最终结果通常用R=R1∣R2∣...R = R_1 | R_2 | ...R=R1∣R2∣...表示。
4. 经典例题
题目1：将正规式(0∣1)∗1(0|1)^*1(0∣1)∗1转换为NFA（描述思路即可）。
解：
- 先构造0∣10|10∣1，再闭包，最后连接111。最终得到一个具有ε\varepsilonε转移的NFA，能识别所有以1结尾的二进制串。
题目2：给定DFA如下（状态A初态，B终态，转移：A–0–>A，A–1–>B，B–0–>A，B–1–>B），求等价的正规式。
解（使用状态消去法）：
- 添加新初态XXX（ε→A）和新终态YYY（B→ε→Y）。
- 消去中间状态？直接观察：从A经过一个1到B，之后可以在B上任意多个1（循环），也可以从B通过0回到A，然后重复。
用方程法（或消去法）：
设RAAR_{AA}RAA表示从A到A的正规式，RABR_{AB}RAB从A到B，等等。- A→A: 读0可自环 →000
- A→B: 读1 →111
- B→A: 读0 →000
- B→B: 读1 →111
列方程：
A=A⋅0∣B⋅0∣εA = A \cdot 0 \mid B \cdot 0 \mid \varepsilonA=A⋅0∣B⋅0∣ε
B=A⋅1∣B⋅1B = A \cdot 1 \mid B \cdot 1B=A⋅1∣B⋅1
先解B=A1∣B1B = A1 \mid B1B=A1∣B1→B=A1⋅1∗B = A1 \cdot 1^*B=A1⋅1∗（由B=B1∣A1B = B1 \mid A1B=B1∣A1得B=A1⋅1∗B = A1 \cdot 1^*B=A1⋅1∗）。
代入AAA：A=A0∣(A1⋅1∗)0∣ε=A(0∣11∗0)∣εA = A0 \mid (A1 \cdot 1^*)0 \mid \varepsilon = A(0 \mid 11^*0) \mid \varepsilonA=A0∣(A1⋅1∗)0∣ε=A(0∣11∗0)∣ε。
所以A=(0∣11∗0)∗A = (0 \mid 11^*0)^*A=(0∣11∗0)∗。
最终正规式（从A到终态B）：A⋅(1⋅1∗)A \cdot (1 \cdot 1^*)A⋅(1⋅1∗)? 注意B是终态，原DFA的初态A，终态B，所以语言是A→BA \to BA→B的串。由B=A1⋅1∗B = A1 \cdot 1^*B=A1⋅1∗，所以正规式为A1⋅1∗=(0∣11∗0)∗1⋅1∗=(0∣11∗0)∗1+A1 \cdot 1^* = (0 \mid 11^*0)^* 1 \cdot 1^* = (0 \mid 11^*0)^* 1^+A1⋅1∗=(0∣11∗0)∗1⋅1∗=(0∣11∗0)∗1+。可以简化为(0∣11∗0)∗1+(0|11^*0)^*1^+(0∣11∗0)∗1+。
答案：(0∣11∗0)∗1+(0|11^*0)^*1^+(0∣11∗0)∗1+（或等价形式）
5. 记忆口诀
正规式与自动机，等价互转需记清。
RE转FA Thompson，递归添加ε边。
FA转RE消状态，自环闭包解方程。
6. 给备考同学的一句话
正规式与有限自动机的等价转换是词法分析理论的核心。软考中通常只考查简单实例（状态数2-3个）或概念性选择题。需要掌握：
- Thompson构造法的基本思想（为每个运算符构造局部NFA）。
- 状态消去法（或方程求解）求DFA的正规式。
如果考试遇到复杂转换，建议先用方程法列方程，再解正规式，避免手工消去出错。
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅
#软考中级 #软件设计师 #正规式 #有限自动机 #等价转换 #词法分析
