形式语言自动机有限自动机幻灯片.ppt

《形式语言自动机有限自动机幻灯片.ppt》由会员分享，可在线阅读，更多相关《形式语言自动机有限自动机幻灯片.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言自动机有限自动机第1页，共53页，编辑于2022年，星期六2College of Computer Science&Technology,BUPT第一节第一节 有限自动机有限自动机一、有限状态系统的概念一、有限状态系统的概念n状态:状态是可以将事物区分开的一种标识。n具有离散状态的系统:如数字电路(0,1),十字路口的红绿灯。离散状态系统的状态数是有限的.n具有连续状态的系统:比如水库的水位,室内温度等可以连续变化,即有无穷个状态.n有限状态系统必然是离散状态系统（而且状态数有限）,因为只有有限个状态.第2页，共53页，编辑于2022年，星期六3College of Computer

2、Science&Technology,BUPT第一节第一节 有限自动机有限自动机n实例实例 一一个个人人带带着着一一头头狼狼，一一头头羊羊，以以及及一一棵棵青青菜菜，处处于于河河的的左左岸岸。有有一一条条小小船船,每每次次只只能能携携带带人人和和其其余余的的三三者者之之一一。人人和和他他的的伴伴随随品品都都希希望望渡渡到到河河的的右右岸岸，而而每每摆摆渡渡一一次次，人人仅仅能能带带其其中中之之一一。然然而而如如果果人人留留下下狼狼和和羊羊不不论论在在左左岸岸还还是是在在右右岸岸，狼狼肯肯定定会会吃吃掉掉羊羊。类类似似地地，如如果果单单独独留留下下羊羊和和菜菜，羊羊也也肯肯定定会会吃吃掉掉菜菜。

3、如如何何才才能能既既渡渡过过河河而而羊和菜又不被吃掉呢羊和菜又不被吃掉呢?第3页，共53页，编辑于2022年，星期六4College of Computer Science&Technology,BUPTMGWC（处处于于左左岸岸的的子子集集处处于右岸的子集于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)第4页，共53页，编辑于2022年，星期六5College of Computer Science&Technology,BUPT二、有限自动机的概念二、有限自动机的概念有限自动机的概念有限自动机的概念n具有离散 输入 输出系统的一种数学模型(可以没有

4、输出，比较特殊的也可以没有输入).n有限的状态n状态+输入状态转移n每次转换的后继状态都唯一 DFAn每次转换的后继状态不唯一 NFA第5页，共53页，编辑于2022年，星期六6College of Computer Science&Technology,BUPTFA FA 的模型的模型 FA可以理解成一个控制器可以理解成一个控制器,它读一条输入带上的它读一条输入带上的字符。字符。101101有限有限控制器控制器(1)控制器包括有限状态控制器包括有限状态;(2)从左到右依次读取字符从左到右依次读取字符;(3)状态状态+激励激励 状态迁移状态迁移(根据当前所处状态和输入字符进根据当前所处状态和输

5、入字符进行状态转移行状态转移)第6页，共53页，编辑于2022年，星期六7College of Computer Science&Technology,BUPT 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合有限自动机的五要素有限自动机的五要素q0q1q2q3第7页，共53页，编辑于2022年，星期六8College of Computer Science&Technology,BUPT三、三、DFADFA的形式定义的形式定义定义定义:DFA是一个五元组 M=(Q,T,q0,F)nQ:有限的状态集合nT:有限的输入字母表

6、n:转换函数(状态转移集合):QT Qnq0:初始状态，q0 QnF:终止状态集,F Qn表示方法：表示方法：第8页，共53页，编辑于2022年，星期六9College of Computer Science&Technology,BUPT转转 移移 图图 表表 示示 的的 DFADFA Q=q0,q1,q2,q3 T=0,1 (q0,0)=q2,(q0,1)=q1 (q1,0)=q3,(q1,1)=q0 (q2,0)=q0,(q2,1)=q3 (q3,0)=q1,(q3,1)=q2 q0 F=q0,q3 q0q1q2q3第9页，共53页，编辑于2022年，星期六10College of Co

7、mputer Science&Technology,BUPT转转 移移 表表 表表 示示 的的 DFADFA q0q1q2 q301q2q1q3q0q0q3q1q2 Q=q0,q1,q2,q3 T=0,1 (q0,0)=q2,(q0,1)=q1 (q1,0)=q3,(q1,1)=q0 (q2,0)=q0,(q2,1)=q3 (q3,0)=q1,(q3,1)=q2 q0 F=q0,q3 第10页，共53页，编辑于2022年，星期六11College of Computer Science&Technology,BUPT四、四、扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串函数：函数：接

8、收一个字符串的状态转移函数。接收一个字符串的状态转移函数。:Q T*Q n 对任何对任何q Q，定义：定义：n 1.(q,)=q 2.若若是一个字符串是一个字符串,a是一个字符是一个字符定义定义:(q,a)=(q,),a)对于对于DFA:(q,a)=(q,),a)=(q,a)，即对即对于单个字符时于单个字符时和和是相等的。为了方便，以后在是相等的。为了方便，以后在不引起混淆时用不引起混淆时用代替代替 第11页，共53页，编辑于2022年，星期六12College of Computer Science&Technology,BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 q0

9、q1q2 q301q2q1q3q0q0q3q1q2 举例举例 (q0,)=q0 (q0,0)=(q0,0)=q2 (q0,00)=(q2,0)=q0 (q0,001)=(q0,1)=q1 (q0,0010)=(q1,0)=q3q0q1q2q3第12页，共53页，编辑于2022年，星期六13College of Computer Science&Technology,BUPTDFADFA接受的语言接受的语言n被被DFA接接收收的的字字符符串串:输输入入结结束束后后使使DFA的的状状态态到到达达终终止止状态。否则该字符串不能被状态。否则该字符串不能被D FA接收接收.nDFA接收的语言接收的语言:

10、被被DFA接收的字符串的集合接收的字符串的集合.L(M)=(q0,)F n例：例：T=0，1接收含有奇数个接收含有奇数个0的任意串的任意串第13页，共53页，编辑于2022年，星期六14College of Computer Science&Technology,BUPT五、格局五、格局n为为描描述述有有限限自自动动机机的的工工作作过过程程，对对于于它它在在某某一一时时刻刻的的工工作作状状态态，可可用用两两个个信信息息表表明明：当当前前状状态态q，待待输输入入字字符符串串。两两者者构构成成一一个个瞬瞬时时描描述述，用用（q,）表示，称为格局。表示，称为格局。n初始格局：（初始格局：（q0,)n

11、终止格局：终止格局：(q,),q F第14页，共53页，编辑于2022年，星期六15College of Computer Science&Technology,BUPTn如图，接受如图，接受001010的格局的格局（q0,001010）(q2,01010)(q0,1010)(q1,010)(q3,10)(q2,0)(q0,)n格局数量是无限的。格局数量是无限的。n有限状态自动机是无记忆的。有限状态自动机是无记忆的。例如接受例如接受0010101111和接受和接受01011111时，都可以进入格时，都可以进入格局局(q0,1111)。格局示例格局示例q0q1q2q3第15页，共53页，编辑于2

12、022年，星期六16College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n自动机的设计是一个创造过程，没有简单的算法或过程。自动机的设计是一个创造过程，没有简单的算法或过程。n技巧：假设自己是机器，思考如何去实现机器的任务技巧：假设自己是机器，思考如何去实现机器的任务。n为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。字符串时需要记住哪些关键的东西。（找出状态）（找出状态）例例1：构造自动机识别所有由奇数个构造自动机识别所有由

13、奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。关键关键：不需要记住所看到的整个字符串，只需记住至此所看到的不需要记住所看到的整个字符串，只需记住至此所看到的a、b个数是偶数还是奇数。个数是偶数还是奇数。q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第16页，共53页，编辑于2022年，星期六17College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n例例2：构造有限自动机：构造有限自动机M，识别识别0,1上的语言上的语言nL=x000y|x,y0.1*n分析：该语言特点是每个串都包含连分析：该语言特点是每个

14、串都包含连续续3 3个个0 0的子串，自动机的任务是识别的子串，自动机的任务是识别/检查是否存在子串检查是否存在子串000000。由于字符是逐一读入，当读入一个由于字符是逐一读入，当读入一个0 0时，时，就需记住（状态就需记住（状态q q1 1),),若接着读入的还是若接着读入的还是0 0，则需记住已读入，则需记住已读入连续的连续的2 2个个0 0了（状态了（状态q q2 2),),若接着读入若接着读入的还是的还是0 0，则需记住已读入连续的，则需记住已读入连续的2 2个个0 0了（状态了（状态q q3 3),),第17页，共53页，编辑于2022年，星期六18College of Compu

15、ter Science&Technology,BUPT设计有限自动机设计有限自动机例例3：构造有限自动机：构造有限自动机M，识，识别别0,1,2上的语言上的语言,每个字符每个字符串代表的数字能整除串代表的数字能整除3。分析：如果一个十进制数的所有位的数字分析：如果一个十进制数的所有位的数字之和能整除之和能整除3 3，则该十进制数就能整除，则该十进制数就能整除3 3。一个十进制数除以一个十进制数除以3 3，余数只能为，余数只能为0 0、1 1、2 2。-设计为状态。设计为状态。状态状态q q0 0表示已读入的数字和除表示已读入的数字和除3 3余余0,0,状态状态q q1 1表示已读入的数字和除表

16、示已读入的数字和除3 3余余1,1,状态状态q q2 2表示已读入的数字和除表示已读入的数字和除3 3余余2,2,第18页，共53页，编辑于2022年，星期六19College of Computer Science&Technology,BUPT第二节第二节不确定的有限自动机不确定的有限自动机(NFA)NFA)修改修改DFA的模型的模型,使之在某个状态使之在某个状态,对应一个输入对应一个输入,可以有可以有多个转移多个转移,到达不到达不 同的状态同的状态,则称为不确定的有限自动机。则称为不确定的有限自动机。例：例：(1)(2)第19页，共53页，编辑于2022年，星期六20College of

17、 Computer Science&Technology,BUPT一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元组是一个五元组,M=(Q,T,q0,F).其中其中是是QT-2Q的函数的函数,其余与其余与DFA相同相同.n如果接收一个字符串后如果接收一个字符串后NFA进入一个状态集进入一个状态集,而此集而此集合中包含合中包含一个以上一个以上F中的状态中的状态,则则称称NFA接收该字接收该字符串符串.第20页，共53页，编辑于2022年，星期六21College of Computer Science&Technology,BUPT(1)(2)pq r0 q q q

18、,r 1pq r0 p r r 1 p,q 转移图和转移表表示的转移图和转移表表示的NFANFA注意：转移表中的每一项都是一个集合。含空集第21页，共53页，编辑于2022年，星期六22College of Computer Science&Technology,BUPT二二、NFANFA的状态转移函数的状态转移函数与与 DFA 唯一不同之处唯一不同之处 :Q T 2Q同样同样,可扩展为可扩展为 (:Q T*2Q)1.(q,)=q 含义:不允许无输入的状态变化.2.(q,a)=p|存在存在r(q,)p(r,a)n含义:(q,a)对应的状态集合是(q,)对应的每个状态下再接收字符a以后可能到达的

19、状态集合的并集.即若若 (q,)=r 1,r 2,r k,则则n (q,a)=(r i,a)n其中其中 T*,a T，r i Q第22页，共53页，编辑于2022年，星期六23College of Computer Science&Technology,BUPT 举例举例 (p,)=p (p,0)=q (p,01)=q,r (p,010)=q (p,0100)=q (p,01001)=q,r pq r0 q q q,r 1扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串第23页，共53页，编辑于2022年，星期六24College of Computer Science&Technol

20、ogy,BUPTNFA 接受的语言接受的语言 设一个设一个 NFA A=(Q,T,q0,F)定义定义 A 的语言：的语言：L(A)=(q0,)F 第24页，共53页，编辑于2022年，星期六25College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性n为什么要讨论等价性？问题的提出为什么要讨论等价性？问题的提出nNFA识别语言的复杂性，参见教材P59的例子。需回溯和智能才能识别句子。nDFA具有结构简单清晰的特点。n是否存在NFA-DFA的转换方法？n如果找到这样的转换方法，是否正确和普适？一般研究方法：找到一种方法（

21、构造方法）或性质，然后证明一般研究方法：找到一种方法（构造方法）或性质，然后证明该方法该方法/性质的正确性。所谓定理就是被证明是正确的性质。性质的正确性。所谓定理就是被证明是正确的性质。第25页，共53页，编辑于2022年，星期六26College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性nDFA是是NFA的特例的特例,所以所以NFA必然能接收必然能接收DFA能接能接收的语言收的语言.因此因此证明等价性只要能够证明一个证明等价性只要能够证明一个NFA所能接收的语言必能被另一个所能接收的语言必能被另一个DFA所接收所接收

22、。n关键问题：是否能构造出这样的关键问题：是否能构造出这样的DFA？n分析思路：分析思路：n基于 :Q T 2Q ，将转移后的“集合”作为新的状态，表示为q1,q2,qm,注意：集合-状态。n新的转移函数的构造。n新的终止状态集合的确定第26页，共53页，编辑于2022年，星期六27College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性1.定理定理:设一个设一个NFA接受语言接受语言L,那么必然存在一个那么必然存在一个DFA接受接受L。2.证明证明:n策略:对于任意一个NFA,构造一个接收它所能接收语言的DFA，这个

23、DFA的状态对应了NFA的状态集合。即NFA幂集的元素。第27页，共53页，编辑于2022年，星期六28College of Computer Science&Technology,BUPT从从 NFA 构造等价的构造等价的 DFA (子集构造法子集构造法)设设 L 是是某某个个 NFA N=(QN,T,N,q0,FN)的的语语言言,则则存存在在一一个个 DFA M,满足满足 L(M)=L(N)=L.证明证明:定义定义 M=(QD,T,D,q0,FD),其中其中 QD=S S QN =2 Q 注意：注意：S是集合是集合 对对 S QD 和和 a T,D(S,a)=N(q,a).FD=S S Q

24、N S FN 需要证明需要证明:对任何对任何 T*,D(q0 ,)=N(q0,).归纳于归纳于|w|可可证上述命题证上述命题.q S第28页，共53页，编辑于2022年，星期六29College of Computer Science&Technology,BUPTpq r0 q q q,r 10 q 1 p q r p,q p,r q,r p,q,r q q,r q q,r q q q,r q q,r 子集构造法举例子集构造法举例1 1、初始的、初始的NFANFA2 2、子集构造，计算状态可达、子集构造，计算状态可达3 3、经筛选后的、经筛选后的DFADFA第29页，共53页，编辑于2022

25、年，星期六30College of Computer Science&Technology,BUPTpq r0 p r r 1 p,q 01 p p,q,r p p,q p p,q p,q p,r p,q,r p,r p,r p,q,r 子集构造法举例子集构造法举例第30页，共53页，编辑于2022年，星期六31College of Computer Science&Technology,BUPT证明证明:从从 NFA 构造等价的构造等价的 DFA 设设 N=(QN,T,N,q0,FN)是一个是一个 NFA,通过子集构造法通过子集构造法 得到相应的得到相应的DFA D=(QD,T,D,q0,F

26、D),则则 对任何对任何 T*,D(q0 ,)=N(q0,).证明证明:归纳于归纳于|1 设设|=0,即即 =.由定义知由定义知 D(q0,)=N(q0,)=q0.2 设设|=n+1,并并 =xa,a T.注意到注意到|x|=n.假设假设 D(q0 ,x)=N(q0,x)=p1,p2,pk .则则 D(q0 ,)=D(D(q0 ,x),a)=D(p1,p2,pk,a)=N(pi,a).=N(q0,)i=1k第31页，共53页，编辑于2022年，星期六32College of Computer Science&Technology,BUPTn 实践中实践中,通过子集构造法得到的通过子集构造法得到

27、的 DFA 的状态数目的状态数目与原与原NFA 的状态数目的状态数目大体大体相当相当.n n 在较坏的情况下在较坏的情况下,上述上述 DFA 的状态数目接近于所有子集的的状态数目接近于所有子集的数目数目.n n 举例举例 由如下由如下 NFA 构造的构造的 DFA 的状态数目为的状态数目为2n子集构造法得到的状态数子集构造法得到的状态数q0q1q2qn第32页，共53页，编辑于2022年，星期六33College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为什么会引出带为什么会引出带转换转换的的NFA？n与NFA的目的一样

28、，也是为了表达简单直观。n例：表示接受字符串或由若干个0,或接若干个1,或再接若干个2的自动机？n问题：如何构造设计这个自动机呢？q0q1q2012第33页，共53页，编辑于2022年，星期六34College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为什么会引出带为什么会引出带转换转换的的NFA？（？（续续）n可以用来识别关键字集合，程序语言中的应用n例：设计识别关键字web,ebay.n问题：如何构造设计这个自动机呢？第34页，共53页，编辑于2022年，星期六35College of Computer Scienc

29、e&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn一、定义一、定义概念:当输入空串(无输入)时，也能引起状态的转移.例：输入输入“002”时的转移格局：时的转移格局：q0q1q2012第35页，共53页，编辑于2022年，星期六36College of Computer Science&Technology,BUPT -NFA 的形式定义的形式定义 一个一个 -NFA 是一个五元组是一个五元组 A=(Q,T,q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NF

30、A 的不同之处的不同之处 :Q (T )2Q第36页，共53页，编辑于2022年，星期六37College of Computer Science&Technology,BUPT -NFA NFA 的形式定义的形式定义n(q0，0)=q0,(q0，1)=,n(q0，2)=,(q0，)=q1,n(q1，0)=,(q1，1)=q1,q1,n(q1，2)=,(q1，)=q2,n(q2，0)=,(q2，1)=,n(q2，2)=q2,q2,(q2，)=,q0q1q2012第37页，共53页，编辑于2022年，星期六38College of Computer Science&Technology,BUPT

31、 -NFA 如何接受输入符号串如何接受输入符号串q1q0q2q3q5 ,+,q4 该该 -NFA 可以接受的字符串如：可以接受的字符串如：3.14 +.314 314.第38页，共53页，编辑于2022年，星期六39College of Computer Science&Technology,BUPT二、二、-闭包（闭包（closure）概念概念定义定义1：状态状态 q 的的 -闭包闭包，记为，记为 -CLOSURE 或或ECLOSE，定义为从，定义为从 q 经所有的经所有的 路径可以到达的状路径可以到达的状态集合（包括态集合（包括q自身），自身），如：如：q0q1q2012 -CLOSURE

32、(q0)=q0,q1,q2 -CLOSURE(q1)=q1,q2 -CLOSURE(q2)=q2 第39页，共53页，编辑于2022年，星期六40College of Computer Science&Technology,BUPT定义定义2 2：状态子集：状态子集I I 的的-闭包：闭包：-CLOSURE(I)-CLOSURE(q)或或 qI =-CLOSURE(q)|qI 例：例：-CLOSURE(q1，q2)-CLOSURE(q1)-CLOSURE(q2)q1，q2第40页，共53页，编辑于2022年，星期六41College of Computer Science&Technology

33、,BUPTIa Ia 概念：概念：对于状态子集对于状态子集I Q，任意任意aT，定义定义Ia如下：如下：Ia=-Closure(P)其中其中P=（I，a）.即即P是从是从I中的状态经过一条标中的状态经过一条标a的边可以到达的状态集合的边可以到达的状态集合 第41页，共53页，编辑于2022年，星期六42College of Computer Science&Technology,BUPT例：例：I Iq0q0，q1q1，求求I I1 1I I1 1 -CLOSURE-CLOSURE（I I，1 1）-CLOSURE-CLOSURE（q0q0，q1q1，1 1）-CLOSURE-CLOSURE（

34、q1 q1）q1q1，q2q2q0q1q2012第42页，共53页，编辑于2022年，星期六43College of Computer Science&Technology,BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 设一个设一个 -NFA,:Q T 2Q 扩充定义扩充定义 :Q T*2Q 对任何对任何q Q，定义：定义：1 (q,)=-CLOSURE(q)2(q,a)-CLOSURE(P)=-CLOSURE(q,),a)3(q，a)-CLOSURE(P)其中：其中：P p|存在存在r(q，)p(r，a)注意：注意：此时此时(q，a)(q，a)，因为因为(q，a)表示由表

35、示由q出发，只沿着标出发，只沿着标a 的路径所能到达的状态，的路径所能到达的状态，而而(q，a)表示由表示由q出发，沿着标出发，沿着标a(包括包括转换在内转换在内)的路径所能到达的状态的路径所能到达的状态.第43页，共53页，编辑于2022年，星期六44College of Computer Science&Technology,BUPT-NFA中，中，与与 函数的不同函数的不同 举例举例 计算计算 (q0,a)(q0，)-CLOSURE(q0)q0，q2(q0，a)-CLOSURE(q0，)，a)-CLOSURE(q0，q2，a)-CLOSURE(q0，a)(q2，a)-CLOSURE(q1

36、 q3)q1，q2 q3q1，q2，q3 同理：同理：(q0，aa)q3-CLOSURE(q0)q0，q2-CLOSURE(q1)q1，q2-CLOSURE(q2)q2-CLOSURE(q3)q3第44页，共53页，编辑于2022年，星期六45College of Computer Science&Technology,BUPT三、三、-NFA 的的 语语 言言 设一个设一个 -NFA M=(Q,T,q0,F)定义定义 M 的语言：的语言：L(M)=|(q0,)F 即即满足满足(q0，)含有含有F的一个状态的一个状态 第45页，共53页，编辑于2022年，星期六46College of Com

37、puter Science&Technology,BUPT四、四、-NFA与与NFA的等价的等价1.-NFANFA具有转移的NFA是不具转移的NFA的一般情况,所以只要证明下面的定理即可:定定理理:如如果果L被被一一个个具具有有 转转移移的的NFA接接收收,那那么么L可被一个不具可被一个不具 转移的转移的NFA 接收接收.证证明明思思路路:构构造造一一个个不不具具 转转移移的的NFA,证证明明其其接接收收具有具有 转移的转移的NFA所接受的语言所接受的语言.第46页，共53页，编辑于2022年，星期六47College of Computer Science&Technology,BUPT从从

38、 -NFA 构造等价的构造等价的 无无 NFAn 设设 M=(Q,T,q0,F)是一个是一个 -NFA,n可构造一个无可构造一个无 的的 NFA M1=(Q,T,1,q0,F1),n构造思路：构造思路：1.状态集合不变；状态集合不变；2.转移函数的构造；转移函数的构造；对任何对任何 a T,1(q,a)=(q,a)-构造方法构造方法 (注意注意与与的区别与联系。而的区别与联系。而1和和1是相等的。是相等的。)3.F1 F q0 若若-CLOSURE(q0)F F 否则否则第47页，共53页，编辑于2022年，星期六48College of Computer Science&Technology

39、,BUPT从从 -NFA 构造等价的构造等价的 无无 NFA 证明证明:采用归纳法证明采用归纳法证明1（q0，）（q0，），），|=1|=1。当当|w|=0,即即 w=时，不一定相等时，不一定相等.1(q0，)q0，而而(q0，)-CLOSURE(q0)因此，从因此，从|1开始证明开始证明 1.当当|=1时，定义相等。时，定义相等。由由1定义定义 1（q0，a）（q0，a）第48页，共53页，编辑于2022年，星期六49College of Computer Science&Technology,BUPT设当设当|=n时，时，1（q0,）=（q0,），），则则当当|=n+1时，时，左侧左侧 1

40、（q0,a）1(1（q0，），a)1(（q0，），），a)由归纳假设由归纳假设1(R，a)设设R（q0，）1(q，a)q R (q，a)q R.由由1定义定义(R，a)(（q0，），），a)R（q0，）(q0，a)右侧右侧再再证证:1（q0，）含含F1的的一一个个状状态态当当且且仅仅当当（q0，）含含F的的一一个状态个状态 （略）（略）第49页，共53页，编辑于2022年，星期六50College of Computer Science&Technology,BUPT证明同时展示了一种将证明同时展示了一种将 -NFA转化为转化为NFA的方法的方法.-NFA NFA DFA例：将将 -NFA转换

41、为转换为NFA.（图3.4.1，3.4.3）q0q1q2012q0q1q20120,11,20,1,2根据 1(q,a)=(q,a)进行构造。参见教材第50页，共53页，编辑于2022年，星期六51College of Computer Science&Technology,BUPT举例举例-请同学们完成这个变换过程请同学们完成这个变换过程q1q0q2q3q5 ,+,q4q0 q1q1q1 q4q2q2 q3 q5q3 q5第51页，共53页，编辑于2022年，星期六52College of Computer Science&Technology,BUPT有限自动机小结n确定型有限自动机确定型有限自动机DFA；n状态转移图、状态转移表；状态转移图、状态转移表；nDFA接受的语言接受的语言L（M），称为：），称为：正则语言正则语言；n非确定型有限自动机非确定型有限自动机NFA；n子集构造法，子集构造法，NFA-DFA；n带带转转移的移的NFA；1、我们需要将注意力集中到正则语言上来，2、需要采用“代数”的方法，从另一个角度来研究正则语言。第52页，共53页，编辑于2022年，星期六53College of Computer Science&Technology,BUPT第53页，共53页，编辑于2022年，星期六