资源描述
11.2 有穷自动机有穷自动机n确定型有穷自动机确定型有穷自动机(DFA)n非确定型有穷自动机非确定型有穷自动机(NFA)n带带转移的转移的NFA(-NFA)111.2 有穷自动机确定型有穷自动机(DFA)1确定型有穷自动机确定型有穷自动机定义定义 确定型有穷自动机确定型有穷自动机(DFA)是一个有序是一个有序5元组元组M=Q,q0,F ,其中其中 (1)状态集合状态集合Q:非空有穷集合非空有穷集合 (2)输入字母表输入字母表:非空有穷集合非空有穷集合 (3)状态转移函数状态转移函数:Q Q (4)初始状态初始状态 q0 Q (5)终结状态集终结状态集 F Q 控制器控制器anaia2a12确定型有穷自动机定义 确定型有穷自动机(DFA)是一个有序5DFA接受的语言接受的语言把把扩张到扩张到Q*上上*:Q*Q,递归定义如下递归定义如下 q Q,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 3DFA接受的语言把扩张到Q*上*:Q*Q,DFA接受的语言接受的语言(续续)例例1 M=q0,q1,a,q0,q1 (q0,a)=q1,(q1,a)=q0 L(M)=a2k+1|k N4DFA接受的语言(续)例1 M=q0,q1,a非确定型有穷自动机非确定型有穷自动机定义定义 非确定型有穷自动机非确定型有穷自动机(NFA)M=Q,q0,F,其中其中 Q,q0,F 的定义与的定义与 DFA 的相同的相同,而而 :Q P(Q)5非确定型有穷自动机定义 非确定型有穷自动机(NFA)5实例实例 q0 q1 *q2 q3 *q401 q0,q3 q2 q4 q4 q0,q1 q2 q2 q4例例2 一台一台NFA6实例 q0 q1 *qNFA接受的语言接受的语言*:Q*Q 递归定义如下递归定义如下:q Q,a 和和 w*(q,)=q *(q,wa)=定义定义 w*,如果如果*(q0,w)F,则称则称M接受接受w.M接受的字符串的全体称作接受的字符串的全体称作M接受的语言接受的语言,记作记作L(M),即即 L(M)=w*|*(q0,w)F 7NFA接受的语言*:Q*Q 递归定义如下:qQ例例2(续续)L(G)=x00y,x11y|x,y 0,1*w*(q0,w)110101101110110q0,q1q0,q3q0,q1q0,q1,q2q0,q2,q38例2(续)L(G)=x00y,x11y|x,DFA与与NFA的等价性的等价性 用用M=Q,q0,F 模拟模拟 M=Q,q0,F Q=P(Q),q0=q0 F=A Q|AF A Q 和和 a,定理定理 对每一个对每一个NFA M 都存在都存在DFA M 使得使得L(M)=L(M )9DFA与NFA的等价性 用M=Q,q0,F模拟实例模拟实例NFA MDFA M 0 1q0 q1*q2q0,q1 q0 q2 0 1q0 q1*q2q0,q1*q0,q2*q1,q2*q0,q1,q2 q0,q1 q0 q2 q0,q1,q2 q0 q0,q1 q0 q2 q0,q1,q2 q0 10模拟实例NFA MDFA M 0 模拟实例模拟实例(续续)0 1q0 q0,q1*q0,q1,q2 q0,q1 q0q0,q1,q2 q0q0,q1,q2 q0不可达状态不可达状态:从初始状态出发永远不可能达到的状态从初始状态出发永远不可能达到的状态删去所有的不可达状态删去所有的不可达状态,不会改变不会改变FA接受的语言接受的语言.如如M 中的中的q1,q2,q0,q2,q1,q2和和都是不可达状都是不可达状态态,删去这些状态得到删去这些状态得到M 11模拟实例(续)0 带带转移的非确定型有穷自动机转移的非确定型有穷自动机转移转移:不读如何符号不读如何符号,自动转移状态自动转移状态.-NFA:Q()P(Q)定理定理 对每一个对每一个-NFA M 都存在都存在DFA M 使得使得 L(M)=L(M)DFA,NFA 和和-NFA 接受同一个语言类接受同一个语言类12带转移的非确定型有穷自动机转移:不读如何符号,自动转用用DFA模拟模拟-NFA设设-NFA M=Q,q0,F ,q Qq的的闭包闭包E(q):从从q出发出发,经过经过转移能够到达的所转移能够到达的所有状态有状态,递归定义如下递归定义如下 (1)E(q)包含包含q;(2)如果如果p E(q),则则(p,)E(q).例例3 -NFA M 0 1 q0 q1*q2q1 q2 q2 q0qE(q)q0q1q2q0,q2q1q0,q213用DFA模拟-NFA设-NFA M=Q,q0,用用DFA模拟模拟-NFA(续续)模拟的方法与用模拟的方法与用DFA模拟不带模拟不带的的NFA的方法基本相同的方法基本相同,只是要用只是要用E(q)代替代替q.用用DFA M=Q,q0,F 模拟模拟-NFA M=Q,q0,F Q=P(Q),q0=E(q0)F =A Q|AF A Q和和a,构造构造DFA M 时时不需要对不可达状态进行计算不需要对不可达状态进行计算,做法如下做法如下:从从q0=E(q0)开始开始,对每一个对每一个a 计算计算 的值的值,然后对每一个新出然后对每一个新出现的子集计算现的子集计算 的值的值,重复进行重复进行,直至没有新的子集出现为止直至没有新的子集出现为止.14用DFA模拟-NFA(续)模拟的方法与用DFA模拟不带的模拟实例模拟实例例例3(续续)L(M)=L(M)=(01)n|n 0 0 1 q0 q1*q2 q1 q2 q2 q0 0 1 *q0,q2 q1 q1 q0,q2 -NFA MDFA M 15模拟实例例3(续)L(M)=L(M)=(01)n 11.3 有穷自动机和正则文法有穷自动机和正则文法 的等价性的等价性n用用-NFA模拟右线性文法模拟右线性文法n用右线性文法模拟用右线性文法模拟DFA1611.3 有穷自动机和正则文法 的等价性用有穷自动机和正则文法的等价性有穷自动机和正则文法的等价性定理定理 设设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接受接受.17有穷自动机和正则文法的等价性定理 设G是右线性文法,则存在用用-NFA模拟右线性文法模拟右线性文法设右线性文法设右线性文法G=V,T,S,P -NFA M=Q,q0,F 构造如下构造如下:Q=V qf,q0=S,F=qf,=T*-|存在存在AB P或或A P A V和和 ,若若AB P,则则(A,)中含有中含有B;若若A P,则则(A,)中含有中含有qf;,(qf,)=18用-NFA模拟右线性文法设右线性文法G=V,T,S,P 模拟实例模拟实例L(G)=L(M)=(11)m0n|m 1,n 0 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 11 0 S A*qf S,A A qf 19模拟实例L(G)=L(M)=(11)m0n|m1,用用右线性文法模拟右线性文法模拟DFA 设设DFA M=Q,q0,F 右线性文法右线性文法G=V,T,S,P 构造如下构造如下:V=Q,T=,S=q0 q Q和和,若若(q,a)=p,则有产生式则有产生式qap 若若q F,则有产生式则有产生式q20用右线性文法模拟DFA 设DFA M=Q,q0,F模拟实例模拟实例 0 1 q0 q1*q2 q1 q0 q2 q1 q0 q2DFA MG=V,T,S,P V=q0,q1,q2,T=0,1,S=q0P:q00q1 q01q0 q10q2 q11q1 q20q0 q21q2 q2L(M)=L(G),它们是所有含它们是所有含3k+2(k 0)个个0的的0,1串组成的集合串组成的集合21模拟实例 0 1 q0 q1
展开阅读全文