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

1、从正则表达式到有限自动机从正则表达式到有限自动机 3.73.9 1/34 2021/3/10 有限自动机有限自动机 2/34 2021/3/10 3.3 有有 限限 自自 动动 机机 3.3.1 不确定的有限自动机（简称不确定的有限自动机（简称NFA） 一个数学模型，它包括：一个数学模型，它包括： 1、有限的状态集合、有限的状态集合S 2、输入符号集合、输入符号集合 3、转换函数、转换函数move : S ( ) P(S) 4、状态、状态s0是唯一的开始状态是唯一的开始状态 5、F S是接受状态集合是接受状态集合 识别语言识别语言 (a|b)*ab 的的NFA 12 开始开始a 0 a b b

2、 一个符号标记离开同一状态有多条边 3/34 2021/3/10 输输 入入 符符 号号 ab 00, 10 12 2 状状 态态 NFA的转换表的转换表 3.3 有有 限限 自自 动动 机机 识别语言识别语言 (a|b)*ab 的的NFA 12 开始开始a 0 a b b 4/34 2021/3/10 3.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括： 1、有限的状态集合、有限的状态集合S 2、输入字母集合、输入字母集合 3、转换函数、转换函数move : S S，且可以是部分函数且可以是部分函数 4、唯一的开始状态、唯一的开始状态

3、 s0 5、接受状态接受状态集合集合F S 1 2 开始开始 a 0 a b b a b 识别语言识别语言 (a|b)*ab 的的DFA 3.3 有有 限限 自自 动动 机机 一个符号标记离开同一状态只有一条边 5/34 2021/3/10 3.3 有有 限限 自自 动动 机机 v例例 识别识别 (a | b)* a b 的DFA DFA NFA 6/34 2021/3/10 NFA到到DFA子集构造法子集构造法 7/34 2021/3/10 3.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了

4、输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 12 a 开始开始 0 a b b 00, 1 a b a 0, 2 b 3.3 有有 限限 自自 动动 机机 未画完未画完 8/34 2021/3/10 3.3 有有 限限 自自 动动 机机 3.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 9/34 2021/3/10 子集构造法 v-closure(s) 从NFA的状态S出发，只用转换就能到达的 状态的集合 v-closure(T) 从NFA的状态集合T中每个状态出发，只用 转

5、换就能到达的状态的集合 vMove(T,a) 状态集合T中每个状态通过a能到达的所有状态 集合 1 9 开始开始 0 a b ab 678 23 4 5 10/34 2021/3/10 子集构造法 找出U=-closure(T) v对于U，以及任意符号a，找出U通过a能到达的集合 V=Move(U,a) ，并计算V=-closure(V) vU通过a到达的状态即为V，U- a - V 1 9 开始开始 0 a b ab 678 23 4 5 11/34 2021/3/10 3.3 有有 限限 自自 动动 机机 3.3.3 NFA到到DFA的变换的变换 子集构造法：子集构造法：状态转换表的构造

6、12/34 2021/3/10 v 例例 (a|b)*ab，NFA如下，把它变换为如下，把它变换为DFA 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 13/34 2021/3/10 输入符号输入符号 ab 状态状态 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 14/34 2021/3/10 输入符号输入符号 ab A 状态状态 A = 0, 1, 2, 4, 7 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 15/34 2021/3/10 1

7、 9 开始开始 0 a b ab 678 23 4 5 输入符号输入符号 ab AB 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 3.3 有有 限限 自自 动动 机机 16/34 2021/3/10 输入符号输入符号 ab AB B 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 17/34 2021/3/10 输入符号输入符号 ab ABC B 状态状态 A = 0, 1, 2, 4, 7 B = 1,

8、 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 18/34 2021/3/10 输入符号输入符号 ab ABC B C 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 19/34 2021/3/10 输入符号输入符号 ab ABC BB C 状态状态 A = 0, 1, 2, 4, 7 B

9、 = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 20/34 2021/3/10 输入符号输入符号 ab ABC BBD C 状态状态 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 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 21/34 2021/3/10 输入符号输入符号 ab AB

10、C BBD C D 状态状态 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 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 22/34 2021/3/10 输入符号输入符号 ab ABC BBD CBC D 状态状态 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 3.3 有有 限限 自自 动动

11、机机 1 9 开始开始 0 a b ab 678 23 4 5 23/34 2021/3/10 输入符号输入符号 ab ABC BBD CBC DBC 状态状态 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 3.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 24/34 2021/3/10 输入符号输入符号 ab ABC BBD CBC DBC 状态状态 BD 开始开始a A a b b a b C b a 3.3 有有 限

12、限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 4 5 25/34 2021/3/10 1 9 开始开始 0 a b ab 678 23 4 5 BD 开始开始a A a b b a b C b a 12 开始开始a 0 a b b a b 识别语言识别语言 (a|b)*ab 的的自动机自动机 3.3 有有 限限 自自 动动 机机 26/34 2021/3/10 1 9 开始开始 0 a b ab 678 23 4 5 BD 开始开始a A a b b a b C b a 12 开始开始a 0 a b b a b 子集构造法不一定得到最简子集构造法不一定得到最简DFA

13、3.3 有有 限限 自自 动动 机机 识别语言识别语言 (a|b)*ab 的的自动机自动机 27/34 2021/3/10 DFA的化简的化简 28/34 2021/3/10 3.3.4 DFA的化简的化简 v构造最简构造最简DFA： 构造状态集合的初始划分构造状态集合的初始划分 ：两个子集：两个子集接受状态子接受状态子 集集F和非接受状态子集和非接受状态子集S F 3.3 有有 限限 自自 动动 机机 29/34 2021/3/10 3.3.4 DFA的化简的化简 v构造最简构造最简DFA： 构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集 F和非接受

14、状态子集和非接受状态子集S F 应用下面的过程构造应用下面的过程构造new vFor 中的每个子集中的每个子集G ，do begin 把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅在同一子集中，当且仅 当对任意输入符号当对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到 的同一子集中的同一子集中 在在new 中，用中，用G的划分代替的划分代替G vEnd 3.3 有有 限限 自自 动动 机机 30/34 2021/3/10 3.3.4 DFA的化简的化简 v构造最简构造最简DFA： 构造状态集合的初始划分构造状态集合的初始划分：两个

15、子集：两个子集接受状态子集接受状态子集 F和非接受状态子集和非接受状态子集S F 应用下面的过程构造应用下面的过程构造new vFor 中的每个子集中的每个子集G ，do begin 把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅在同一子集中，当且仅 当对任意输入符号当对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到 的同一子集中的同一子集中 在在new 中，用中，用G的划分代替的划分代替G vEnd 如果如果new = ，则，则final = ；否则令；否则令 = new ，转上步，转上步 3.3 有有 限限 自自 动动 机机

16、31/34 2021/3/10 3.3.4 DFA的化简的化简 v构造最简构造最简DFA： 构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集 F和非接受状态子集和非接受状态子集S F 应用下面的过程构造应用下面的过程构造new vFor 中的每个子集中的每个子集G ，do begin 把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅在同一子集中，当且仅 当对任意输入符号当对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到 的同一子集中的同一子集中 在在new 中，用中，用G的划分代替的划分代替G

17、 vEnd 如果如果new = ，则，则final = ；否则令；否则令 = new ，转上步，转上步 在在final的每个状态子集中选一个状态代表它，即为最简的每个状态子集中选一个状态代表它，即为最简 DFA的状态的状态 3.3 有有 限限 自自 动动 机机 32/34 2021/3/10 DFA的化简 v把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到同一子集中 33/34 2021/3/10 DFA的化简 v构造最简的DFA v接受状态子集D,非接受状态子集A,B,C vA,B,C-A,C B BD 开始开始a A a

18、 b b a b C b a 34/34 2021/3/10 从正则表达式到有限自动机从正则表达式到有限自动机 35/34 2021/3/10 v从正则式建立识别器的步骤从正则式建立识别器的步骤 从正则式构造从正则式构造NFA（本节介绍）（本节介绍） v用语法制导的算法，它用正则式语法结构来指导构造用语法制导的算法，它用正则式语法结构来指导构造 过程过程 把把NFA变成变成DFA （子集构造法，已介绍）（子集构造法，已介绍） 将将DFA化简化简 （合并不可区别状态，也已介绍）（合并不可区别状态，也已介绍） 3.4 从正则式到有限自动机从正则式到有限自动机 36/34 2021/3/10 v首先

19、构造识别首先构造识别 和字母表中一个符号的和字母表中一个符号的NFA 重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 i 开始开始 识别正则式识别正则式 的的NFA a fif 开始开始 识别正则式识别正则式a的的NFA 3.4 从正则式到有限自动机从正则式到有限自动机 37/34 2021/3/10 v构造识别主算符为选择的正则式的构造识别主算符为选择的正则式的NFA 重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 f i 开始开始 识别正则式识别正则式s | t 的的NFA N (s) N (t) 3.4 从正则式

20、到有限自动机从正则式到有限自动机 38/34 2021/3/10 v构造识别主算符为连接的正则式的构造识别主算符为连接的正则式的NFA 重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 识别正则式识别正则式 st 的的NFA i N (s) f 开始开始 N (t) 3.4 从正则式到有限自动机从正则式到有限自动机 39/34 2021/3/10 v构造识别主算符为闭包的正则式的构造识别主算符为闭包的正则式的NFA 重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 N (s) f 开始开始 识别正则式识别正则式 s* 的的

21、NFA i 3.4 从正则式到有限自动机从正则式到有限自动机 40/34 2021/3/10 v对于加括号的正则式对于加括号的正则式(s)，使用使用N(s)本身作为本身作为 它的它的NFA 3.4 从正则式到有限自动机从正则式到有限自动机 41/34 2021/3/10 v本方法产生的本方法产生的NFA有有下列性质下列性质 N(r)的状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍 N(r)只有一个接受状态，接受状态没有向外的转只有一个接受状态，接受状态没有向外的转 换换 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2

22、3 4 5 42/34 2021/3/10 v本方法产生的本方法产生的NFA有有下列性质下列性质 N(r)的每个状态有一个用的每个状态有一个用 的符号标记的指向其的符号标记的指向其 它结点的转换，或者最多两个指向其它结点的它结点的转换，或者最多两个指向其它结点的 转换转换 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2 3 4 5 43/34 2021/3/10 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b

23、a b (a|b)*ab的分解的分解 44/34 2021/3/10 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 ab 678 a b 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 45/34 2021/3/10 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 46/34 2021/3/10 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2 3 4 5 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 47/34 2021/3/10 3.4 从正则式到有限自动机从正则式到有限自动机 1 9 开始开始 0 a b ab 678 2 3 4 5 r9 r7 r8 r4