《有穷自动机.ppt》由会员分享，可在线阅读，更多相关《有穷自动机.ppt（21页珍藏版）》请在三一办公上搜索。
1、1,11.2 有穷自动机,确定型有穷自动机(DFA)非确定型有穷自动机(NFA)带转移的NFA(-NFA),2,确定型有穷自动机,3,DFA接受的语言,把扩张到Q*上*:Q*Q,递归定义如下qQ,a和w*(q,)=q*(q,wa)=(*(q,w),a)定义 w*,如果*(q0,w)F,则称 M接受w.M接受的字符串的全体称作M接受的语言,记作 L(M),即 L(M)=w*|*(q0,w)F,4,DFA接受的语言(续),例1 M=q0,q1,a,q0,q1(q0,a)=q1,(q1,a)=q0 L(M)=a2k+1|kN,5,非确定型有穷自动机,定义 非确定型有穷自动机(NFA)M=Q,q0,F
2、,其中 Q,q0,F 的定义与 DFA 的相同,而:Q P(Q),6,实例,例2 一台NFA,7,NFA接受的语言,*:Q*Q 递归定义如下:qQ,a 和 w*(q,)=q*(q,wa)=定义 w*,如果*(q0,w)F,则称M接受w.M接受的字符串的全体称作M接受的语言,记作L(M),即 L(M)=w*|*(q0,w)F,8,例2(续),L(G)=x00y,x11y|x,y0,1*,9,DFA与NFA的等价性,用M=Q,q0,F 模拟 M=Q,q0,F Q=P(Q),q0=q0 F=AQ|AF AQ 和 a,定理 对每一个NFA M 都存在DFA M 使得L(M)=L(M),10,模拟实例,
3、NFA M,DFA M,11,模拟实例(续),不可达状态:从初始状态出发永远不可能达到的状态删去所有的不可达状态,不会改变FA接受的语言.如M中的q1,q2,q0,q2,q1,q2和都是不可达状态,删去这些状态得到M,12,带转移的非确定型有穷自动机,转移:不读如何符号,自动转移状态.-NFA:Q()P(Q)定理 对每一个-NFA M 都存在DFA M 使得 L(M)=L(M)DFA,NFA 和-NFA 接受同一个语言类,13,用DFA模拟-NFA,设-NFA M=Q,q0,F,qQq的闭包E(q):从q出发,经过转移能够到达的所有状态,递归定义如下(1)E(q)包含q;(2)如果pE(q),
4、则(p,)E(q).例3-NFA M,14,用DFA模拟-NFA(续),模拟的方法与用DFA模拟不带的NFA的方法基本相同,只是要用E(q)代替q.,用DFA M=Q,q0,F 模拟-NFA M=Q,q0,F Q=P(Q),q0=E(q0)F=AQ|AF AQ和a,构造DFA M时不需要对不可达状态进行计算,做法如下:从q0=E(q0)开始,对每一个a计算的值,然后对每一个新出现的子集计算的值,重复进行,直至没有新的子集出现为止.,15,模拟实例例3(续),L(M)=L(M)=(01)n|n0,-NFA M,DFA M,16,11.3 有穷自动机和正则文法 的等价性,用-NFA模拟右线性文法用
5、右线性文法模拟DFA,17,有穷自动机和正则文法的等价性,定理 设G是右线性文法,则存在-NFA M 使得L(M)=L(G);设M是DFA,则存在右线性文法G使得L(G)=L(M).定理 下述命题是等价的:(1)L是正则语言;(2)语言L能由右线性文法生成;(3)语言L能由左线性文法生成;(4)语言L能被DFA接受;(5)语言L能被NFA接受;(6)语言L能被-NFA接受.,18,用-NFA模拟右线性文法,设右线性文法G=V,T,S,P-NFA M=Q,q0,F 构造如下:Q=Vqf,q0=S,F=qf,=T*-|存在ABP或AP AV和,若ABP,则(A,)中含有B;若AP,则(A,)中含有
6、qf;,(qf,)=,19,模拟实例,L(G)=L(M)=(11)m0n|m1,n0,G=V,T,S,P V=A,S T=0,1 P:S11S S11A A0A A,-NFA M=Q,S,qf Q=A,S,qf=11,0,20,用右线性文法模拟DFA,设DFA M=Q,q0,F 右线性文法G=V,T,S,P 构造如下:V=Q,T=,S=q0 qQ和,若(q,a)=p,则有产生式qap 若qF,则有产生式q,21,模拟实例,DFA M,G=V,T,S,P,V=q0,q1,q2,T=0,1,S=q0P:q00q1 q01q0 q10q2 q11q1 q20q0 q21q2 q2,L(M)=L(G),它们是所有含3k+2(k0)个0的0,1串组成的集合,
