非确定的有限状态自动机ppt课件.ppt

非确定的有限状态自动机NON-DETERMINISTIC FINITE AUTOMATON, NFA第三章第三章第三章第三章 有限状态自动机有限状态自动机有限状态自动机有限状态自动机1引言FA的修改的修改DFA对于同一个输入，从同一个状态出发只能有一对于同一个输入，从同一个状态出发只能有一个转移；个转移；能否修改能否修改FA，使它对同一个输入从同一个状态出发，使它对同一个输入从同一个状态出发可以有零个、一个或多个转移；可以有零个、一个或多个转移；从而得到一个更为紧凑从而得到一个更为紧凑(状态数量较少状态数量较少)、更为容易、更为容易设计的自动机设计的自动机非确定有穷状态自动机非确定有穷状态自动机￿ ￿(non-deterministic finite automaton, NFA)2提要主要内容主要内容NFA非形式化描述、形式定义、非形式化描述、形式定义、NFA与与DFA的等价性；的等价性； -NFA形式定义、形式定义、￿ ￿ -NFA与与NFA的等价性的等价性重点重点NFA和和 -NFA的概念、的概念、DFA和和NFA以及以及 -NFA和和NFA之间的等价转换方法；之间的等价转换方法；难点难点对对NFA和和 -NFA概念的理解；概念的理解；NFA与与DFA的等价性的等价性证明；证明；3提要主要内容主要内容NFA非形式化描述、形式定义、非形式化描述、形式定义、NFA与与DFA的等价性；的等价性； -NFA形式定义、形式定义、￿ ￿ -NFA与与NFA的等价性的等价性重点重点NFA和和 -NFA的概念、的概念、DFA和和NFA以及以及 -NFA和和NFA之间的等价转换方法；之间的等价转换方法；难点难点对对NFA和和 -NFA概念的理解；概念的理解；NFA与与DFA的等价性的等价性证明；证明；4NFA• 非形式描述非形式描述• 形式定义形式定义• 扩展转移函数扩展转移函数• 从从NFA构造构造DFA• NFA与与DFA的等价性的等价性5NFA的非形式化描述NFA对同一个输入符号，从一个状态出发可以对同一个输入符号，从一个状态出发可以有零个、一个或多个转移。

有零个、一个或多个转移q1q201Sq00,1M1q1q201Sq00,1M2L(M1)={x|x为为01结尾的结尾的0和和1的串的串}L(M1)={x|x为为以以0开始、开始、1结尾的结尾的0和和1的串的串}6NFA的非形式化描述的非形式化描述￿ ￿(CONT.)NFA与与DFA的区别的区别并不是对于所有的并不是对于所有的(q,a)Q, (q,a)都有一个状都有一个状态与它对应；态与它对应；并不是对于所有的并不是对于所有的(q,a) Q, (q,a)只对应一个状只对应一个状态；态；NFA在任意时刻可以处于有穷多个状态；在任意时刻可以处于有穷多个状态；NFA具有具有““智能智能””具备同时处理多个状态的能力；具备同时处理多个状态的能力；具备对输入进行预测的能力；具备对输入进行预测的能力；7NFA的非形式化描述￿ ￿(CONT.)例：例：M1如何接受如何接受00101q1q201Sq00,1M100101q0q0q0q0q0q0q1q1q1q2q2不能继续不能继续不能继续不能继续8NFA的形式定义的形式定义非确定的有穷状态自动机非确定的有穷状态自动机(Non-deterministic finite automaton, NFA)五元组：五元组：￿ ￿M=(Q, ∑, δ, q0, F)￿ ￿有穷状态集有穷状态集输入字母表输入字母表状态转移函数状态转移函数开始状态开始状态q0∈∈Q终止状态集终止状态集F Q–δ: Q×∑2Q，， (q, a)∈∈Q×∑,δ(q, a)= {p1,p2,…,pm}•M在状态在状态q读入字符读入字符a，可以选择地将状态变成，可以选择地将状态变成p1,p2,…,或或pm ；；•将读头向右移动一个带方格而指向输入字符串的下一个字符；将读头向右移动一个带方格而指向输入字符串的下一个字符；9NFA的表示的表示•接受接受{x|x∈∈{0,1}*，且，且x含有子串含有子串00或或11}的的NFA的的表示表示01→q0{q0, q1}{q0, q2}q1{q3}Φq2Φ{q3}*q3{q3}{q3}状态转移表状态转移表q2q1q31100Sq00,10,1状态转移图状态转移图M=({q0, q1, q2, q3}, {0, 1},  , q0, {q0 , q3})  (q0, 0)={q0, q2},  (q0, 1)={q0, q2},  (q1, 0)={q3},  (q1, 1)=Φ, (q2, 0)=Φ,  (q2, 1)={q3},  (q3, 0)={q3},  (q3, 1)={q3} 四元组四元组10把状态函数扩展到串设设NFA￿ ￿M=(Q,  ,  , q0, F) : Q→2Q扩展扩展 定义定义 : Q*→2Q 的递归定义的递归定义￿ ￿(1) 基础：基础：q Q，， ￿ ￿(q,  )={q}；；(2) 归纳：设串归纳：设串x形如形如wa (w*，，a)，， q Q,   (q, w)={p1,p2, …, pk}，则，则   (q, wa)= {p| r(q, w), 使得使得p(r, a)}￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿可以不区分可以不区分  (q, a)和和  (q, a)  (q, a)=   (q, a)11把状态函数扩展到串￿ ￿(CONT.)设设x=a1a2…an * * ，，则则  (q, x)的计算如下：的计算如下：举例：用举例：用 描述右图所示描述右图所示的的NFA处理处理01100的过程的过程q2q1q31100Sq00,10,11.  (q0,  )={q0} 2.  (q0, 0)= (q0, 0)={q0, q1} 3.  (q0, 01)= (q0, 1)(q1, 1)={q0, q2} Φ={q0, q2} 4.  (q0, 011)= (q0, 1)(q2, 1)={q0, q2} {q3}={q0, q2, q3} 5.  (q0, 0110)= (q0, 0)(q2, 0)(q3, 0) ={q0, q1} Φ {q3}={q0, q1, q3} 6.  (q0, 01100)= (q0, 0)(q1, 0)(q3, 0)={q0, q1} {q3} {q3}={q0, q1, q3} 12NFA接受的语言NFA接受接受(识别识别)的字符串的字符串 x∈ ∈ *，，如果如果 (q0, ,x) ∩∩ F，则称，则称x被被M接受接受；；如果如果 (q0, ,x)∩∩F=，则称，则称M不接受不接受x￿ ￿；；NFA接受接受(识别识别)的语言的语言L(M)={x| x  *且且 (q0, ,x)∩∩F}13NFA与与DFA的比较的比较•DFA vs. NFA–都是正则语言的识别模型都是正则语言的识别模型；；–从定义角度，对于一个输入字符，从定义角度，对于一个输入字符，•NFA可以进入若干个状态可以进入若干个状态；；•DFA只能进入一个惟一的状态；只能进入一个惟一的状态；–从从DFA看待问题的角度来说，看待问题的角度来说，•NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的在一起的“总效果总效果”相当于它处于一个相当于它处于一个“综合状态综合状态”；；•可让可让DFA用一个状态去对应用一个状态去对应NFA的一组状态的一组状态。

•DFA可看作是一种特殊的可看作是一种特殊的NFA；；14NFA与与DFA的对应关系的对应关系NFA MN=(Q,  ,  N, q0, FN)与与DFA MD=(Q2,  ,  D, q0 , FD)的对应关系的对应关系NFA从开始状态从开始状态q0启动，相应的启动，相应的DFA则则从状态从状态[q0]启动，所以启动，所以q0 =[q0]；；对于对于NFA 的一个状态组的一个状态组{q1, ,q2, ,…, ,qn}如果如果NFA在此状态组时读入字符在此状态组时读入字符a后可以进入状态组后可以进入状态组{p1, , p2, ,…, ,pm},则让相应的则让相应的DFA在状态在状态[q1, ,q2, ,…, ,qn]读入字符读入字符a时，进入时，进入状态状态[p1, ,p2, ,…, ,pm]；；DFA能做能做NFA所做的一切！所做的一切！为了区分，用[…]表 示 DFA上的状态集合{…}15从从NFA构造等价的构造等价的DFA设设NFA MN=(QN,  ,  N, q0, FN)，构造，构造DFA MD=(QD,  ,  D, [q0], FD)，使得，使得L(MN)=L(MD)方法一：子集构造法方法一：子集构造法MN和和MD具有相同的字母表；具有相同的字母表；MD的初始状态是只包含的初始状态是只包含MN初始状态的集合，为区初始状态的集合，为区别记作别记作[q0]；；QD是是QN的幂集，即的幂集，即￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿；；FD是所有至少含有一个是所有至少含有一个MN的接受状态的的接受状态的MN的状态的状态集合的集合，即：集合的集合，即：FD={S|SFN且且S  QN}；； S   QN和和a，，为了计算为了计算 D，需要检查，需要检查S中的所有状态中的所有状态p，看看，看看MN在输入在输入a时从时从p进入那些状态，这些状态的并集即进入那些状态，这些状态的并集即 D.16从从NFA构造等价的构造等价的DFA (CONT.)例例￿ ￿3-7 构造下图所示的构造下图所示的NFA 对应的对应的DFAq2q1q31100Sq00,10,101→q0{q0, q1}{q0, q2}q1{q3}Φq2Φ{q3}*q3{q3}{q3}NFA状态转移图状态转移图NFA状态转移表状态转移表17从从NFA构造等价的构造等价的DFA (CONT.)状态01 [q0][q0, q1][q0, q2] [q1][q3][Φ] [q2][Φ][q3] *[q3][q3][q3] [q0, q1][q0, q1, q3][q0, q2] [q0, q2][q0, q1][q0, q2, q3] *[q0, q3][q0, q1, q3][q0, q2, q3] [q1, q2][q3][q3] *[q1, q3][q3][q3] *[q2, q3][q3][q3] [q0, q1, q2][q0, q1, q3][q0, q2, q3] *[q0, q1, q3][q0, q1, q3][q0, q2, q3] *[q0, q2, q3][q0, q1, q3][q0, q2, q3] *[q1, q2, q3][q3][q3]*[q0, q1, q2, q3][q0, q1, q3][q0, q2, q3] [Φ][Φ][Φ]•针对针对QN所有子集所有子集S和所有输入符号计算和所有输入符号计算 D(S, a)18从从NFA构造等价的构造等价的DFA (CONT.)•不可达状态不可达状态(inaccessible stae)(inaccessible stae)–如果存在从如果存在从[q[q0 0] ]对应的顶点发，到达某个状态对应的顶对应的顶点发，到达某个状态对应的顶点的路点的路，，•则称该状态从开始状态是可达的则称该状态从开始状态是可达的；；–否则，就称该状态从开始状态是不可达的否则，就称该状态从开始状态是不可达的；；19从从NFA构造等价的构造等价的DFA (CONT.)状态01 [q0][q0, q1][q0, q2] [q1][q3][Φ] [q2][Φ][q3] *[q3][q3][q3] [q0, q1][q0, q1, q3][q0, q2] [q0, q2][q0, q1][q0, q2, q3] *[q0, q3][q0, q1, q3][q0, q2, q3] [q1, q2][q3][q3] *[q1, q3][q3][q3] *[q2, q3][q3][q3] [q0, q1, q2][q0, q1, q3][q0, q2, q3] *[q0, q1, q3][q0, q1, q3][q0, q2, q3] *[q0, q2, q3][q0, q1, q3][q0, q2, q3] *[q1, q2, q3][q3][q3]*[q0, q1, q2, q3][q0, q1, q3][q0, q2, q3] [Φ][Φ][Φ]20从从NFA构造等价的构造等价的DFA (CONT.)绘制绘制DFA状态转移图状态转移图不可达的状态是无用的或无意义的，可以去掉不可达的状态是无用的或无意义的，可以去掉[q0,q1][q0,q1,q3]1100S[q0]10状态01 [q0][q0, q1][q0, q2] [q0, q1][q0, q1, q3][q0, q2] [q0, q2][q0, q1][q0, q2, q3] *[q0, q1, q3][q0, q1, q3][q0, q2, q3] *[q0, q2, q3][q0, q1, q3][q0, q2, q3][q0,q2][q0,q2,q3]0101 121从从NFA构造等价的构造等价的DFA (CONT.)小结：子集构造法主要步骤小结：子集构造法主要步骤(1) 根据给定根据给定NFA MN，构造其状态集合的所有子集，，构造其状态集合的所有子集，即幂集即幂集￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿；；(2) ，计算，计算(3) 从从[q0]依次判断依次判断[S]是否可达状态；是否可达状态；(4) 去掉所有不可达状态，剩下的状态及其相应的去掉所有不可达状态，剩下的状态及其相应的转移就构成转移就构成DFA的状态转移表。

的状态转移表22从从NFA构造等价的构造等价的DFA (CONT.)方法二：画图法方法二：画图法先画出开始状态先画出开始状态[q0]的图的图；；如果图中有未处理的顶点如果图中有未处理的顶点任选一个未处理的状态任选一个未处理的状态[q1, ,q2, ,…, ,qn]；；对对 中的每个字符中的每个字符a，计算，计算 ([q1, ,q2, ,…, ,qn], ,a)；；如果如果 ([q1, ,q2, ,…, ,qn]，，a)已经是图的一个顶点，已经是图的一个顶点，则在图中画一条从顶点则在图中画一条从顶点[q1, ,q2, ,…, ,qn]到顶点到顶点 ([q1, ,q2, ,…, ,qn]，，a)标记为标记为a的弧；的弧；如果如果 ([q1, ,q2, ,…, ,qn]，，a)不是图的一个顶点，不是图的一个顶点，则在图中增加一个标记为则在图中增加一个标记为 ([q1, ,q2, ,…, ,qn]，，a)的顶点，的顶点，并画一条从顶点并画一条从顶点[q1, ,q2, ,…, ,qn]到顶点到顶点 ([q1, ,q2, ,…, ,qn]，，a)标记为标记为a的弧；的弧；如此重复下去，直到图中不存在未处理的顶点如此重复下去，直到图中不存在未处理的顶点。

23从从NFA构造等价的构造等价的DFA (CONT.)01→q0{q0, q1}{q0, q2}q1{q3}Φq2Φ{q3}*q3{q3}{q3}[q0,q1]10S[q0][q0,q2](3) 考察状态考察状态 [q0, q1]关于关于0和和1的转移的转移[q0,q1,q3]01(4) 考察状态考察状态 [q0, q2]关于关于0和和1的转移的转移01[q0,q2,q3](5) 考察状态考察状态 [q0, q1, q3]关于关于0和和1的转移的转移01(6) 考察状态考察状态 [q0, q2, q3]关于关于0和和1的转移的转移01例：用绘图法构造例例：用绘图法构造例3-7所示的所示的NFA 对应的对应的DFA(2) 考察状态考察状态 [q0]关于关于0和和1的转移的转移(1) 先画出开始状态先画出开始状态 [q0]24NFA与与DFA等价等价定理定理￿ ￿3-1 NFA与与DFA等价等价证明证明(1)(1)构造与构造与NFA M1等价的等价的DFA M2设设M1=(Q1, , , , 1, ,q0, ,F1)，，构造构造M2=(Q2,  ,  2, [q0], F2)Q2=2QF2={[p1, ,p2, ,…, ,pm]|{p1, ,p2, ,…, ,pm} Q1且且{p1, ,p2, ,…, ,pm}∩∩F1 Φ}  2([q1, ,q2, ,…, ,qn], ,a)=[p1, ,p2, ,…, ,pm]  1({q1, ,q2, ,…, ,qn}, ,a)= {p1, ,p2, ,…, ,pm}25NFA与与DFA等价等价(CONT.)(2)(2) x x* *，施归纳于，施归纳于|x|证明：证明： 1(q0, ,x)= {p1, ,p2, ,…, ,pm}   2([q0], ,x)= [p1, ,p2, ,…, ,pm]当当|x|=0时，时，x=εε 1(q0, , )= {q0},  2([q0], ,  )=[q0], 结论成立；结论成立；设当设当|x|=n时结论成立，往证当时结论成立，往证当|x|=n+1时结论也成时结论也成立立不妨设不妨设x=wa，，|w|=n，，a 1(q0, wa)= 1( 1(q0, w), a) = 1({q1, q2, …, qn}, a) ={p1, p2, …, pm}由归纳假设由归纳假设  1(q0,w)={q1,q2,…,qn}  2([q0],w)=[q1,q2,…,qn]26NFA与与DFA等价等价(CONT.)根据根据 2的定义的定义  2([q1, q2, …, qn], a)=[p1, p2, …, pm]1({q1, q2, …, qn}, a)={p1, p2, …, pm}；；于是，于是，  2([q0],wa)=  2( 2([q0],w),a) =  2([q1, ,q2, ,…, ,qn], ,a) =[p1, ,p2, ,…, ,pm]；；因此，如果因此，如果 1(q0, ,wa)= {p1, ,p2, ,…, ,pm}则必有则必有 2([q0], ,wa)= [p1, ,p2, ,…, ,pm]；；由上述推导可知，反向的推导也成立；由上述推导可知，反向的推导也成立；因此结论对因此结论对|x|=n+1也成立；也成立；由归纳法原理，结论对由归纳法原理，结论对 x*成立。

成立27NFA与与DFA等价等价(CONT.)(3) 证明证明L(M1)=L(M2)设设x L(M1)，且，且 1(q0, ,x)= {p1, ,p2, ,…, ,pm}，，则则 1(q0, ,x)∩∩F1 ΦΦ；；即即{p1, ,p2, ,…, ,pm}∩∩F1  ΦΦ；；由由F2的定义，的定义，[p1, ,p2, ,…, ,pm] F2；；再由结论再由结论(2)知知 2([q0], ,x)=[p1, ,p2, ,…, ,pm]；；于是，于是，x L(M2)；；故故L(M1)  L(M2)；；反过来推，可得反过来推，可得L(M2)   L(M1)；；综合综合(1)(1)、、(2)(2)和和(3)(3)，定理成立定理成立28-NFA• 非形式描述非形式描述• 形式定义形式定义•  闭包闭包• 扩展转移函数扩展转移函数• NFA与与DFA的等价性的等价性29 -NFA的非形式描述的非形式描述•构造接受语言构造接受语言{0n1m2k|n，，m，，k≥1}的的NFA M1q0Sq1q3q2012012•构造接受语言构造接受语言{0n1m2k|n，，m，，k≥0}的的NFA M22q0Sq1q3q201201212•显然，构造显然，构造M2比构造比构造M1复杂很多复杂很多30 -NFA的非形式描述的非形式描述(续续)•接受语言接受语言{0n1m2k|n，，m，，k≥0}的的NFA 能否构造成能否构造成下图所示的下图所示的M3Sq0q2q1εε012–M3在某一状态下可以不移动读头在某一状态下可以不移动读头(即读入字符即读入字符)，而知改，而知改变状态；变状态；–M3的构造显然比的构造显然比M2更容易；更容易；–希望希望M3和和M2是等价的是等价的31 -NFA的形式定义的形式定义带空移动的非确定有穷状态自动机带空移动的非确定有穷状态自动机 Non-deterministic finite automaton with  -moves,  -NFA五元组：五元组：￿ ￿M=(Q, ∑, δ, q0, F)￿ ￿有穷状态集有穷状态集输入字母表输入字母表状态转移函数状态转移函数开始状态开始状态q0∈∈Q终止状态集终止状态集F Q– : Q ( ∪∪{ })2Q ，，• (q, a) Q,  (q, a)={p1,p2,…,pm}：：M在状态在状态q读入字符读入字符a，，可以选择地将状态变成可以选择地将状态变成p1,p2,…,或或pm，并将将读头向右移格而，并将将读头向右移格而指向输入字符串的下一个字符；指向输入字符串的下一个字符；• q Q，， (q,  )={p1, p2, …,pm} ：表示：表示M在状态在状态q不读入任何字不读入任何字符，即符，即M在状态在状态q做一个空移动做一个空移动(又称为又称为 移动移动)，并选择地将状，并选择地将状态变成态变成p1, p2, …或或pm ；；32 -NFA的表示的表示•接受语言接受语言{0n1m2k|n，，m，，k≥0}的的 -NF的表示的表示 012→q0{q1}{q0}q1{q2}{q1}*q2{q2}状态转移表状态转移表状态转移图状态转移图M=({q0, q1, q2}, {0, 1, 2},  , q0, {q3})  (q0,  )={q1},  (q0, 0)={q0},  (q0, 1)=,  (q0, 2)=, (q1,  )={q2},  (q1, 0)=,  (q1, 1)={q1},  (q1, 2)=, (q2,  )=,  (q2, 0)=,  (q2, 1)=,  (q2, 2)={q2},四元组四元组Sq0εε012q1q233 -闭包闭包( -CLOSURE)设设 -NFA M=(Q, ∑, δ, q0, F)，， q Q, q的的 -闭闭包，定义为包，定义为从从q经所有的经所有的 ￿ ￿路径可以到达的状态路径可以到达的状态(包括包括q自身自身) - CLOSURE(q)={p|从从q到到p有一条标记为有一条标记为ε的路的路} P Q，，例子例子      q1q2q3q5q6q4q7abcS -CLOSE(q1)={q1,q2,q4,q5,q6,q7} -CLOSE(q2)={q2,q4,q5,q6,q7} -CLOSE(q7)={q5, q7} -CLOSE({q2,q7})= -CLOSE(q2) -CLOSE(q7)={q2,q4,q5,q6,q7}34扩展状态转移函数扩展状态转移函数扩展状态转移函数到输入串扩展状态转移函数到输入串设设NFA￿ ￿M=(Q,  ,  , q0, F) : Q{ }2Q扩展扩展 定义：定义： : Q*2Q 的递归定义的递归定义￿ ￿(1) 基础：基础：q Q，， ￿ ￿(q,  )= -CLOSURE(q)；；(2) 归纳：设串归纳：设串x=wa (w*，，a)，， q Q, 假设假设 ￿ ￿(q, w)={p1,p2, …, pk}，且，且则则￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿35扩展状态转移函数扩展状态转移函数(CONT.)扩展状态转移函数到子集扩展状态转移函数到子集设设NFA￿ ￿M=(Q,  ,  , q0, F) : Q{ }2Q进一步扩展进一步扩展 ：：2Q2Q (P, a) 2Q进一步扩展进一步扩展  : 2Q*2Q (P, x) 2Q*￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿36扩展状态转移函数扩展状态转移函数(CONT.)注意：注意：在在 -NFA中，对任意中，对任意a，，q Q，，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿ (q, a)  (q, a) (q, a)包含所有可从包含所有可从q q出发、沿着标记为出发、沿着标记为a a的路径的路径( (包括包括标记为标记为 的弧的弧) )所能到达的各个状态；所能到达的各个状态； (q, a)仅包含所有可从仅包含所有可从q q出发、沿着标记为出发、沿着标记为a a的弧线所能的弧线所能到达的那些状态；到达的那些状态；类似地类似地￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿ (q,  )  (q,  )在在 -NFA中，必须区分中，必须区分 和和 ！！37扩展状态转移函数扩展状态转移函数(CONT.)状态状态   012 012q0{q1}{q0}ФФ{q0,q1,q2} {q0,q1,q2} {q1,q2}{q2}q1{q2}Ф{q1}Ф{q1,q2}Ф{q1,q2}{q2}q2ФФФ{q2}{q2}ФФ{q2}Sq0q2q1εε01238扩展状态转移函数扩展状态转移函数(CONT.)例：根据下图所示的例：根据下图所示的 -NFA计算计算 (q0,01)(1)计算计算 (q0,  )￿￿￿￿￿￿￿￿ (q0,  )= -CLOSURE(q0)￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿={q0, q1, q2}(2)计算计算 (q0, 0)￿￿￿￿￿￿￿￿ (q0, 0)= -CLOSURE( ( (q0,  ), 0))￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿=  -CLOSURE( ({q0, q1, q2}, 0)) =  -CLOSURE( (q0, 0)(q1, 0)(q2, 0)) =  -CLOSURE({q0} ) =  -CLOSURE({q0})={q0, q1, q2}(3)计算计算 (q0, 01) (q0, 01)= -CLOSURE( ( (q0, 0), 1))￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿=  -CLOSURE( ({q0, q1, q2}, 1)) =  -CLOSURE( (q0, 1)(q1, 1)(q2, 1)) =  -CLOSURE( {q1}) =  -CLOSURE({q1})={q1,q2}Sq0εε012q1q239 -NFA接受的语言接受的语言– x∈∑∈∑*，，•如果如果 (q0, x)  F，，则称则称x被被M接受；接受；–于是于是，， -NFA M接受或识别的语言接受或识别的语言L(M) •设设 -NFA M=(Q,  ,  , q0, F)，，•如果如果 (q0, x)  F=，，则称则称x不被不被M接受；接受；40从从 -NFA构造等价的构造等价的NFA给定给定 -NFA M1=(Q,  ,  1, q0, F1)，构造，构造NFA M2=(Q,  ,  2, q0, F2)，使得，使得L(M2)=L(M1)M2和和M1具有相同的字母表、相同的状态集和相同具有相同的字母表、相同的状态集和相同的初始状态；的初始状态；接受状态接受状态F2状态转移函数状态转移函数 2￿￿￿￿￿￿￿￿￿￿ (q, a) Q，， 2(q, a)= 1 (q, a)41从从 -NFA构造构造NFA (CONT.)例：设有下表所示的例：设有下表所示的 -NFA M1 =(Q,  ,  1, q0, F1) ，构造相应的，构造相应的NFA M2确定确定F2因为因为 -CLOSURE(q0)={q0, q1, q2} F1则则F2=F1 {q0}={q0, q2}通过计算通过计算 1 (q, a)，确定，确定 2=  1 (q, a)即可得到即可得到NFA M2=(Q,  ,  2, q0, F2) 1 = -CLOSURE( 1( 1 (q,  ), a)状态状态 012*q0{q0,q1,q2}{q0,q1,q2}{q1,q2} {q2}q1{q1,q2}Ф{q1,q2} {q2}*q2{q2}ФФ{q2} 012→q0{q1} {q0}q1{q2}{q1}*q2{q2}S0,11,2012q1q2q00,1,242 -NFA与NFA等价定理定理 3-2  -NFA与与NFA等价等价证明证明：：设有设有 -NFA M1=(Q, , , , 1, ,q0, ,F1)(1) 构造与之等价的构造与之等价的NFA M2 –取取NFA M2=(Q, , , , 2, ,q0, ,F2) ；；43 -NFA与NFA等价￿ ￿(CONT.)(2)  x+, 施归纳于施归纳于|x|证明证明，， –当当|x|=1时，由时，由 2的定义，结论成立。

的定义，结论成立 –设当设当|x|=n结论成立，需要证明结论成立，需要证明|x|=n +1时结论也成立时结论也成立 •不妨设不妨设|x|=n +1时，时，x=wa，其中，其中|w|=n, a∈∈∑ 归纳假设归纳假设NFA相关定义相关定义NFA移动函数定义移动函数定义44 -NFA与NFA等价￿ ￿(CONT.)M2定义定义ε-NFA有关有关定义定义–即即|x|=n+1|x|=n+1时结论成立时结论成立 45 -NFA与NFA等价￿ ￿(CONT.)(3) 证明对证明对 x+,  2(q0,x) F21 (q0, x) F1(4) 证明证明L(M1)L(M2)由由(1)、、(2)、、(3)和和(4)的结论，的结论，L(M1)=L(M2)，，定理得证定理得证46小结DFA的两个扩展的两个扩展要点要点NFA和和 -NFA相关基本概念；相关基本概念；从从NFA到到DFA以及从以及从 -NFA到到NFA的等价构的等价构造；造；自动机等价性证明的基本方法自动机等价性证明的基本方法基于文法基于文法语言识别语言识别DFANFA -DFA回溯回溯多个多个转移转移问题问题空移动空移动47课后阅读和作业必读必读蒋宗礼蒋宗礼, 姜守旭姜守旭. 形式语言与自动机理论形式语言与自动机理论. 北京：清北京：清华大学出版社华大学出版社, 2003. [ [pp.102-115] ]参考参考John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman 著，刘田等译著，刘田等译. 自动机理论、语言和计算导自动机理论、语言和计算导论论. 机械工业出版社，中信出版社，机械工业出版社，中信出版社，2005. [ [pp.37-55] ] 作业作业￿ ￿4教材：教材：pp.126-130￿习题11,￿15上交时间：上交时间：2008-10-16 2008-10-16 星期四星期四48。