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

单击编辑母版标题样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,从正则表达式到有限自动机,从正则表达式到有限自动机从正则表达式到有限自动机有限自动机,有限自动机,3.3,有 限 自 动 机,3.3,.1,不确定的有限自动机（简称,NFA,）,一个数学模型，它包括：,1,、有限的状态集合,S,2,、输入符号集合,3,、转换函数,move,:,S,(,),P,(,S,),4,、状态,s,0,是唯一的开始状态,5,、,F,S,是接受状态集合,识别语言,(,a,|,b,),*,ab,的,NFA,1,2,开始,a,0,a,b,b,一个符号标记离开同一状态有多条边,输 入 符 号,a,b,0,0,1,0,1,2,2,状 态,NFA,的转换表,3.3,有 限 自 动 机,识别语言,(,a,|,b,),*,ab,的,NFA,1,2,开始,a,0,a,b,b,3.3,.2,确定的有限自动机（简称,DFA,),一个数学模型，包括：,1,、有限的状态集合,S,2,、输入字母集合,3,、转换函数,move,:,S,S,，,且可以是部分函数,4,、唯一的开始状态,s,0,5,、,接受状态,集合,F,S,1,2,开始,a,0,a,b,b,a,b,识别语言,(,a,|,b,),*,ab,的,DFA,3.3,有 限 自 动 机,一个符号标记离开同一状态只有一条边,3.3,有 限 自 动 机,例 识别,(,a,|,b,)*,a,b,的,DFA,DFA,NFA,NFA,到,DFA,子集构造法,3.3,.3,NFA,到,DFA,的变换,子集构造法,1,、,DFA,的一个状态是,NFA,的一个状态集合,2,、读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2,s,k,，,则,DFA,到达状态,s,1,s,2,s,k,1,2,a,开始,0,a,b,b,0,0,1,a,b,a,0,2,b,3.3,有 限 自 动 机,未画完,3.3,有 限 自 动 机,3.3,.3,NFA,到,DFA,的变换,子集构造法,子集构造法,-closure(s),从,NFA,的状态,S,出发，只用,转换就能到达的状态的集合,-closure(T),从,NFA,的状态集合,T,中每个状态出发，只用,转换就能到达的状态的集合,Move(T,a),状态集合,T,中每个状态通过,a,能到达的所有状态集合,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,子集构造法,找出,U=,-closure(T),对于,U,，以及任意符号,a,，找出,U,通过,a,能到达的集合,V=,Move(,U,a)，并计算,V=,-closure(V),U,通过,a,到达的状态即为,V,，,U-a-V,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,3.3,有 限 自 动 机,3.3,.3,NFA,到,DFA,的变换,子集构造法：,状态转换表的构造,例(,a,|,b,)*,ab,，,NFA,如下，把它变换为,DFA,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,状态,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,状态,A,=0,1,2,4,7,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,3.3,有 限 自 动 机,输入符号,a,b,A,B,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,状态,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,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,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,B,D,开始,a,A,a,b,b,a,b,C,b,a,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,2,开始,a,0,a,b,b,a,b,识别语言,(,a,|,b,),*,ab,的,自动机,3.3,有 限 自 动 机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,2,开始,a,0,a,b,b,a,b,子集构造法不一定得到最简,DFA,3.3,有 限 自 动 机,识别语言,(,a,|,b,),*,ab,的,自动机,DFA,的化简,3.3.4 DFA,的化简,构造最简,DFA,：,构造状态集合的初始划分,：两个子集,接受状态子集,F,和非接受状态子集,S F,3.3,有 限 自 动 机,3.3.4 DFA,的化简,构造最简,DFA,：,构造状态集合的初始划分,：两个子集,接受状态子集,F,和非接受状态子集,S F,应用下面的过程构造,new,For,中的每个子集,G,，,do begin,把,G,划分为若干子集，,G,的两个状态,s,和,t,在同一子集中，当且仅当对任意输入符号,a,，,s,和,t,的,a,转换都到,的同一子集中,在,new,中，用,G,的划分代替,G,End,3.3,有 限 自 动 机,3.3.4 DFA,的化简,构造最简,DFA,：,构造状态集合的初始划分,：两个子集,接受状态子集,F,和非接受状态子集,S F,应用下面的过程构造,new,For,中的每个子集,G,，,do begin,把,G,划分为若干子集，,G,的两个状态,s,和,t,在同一子集中，当且仅当对任意输入符号,a,，,s,和,t,的,a,转换都到,的同一子集中,在,new,中，用,G,的划分代替,G,End,如果,new,=,，则,final,=,；否则令,=,new,，转上步,3.3,有 限 自 动 机,3.3.4 DFA,的化简,构造最简,DFA,：,构造状态集合的初始划分,：两个子集,接受状态子集,F,和非接受状态子集,S F,应用下面的过程构造,new,For,中的每个子集,G,，,do begin,把,G,划分为若干子集，,G,的两个状态,s,和,t,在同一子集中，当且仅当对任意输入符号,a,，,s,和,t,的,a,转换都到,的同一子集中,在,new,中，用,G,的划分代替,G,End,如果,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,B,D,开始,a,A,a,b,b,a,b,C,b,a,从正则表达式到有限自动机,从正则式建立识别器的步骤,从正则式构造,NFA,（本节介绍）,用语法制导的算法，它用正则式语法结构来指导构造过程,把,NFA,变成,DFA,（子集构造法，已介绍）,将,DFA,化简（合并不可区别状态，也已介绍）,3,.4,从正则式到有限自动机,首先构造识别,和字母表中一个符号的,NFA,重要特点：仅一个接受状态，它没有向外的转换,i,开始,识别正则式,的,NFA,a,f,i,f,开始,识别正则式,a,的,NFA,3,.4,从正则式到有限自动机,构造识别主算符为选择的正则式的,NFA,重要特点：仅一个接受状态，它没有向外的转换,f,i,开始,识别正则式,s,|,t,的,NFA,N,(,s,),N,(,t,),3,.4,从正则式到有限自动机,构造识别主算符为连接的正则式的,NFA,重要特点：仅一个接受状态，它没有向外的转换,识别正则式,st,的,NFA,i,N,(,s,),f,开始,N,(,t,),3,.4,从正则式到有限自动机,构造识别主算符为闭包的正则式的,NFA,重要特点：仅一个接受状态，它没有向外的转换,N,(,s,),f,开始,识别正则式,s,*,的,NFA,i,3,.4,从正则式到有限自动机,对于加括号的正则式,(,s,),，,使用,N,(,s,),本身作为它的,NFA,3,.4,从正则式到有限自动机,本方法产生的,NFA,有,下列性质,N,(,r,),的状态数最多是,r,中符号和算符总数的两倍,N,(,r,),只有一个接受状态，接受状态没有向外的转换,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,本方法产生的,NFA,有,下列性质,N,(,r,),的每个状态有一个用,的符号标记的指向其它结点的转换，或者最多两个指向其它结点的,转换,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,6,7,8,a,b,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,(,a,|,b,),*,ab,的两个,NFA,的比较,1,2,开始,a,0,a,b,b,手工构造,:,算法构造,:,3,.4,从正则式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,重点,从正则式建立识别器的步骤,从正则式构造NFA,把NFA变成DFA,将DFA化简,练习,为正则式,(a|b)*a(a|b)(a|b),构造,NFA,用子集构造法将,NFA,转换为,DFA,用状态转换图表示接受正则式,(a|b)*aa,的,DFA,画出接受,(1|01)*0*,所描述语言的最简,DFA,的状态转换图,练习,用子集构造法给出如下,NFA,到,DFA,的转换表,0,1,2,3,a,a,b,a,a,b,a,b,a,b,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富知识，,培养逻辑思维能力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培养文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的知识面。,有许多书籍还能培养我们的道德情操，,给我们巨大的精神力量，,鼓舞我们前进,。,