从正则表达式到有限自动机.ppt-淘文阁

资源描述

《从正则表达式到有限自动机.ppt》由会员分享，可在线阅读，更多相关《从正则表达式到有限自动机.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、从正则表达式到有限自动机从正则表达式到有限自动机有限自动机3.3 有有限限自自动动机机 v例例识别识别(a|b)*a b 的DFADFANFANFA到DFA子集构造法3.3.3 NFA到到DFA的变换的变换子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后，NFA能到达的所有状态：能到达的所有状态：s1,s2,sk，则则 DFA到达状态到达状态s1,s2,sk 12a开始开始 0abb00,1aba0,2b3.3 有有限限自自动动机机未画完未画完3.3 有有限限自自动动机机 3.3.3

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

3、3.3 NFA到到DFA的变换的变换子集构造法：子集构造法：状态转换表的构造v 例例(a|b)*ab，NFA如下，把它变换为如下，把它变换为DFA3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号ab状态状态 3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号abA状态状态 A=0,1,2,4,7 3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 输入符号输入符号abAB状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7

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

5、 ab6782345 输入符号输入符号abABCBBC状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号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 3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCD状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D

6、=1,2,4,5,6,7,9 3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCD状态状态 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 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号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 3.3 有有限限自自动动机机 19开始开始 0ab ab67823

7、45 输入符号输入符号abABCBBDCBCDBC状态状态 BD开始开始aAabbabCba3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab子集构造法不一定得到最简子集构造法不一定得到最简DFA3.3 有有限限自自动动机机识别语言识别语言(a|b)*ab 的的自动机自动

8、机DFA的化简3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集F和非接受状态子集和非接受状态子集S F3.3 有有限限自自动动机机 3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集F和非接受状态子集和非接受状态子集S F应用下面的过程构造应用下面的过程构造newvFor 中的每个子集中的每个子集G，do begin把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子

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

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

11、，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅当在同一子集中，当且仅当对任意输入符号对任意输入符号 a，s 和和 t 的的 a 转换都到转换都到的同一子集中的同一子集中在在new 中，用中，用G的划分代替的划分代替GvEnd如果如果new=，则，则final=；否则令；否则令=new，转上步，转上步在在final的每个状态子集中选一个状态代表它，即为最简的每个状态子集中选一个状态代表它，即为最简DFA的状态的状态3.3 有有限限自自动动机机 DFA的化简v把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a，s 和 t

12、的 a 转换都到同一子集中DFA的化简v构造最简的DFAv接受状态子集D,非接受状态子集A,B,CvA,B,C-A,C BBD开始开始aAabbabCba从正则表达式到有限自动机v从正则式建立识别器的步骤从正则式建立识别器的步骤从正则式构造从正则式构造NFA（本节介绍）（本节介绍）v用语法制导的算法，它用正则式语法结构来指导构造用语法制导的算法，它用正则式语法结构来指导构造过程过程把把NFA变成变成DFA（子集构造法，已介绍）（子集构造法，已介绍）将将DFA化简化简（合并不可区别状态，也已介绍）（合并不可区别状态，也已介绍）3.4 从正则式到有限自动机从正则式到有限自动机v首先构造识别首先构造

13、识别和字母表中一个符号的和字母表中一个符号的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换i开始开始识别正则式识别正则式的的NFAafif开始开始识别正则式识别正则式a的的NFA3.4 从正则式到有限自动机从正则式到有限自动机v构造识别主算符为选择的正则式的构造识别主算符为选择的正则式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 fi开始开始识别正则式识别正则式s|t 的的NFAN(s)N(t)3.4 从正则式到有限自动机从正则式到有限自动机v构造识别主算符为连接的正则式的构造识别主算符为连接的正

14、则式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换识别正则式识别正则式 st 的的NFAiN(s)f开始开始N(t)3.4 从正则式到有限自动机从正则式到有限自动机v构造识别主算符为闭包的正则式的构造识别主算符为闭包的正则式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换N(s)f开始开始识别正则式识别正则式 s*的的NFAi 3.4 从正则式到有限自动机从正则式到有限自动机v对于加括号的正则式对于加括号的正则式(s)，使用使用N(s)本身作为本身作为它的它的NFA3.4 从正则式到有限自动机从正则式到有

15、限自动机v本方法产生的本方法产生的NFA有有下列性质下列性质N(r)的状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍N(r)只只有有一一个个接接受受状状态态，接接受受状状态态没没有有向向外外的的转转换换3.4 从正则式到有限自动机从正则式到有限自动机19开始开始 0ab ab6782345 v本方法产生的本方法产生的NFA有有下列性质下列性质N(r)的的每每个个状状态态有有一一个个用用的的符符号号标标记记的的指指向向其其它它结结点点的的转转换换，或或者者最最多多两两个个指指向向其其它它结结点点的的转转换换3.4 从正则式到有限自动机从正则式到有限自动机19开始开始

16、 0ab ab6782345 3.4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 从正则式到有限自动机从正则式到有限自动机 19

展开阅读全文