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

从正则表达式到有限自动机3 7 3 9 有限自动机 3 3有限自动机 3 3 1不确定的有限自动机 简称NFA 一个数学模型 它包括 1 有限的状态集合S2 输入符号集合 3 转换函数move S P S 4 状态s0是唯一的开始状态5 F S是接受状态集合 识别语言 a b ab的NFA 一个符号标记离开同一状态有多条边 状态 NFA的转换表 3 3有限自动机 识别语言 a b ab的NFA 3 3 2确定的有限自动机 简称DFA 一个数学模型 包括 1 有限的状态集合S2 输入字母集合 3 转换函数move S S 且可以是部分函数4 唯一的开始状态s05 接受状态集合F S 识别语言 a b ab的DFA 3 3有限自动机 一个符号标记离开同一状态只有一条边 3 3有限自动机 例识别 a b ab的DFA DFA NFA NFA到DFA 子集构造法 3 3 3NFA到DFA的变换子集构造法1 DFA的一个状态是NFA的一个状态集合2 读了输入a1a2 an后 NFA能到达的所有状态 s1 s2 sk 则DFA到达状态 s1 s2 sk 0 0 1 0 2 3 3有限自动机 未画完 3 3有限自动机 3 3 3NFA到DFA的变换子集构造法 子集构造法 closure s 从NFA的状态S出发 只用 转换就能到达的状态的集合 closure T 从NFA的状态集合T中每个状态出发 只用 转换就能到达的状态的集合Move T a 状态集合T中每个状态通过a能到达的所有状态集合 子集构造法 找出U closure T 对于U 以及任意符号a 找出U通过a能到达的集合V Move U a 并计算V closure V U通过a到达的状态即为V U a V 3 3有限自动机 3 3 3NFA到DFA的变换子集构造法 状态转换表的构造 例 a b ab NFA如下 把它变换为DFA 3 3有限自动机 状态 3 3有限自动机 状态 A 0 1 2 4 7 3 3有限自动机 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 3 3有限自动机 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 3 3有限自动机 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 3 3有限自动机 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 3 3有限自动机 状态 A 0 1 2 4 7 B 1 2 3 4 6 7 8 C 1 2 4 5 6 7 3 3有限自动机 状态 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有限自动机 状态 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有限自动机 状态 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有限自动机 状态 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有限自动机 状态 3 3有限自动机 识别语言 a b ab的自动机 3 3有限自动机 子集构造法不一定得到最简DFA 3 3有限自动机 识别语言 a b ab的自动机 DFA的化简 3 3 4DFA的化简构造最简DFA 构造状态集合的初始划分 两个子集 接受状态子集F和非接受状态子集S F 3 3有限自动机 3 3 4DFA的化简构造最简DFA 构造状态集合的初始划分 两个子集 接受状态子集F和非接受状态子集S F应用下面的过程构造 newFor 中的每个子集G dobegin把G划分为若干子集 G的两个状态s和t在同一子集中 当且仅当对任意输入符号a s和t的a转换都到 的同一子集中在 new中 用G的划分代替GEnd 3 3有限自动机 3 3 4DFA的化简构造最简DFA 构造状态集合的初始划分 两个子集 接受状态子集F和非接受状态子集S F应用下面的过程构造 newFor 中的每个子集G dobegin把G划分为若干子集 G的两个状态s和t在同一子集中 当且仅当对任意输入符号a s和t的a转换都到 的同一子集中在 new中 用G的划分代替GEnd如果 new 则 final 否则令 new 转上步 3 3有限自动机 3 3 4DFA的化简构造最简DFA 构造状态集合的初始划分 两个子集 接受状态子集F和非接受状态子集S F应用下面的过程构造 newFor 中的每个子集G dobegin把G划分为若干子集 G的两个状态s和t在同一子集中 当且仅当对任意输入符号a s和t的a转换都到 的同一子集中在 new中 用G的划分代替GEnd如果 new 则 final 否则令 new 转上步在 final的每个状态子集中选一个状态代表它 即为最简DFA的状态 3 3有限自动机 DFA的化简 把G划分为若干子集 G的两个状态s和t在同一子集中 当且仅当对任意输入符号a s和t的a转换都到同一子集中 DFA的化简 构造最简的DFA接受状态子集 D 非接受状态子集 A B C A B C A C B 从正则表达式到有限自动机 从正则式建立识别器的步骤从正则式构造NFA 本节介绍 用语法制导的算法 它用正则式语法结构来指导构造过程把NFA变成DFA 子集构造法 已介绍 将DFA化简 合并不可区别状态 也已介绍 3 4从正则式到有限自动机 首先构造识别 和字母表中一个符号的NFA重要特点 仅一个接受状态 它没有向外的转换 3 4从正则式到有限自动机 构造识别主算符为选择的正则式的NFA重要特点 仅一个接受状态 它没有向外的转换 3 4从正则式到有限自动机 构造识别主算符为连接的正则式的NFA重要特点 仅一个接受状态 它没有向外的转换 识别正则式st的NFA 3 4从正则式到有限自动机 构造识别主算符为闭包的正则式的NFA重要特点 仅一个接受状态 它没有向外的转换 3 4从正则式到有限自动机 对于加括号的正则式 s 使用N s 本身作为它的NFA 3 4从正则式到有限自动机 本方法产生的NFA有下列性质N r 的状态数最多是r中符号和算符总数的两倍N r 只有一个接受状态 接受状态没有向外的转换 3 4从正则式到有限自动机 本方法产生的NFA有下列性质N r 的每个状态有一个用 的符号标记的指向其它结点的转换 或者最多两个指向其它结点的 转换 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 3 4从正则式到有限自动机 a b ab的两个NFA的比较 手工构造 算法构造 3 4从正则式到有限自动机 重点 从正则式建立识别器的步骤从正则式构造NFA把NFA变成DFA将DFA化简 练习 为正则式 a b a a b a b 构造NFA用子集构造法将NFA转换为DFA用状态转换图表示接受正则式 a b