从正则表达式到有限自动机

1、从正则表达式到有限自动机有限自动机 有 限 自 动 机 .1 不确定的有限自动机简称NFA一个数学模型，它包括：1、有限的状态集合S2、输入符号集合3、转换函数move : S ( ) P(S)4、状态s0是唯一的开场状态5、F S是承受状态集合识别语言(a|b)*ab 的NFA12开始a0abb一个符号标记离开同一状态有多条边输 入 符 号ab00, 10122状 态 NFA的转换表 有 限 自 动 机 识别语言(a|b)*ab 的NFA12开始a0abb.2 确定的有限自动机简称DFA) 一个数学模型，包括：1、有限的状态集合S2、输入字母集合3、转换函数move : S S，且可以是局部

2、函数4、唯一的开场状态 s05、承受状态集合F S12开始a0abbab识别语言(a|b)*ab 的DFA 有 限 自 动 机 一个符号标记离开同一状态只有一条边 有 限 自 动 机 例 识别 (a | b)* a b 的DFADFANFANFA到DFA子集构造法.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后， NFA能到达的所有状态：s1, s2, , sk，那么 DFA到达状态s1, s2, , sk 12a开始 0abb00, 1aba0, 2b 有 限 自 动 机 未画完 有 限 自 动 机 .3 NFA到DFA的变换 子

3、集构造法子集构造法-closure(s) 从NFA的状态S出发，只用转换就能到达的状态的集合-closure(T) 从NFA的状态集合T中每个状态出发，只用转换就能到达的状态的集合Move(T,a) 状态集合T中每个状态通过a能到达的所有状态集合19开始0abab6782345子集构造法找出U=-closure(T)对于U，以及任意符号a，找出U通过a能到达的集合V=Move(U,a) ，并计算V=-closure(V)U通过a到达的状态即为V，U- a - V19开始0abab6782345 有 限 自 动 机 .3 NFA到DFA的变换 子集构造法：状态转换表的构造 例 (a|b)*ab，

4、NFA如下，把它变换为DFA 有 限 自 动 机 19开始0abab6782345输入符号ab状态 有 限 自 动 机 19开始0abab6782345输入符号abA状态 A = 0, 1, 2, 4, 7 有 限 自 动 机 19开始0abab678234519开始0abab6782345输入符号abAB状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 动 机 输入符号abABB状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 动 机 19开始0abab6782345输入符号abABCB状

5、态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 动 机 19开始0abab6782345输入符号abABCBC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 动 机 19开始0abab6782345输入符号abABCBBC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 动 机 19开始0abab6782345输入

6、符号abABCBBDC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 动 机 19开始0abab6782345输入符号abABCBBDCD状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 动 机 19开始0abab6782345输入符号abABCBBDCBCD状态 A = 0, 1, 2, 4, 7 B = 1,

7、 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 动 机 19开始0abab6782345输入符号abABCBBDCBCDBC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 动 机 19开始0abab6782345输入符号abABCBBDCBCDBC状态 BD开始aAabbabCba 有 限 自 动 机 19开始0abab678234519开始0abab678234

8、5BD开始aAabbabCba12开始a0abbab识别语言(a|b)*ab 的自动机 有 限 自 动 机 19开始0abab6782345BD开始aAabbabCba12开始a0abbab子集构造法不一定得到最简DFA 有 限 自 动 机 识别语言(a|b)*ab 的自动机DFA的化简3.3.4 DFA的化简构造最简DFA：构造状态集合的初始划分 ：两个子集承受状态子集F和非承受状态子集S F 有 限 自 动 机 3.3.4 DFA的化简构造最简DFA：构造状态集合的初始划分：两个子集承受状态子集F和非承受状态子集S F应用下面的过程构造newFor 中的每个子集G ，do begin把G划

9、分为假设干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 的同一子集中在new 中，用G的划分代替GEnd 有 限 自 动 机 3.3.4 DFA的化简构造最简DFA：构造状态集合的初始划分：两个子集承受状态子集F和非承受状态子集S F应用下面的过程构造newFor 中的每个子集G ，do begin把G划分为假设干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 的同一子集中在new 中，用G的划分代替GEnd如果new = ，那么final = ；否那么令 = new ，转上步

10、 有 限 自 动 机 3.3.4 DFA的化简构造最简DFA：构造状态集合的初始划分：两个子集承受状态子集F和非承受状态子集S F应用下面的过程构造newFor 中的每个子集G ，do begin把G划分为假设干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 的同一子集中在new 中，用G的划分代替GEnd如果new = ，那么final = ；否那么令 = new ，转上步在final的每个状态子集中选一个状态代表它，即为最简DFA的状态 有 限 自 动 机 DFA的化简把G划分为假设干子集，G的两个状态 s 和 t 在同一子集中，当

11、且仅当对任意输入符号 a ，s 和 t 的 a 转换都到同一子集中DFA的化简构造最简的DFA承受状态子集D,非承受状态子集A,B,CA,B,C-A,C BBD开始aAabbabCba从正那么表达式到有限自动机从正那么式建立识别器的步骤从正那么式构造NFA本节介绍用语法制导的算法，它用正那么式语法构造来指导构造过程把NFA变成DFA 子集构造法，已介绍将DFA化简 合并不可区别状态，也已介绍3.4 从正那么式到有限自动机首先构造识别和字母表中一个符号的NFA重要特点：仅一个承受状态，它没有向外的转换i开始识别正则式的NFAafif开始识别正则式a的NFA3.4 从正那么式到有限自动机构造识别主

12、算符为选择的正那么式的NFA重要特点：仅一个承受状态，它没有向外的转换 fi开始识别正则式s | t 的NFAN (s)N (t)3.4 从正那么式到有限自动机构造识别主算符为连接的正那么式的NFA重要特点：仅一个承受状态，它没有向外的转换识别正那么式 st 的NFAiN (s)f开始N (t)3.4 从正那么式到有限自动机构造识别主算符为闭包的正那么式的NFA重要特点：仅一个承受状态，它没有向外的转换N (s)f开始识别正则式 s* 的NFAi3.4 从正那么式到有限自动机对于加括号的正那么式(s)，使用N(s)本身作为它的NFA3.4 从正那么式到有限自动机本方法产生的NFA有以下性质N(

13、r)的状态数最多是r中符号和算符总数的两倍N(r)只有一个承受状态，承受状态没有向外的转换3.4 从正那么式到有限自动机19开始0abab6782345本方法产生的NFA有以下性质N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换3.4 从正那么式到有限自动机19开始0abab67823453.4 从正那么式到有限自动机 19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 从正那么式到有限自动机 19开始0ab678ab2345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab

14、的分解3.4 从正那么式到有限自动机 19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 从正那么式到有限自动机 19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 从正那么式到有限自动机 19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 从正那么式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 从正那么式到有限自动机 19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解 (a|b)*ab的两个NFA的比较 12开始a 0abb手工构造:算法构造:3.4 从正那么式到有限自动机19开始0abab6782345重点从正那么式建立识别器的步骤从正那么式