【程序语言与编译】正规式与有限自动机的等价转换

适合读者软考中级备考同学阅读时间4分钟内容正规式与FA等价性、正规式转NFAThompson构造法、NFA转正规式状态消去法、例题1. 为什么需要等价转换正规式RE和有限自动机FA包括NFA和DFA都能描述正则语言且二者等价每个正规式对应一个NFA进而可转为DFA每个NFA/DFA对应的语言都可以用一个正规式表示软考中常考查两种方向给定正规式画出NFA状态图给定DFA或NFA写出等价的正规式掌握转换方法可以灵活地在两种表示之间切换便于词法分析器的设计。2. 正规式 → NFAThompson构造法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→fi→iri \to i_ri→ir​fr→ff_r \to ffr​→ffr→irf_r \to i_rfr​→ir​允许循环。2.3 示例将正规式(a∣b)∗a(a|b)^*a(a∣b)∗a转换为NFA。构造a∣ba|ba∣baaa的NFAi0→a→f0bbb的NFAi1→b→f1选择构造新初态I新终态FIε→i0Iε→i1f0ε→Ff1ε→F。对(a∣b)(a|b)(a∣b)做闭包∗*∗新增初态I’和终态F’添加ε边I’→F’I’→IF→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及其所有关联边。重复直到只剩XXX和YYY。如果存在从XXX到YYY的边标记为RRR则正规式为RRR如果有多条平行边用|合并。3.2 简化规则若XXX有自环可忽略因为开始前不输入任何字符。最终结果通常用RR1∣R2∣...R R_1 | R_2 | ...RR1​∣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–AA–1–BB–0–AB–1–B求等价的正规式。解使用状态消去法添加新初态XXXε→A和新终态YYYB→ε→Y。消去中间状态直接观察从A经过一个1到B之后可以在B上任意多个1循环也可以从B通过0回到A然后重复。用方程法或消去法设RAAR_{AA}RAA​表示从A到A的正规式RABR_{AB}RAB​从A到B等等。A→A: 读0可自环 →000A→B: 读1 →111B→A: 读0 →000B→B: 读1 →111列方程AA⋅0∣B⋅0∣εA A \cdot 0 \mid B \cdot 0 \mid \varepsilonAA⋅0∣B⋅0∣εBA⋅1∣B⋅1B A \cdot 1 \mid B \cdot 1BA⋅1∣B⋅1先解BA1∣B1B A1 \mid B1BA1∣B1→BA1⋅1∗B A1 \cdot 1^*BA1⋅1∗由BB1∣A1B B1 \mid A1BB1∣A1得BA1⋅1∗B A1 \cdot 1^*BA1⋅1∗。代入AAAAA0∣(A1⋅1∗)0∣εA(0∣11∗0)∣εA A0 \mid (A1 \cdot 1^*)0 \mid \varepsilon A(0 \mid 11^*0) \mid \varepsilonAA0∣(A1⋅1∗)0∣εA(0∣11∗0)∣ε。所以A(0∣11∗0)∗A (0 \mid 11^*0)^*A(0∣11∗0)∗。最终正规式从A到终态BA⋅(1⋅1∗)A \cdot (1 \cdot 1^*)A⋅(1⋅1∗)? 注意B是终态原DFA的初态A终态B所以语言是A→BA \to BA→B的串。由BA1⋅1∗B A1 \cdot 1^*BA1⋅1∗所以正规式为A1⋅1∗(0∣11∗0)∗1⋅1∗(0∣11∗0)∗1A1 \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篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #正规式 #有限自动机 #等价转换 #词法分析