形式语言自动机有限自动机精品文稿.ppt

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

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

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

3、和和菜菜又不被吃掉呢又不被吃掉呢?第3页，本讲稿共53页4College of Computer Science&Technology,BUPTMGWC（处处于于左左岸岸的的子子集集处于右岸的子集处于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)第4页，本讲稿共53页5College of Computer Science&Technology,BUPT二、有限自动机的概念二、有限自动机的概念有限自动机的概念有限自动机的概念n具有离散 输入 输出系统的一种数学模型(可以没有输出，比较特殊的也可以没有输入).n有限的状态n状态+输入状态转移n每次转换的后

4、继状态都唯一 DFAn每次转换的后继状态不唯一 NFA第5页，本讲稿共53页6College of Computer Science&Technology,BUPTFA FA 的模型的模型 FA可以理解成一个控制器可以理解成一个控制器,它读一条输入带上的它读一条输入带上的字符。字符。101101有限有限控制器控制器(1)控制器包括有限状态控制器包括有限状态;(2)从左到右依次读取字符从左到右依次读取字符;(3)状态状态+激励激励 状态迁移状态迁移(根据当前所处状态和输入字符进行根据当前所处状态和输入字符进行状态转移状态转移)第6页，本讲稿共53页7College of Computer Sci

5、ence&Technology,BUPT 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合有限自动机的五要素q0q1q2q3第7页，本讲稿共53页8College of Computer Science&Technology,BUPT三、三、DFADFA的形式定义的形式定义定义定义:DFA是一个五元组 M=(Q,T,q0,F)nQ:有限的状态集合nT:有限的输入字母表n:转换函数(状态转移集合):QT Qnq0:初始状态，q0 QnF:终止状态集,F Qn表示方法：表示方法：第8页，本讲稿共53页9College of C

6、omputer 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页10College of Computer Science&Technology,BUPT转转 移移 表表 表表 示示 的的 DFADFA q0q1q2 q301q2q1q3q0q0q3q1q2 Q=q0,q1,q2,q3 T=

7、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页11College of Computer Science&Technology,BUPT四、四、扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串函数：函数：接收一个字符串的状态转移函数。接收一个字符串的状态转移函数。:Q T*Q n 对任何对任何q Q，定义：定义：n 1.(q,)=q 2.若若是一个字符串是一个字符串,a是一个字符是一个字符定义定义:(q,a)=(q,),

8、a)对于对于DFA:(q,a)=(q,),a)=(q,a)，即对即对于单个字符时于单个字符时和和是相等的。为了方便，以后在是相等的。为了方便，以后在不引起混淆时用不引起混淆时用代替代替 第11页，本讲稿共53页12College of Computer Science&Technology,BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 q0q1q2 q301q2q1q3q0q0q3q1q2 举例举例 (q0,)=q0 (q0,0)=(q0,0)=q2 (q0,00)=(q2,0)=q0 (q0,001)=(q0,1)=q1 (q0,0010)=(q1,0)=q3q0q1q2

9、q3第12页，本讲稿共53页13College of Computer Science&Technology,BUPTDFADFA接受的语言接受的语言n被被DFA接接收收的的字字符符串串:输输入入结结束束后后使使DFA的的状状态态到到达达终终止止状状态。否则该字符串不能被态。否则该字符串不能被D FA接收接收.nDFA接收的语言接收的语言:被被DFA接收的字符串的集合接收的字符串的集合.L(M)=(q0,)F n例：例：T=0，1接收含有奇数个接收含有奇数个0的任意串的任意串第13页，本讲稿共53页14College of Computer Science&Technology,BUPT五、格

10、局五、格局n为为描描述述有有限限自自动动机机的的工工作作过过程程，对对于于它它在在某某一一时时刻刻的的工工作作状状态态，可可用用两两个个信信息息表表明明：当当前前状状态态q，待待输输入入字字符符串串。两两者者构构成成一一个个瞬瞬时时描描述述，用（用（q,）表示，称为格局。表示，称为格局。n初始格局：（初始格局：（q0,)n终止格局：终止格局：(q,),q F第14页，本讲稿共53页15College of Computer Science&Technology,BUPTn如图，接受如图，接受001010的格局的格局（q0,001010）(q2,01010)(q0,1010)(q1,010)(q

11、3,10)(q2,0)(q0,)n格局数量是无限的。格局数量是无限的。n有限状态自动机是无记忆的。有限状态自动机是无记忆的。例如接受例如接受0010101111和接受和接受01011111时，都可以进入格时，都可以进入格局局(q0,1111)。格局示例格局示例q0q1q2q3第15页，本讲稿共53页16College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n自动机的设计是一个创造过程，没有简单的算法或过程。自动机的设计是一个创造过程，没有简单的算法或过程。n技巧：假设自己是机器，思考如何去实现机器的任务技巧：假设自己是机器，思考如何去

12、实现机器的任务。n为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。个字符串时需要记住哪些关键的东西。（找出状态）（找出状态）例例1：构造自动机识别所有由奇数个构造自动机识别所有由奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。关键关键：不需要记住所看到的整个字符串，只需记住至此所看到的不需要记住所看到的整个字符串，只需记住至此所看到的a、b个数是偶数还是奇数。个数是偶数还是奇数。q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第16页，本讲稿共53页17Colleg

13、e of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n例例2：构造有限自动机：构造有限自动机M，识别识别0,1上的语言上的语言nL=x000y|x,y0.1*n分析：该语言特点是每个串都包含分析：该语言特点是每个串都包含连续连续3 3个个0 0的子串，自动机的任务是识别的子串，自动机的任务是识别/检查是否存在子串检查是否存在子串000000。由于字符是逐一读入，当读入一个由于字符是逐一读入，当读入一个0 0时，就需记住（状态时，就需记住（状态q q1 1),),若接着读入的还是若接着读入的还是0 0，则需记住已读入，则需记住已读入连续的连续的2

14、 2个个0 0了（状态了（状态q q2 2),),若接着读入的若接着读入的还是还是0 0，则需记住已读入连续的，则需记住已读入连续的2 2个个0 0了了（状态（状态q q3 3),),第17页，本讲稿共53页18College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机例例3：构造有限自动机：构造有限自动机M，识，识别别0,1,2上的语言上的语言,每个字每个字符串代表的数字能整除符串代表的数字能整除3。分析：如果一个十进制数的所有位的数字之分析：如果一个十进制数的所有位的数字之和能整除和能整除3 3，则该十进制数就能整除，则该十进制数就能

15、整除3 3。一个十进制数除以一个十进制数除以3 3，余数只能为，余数只能为0 0、1 1、2 2。-设计为状态。设计为状态。状态状态q q0 0表示已读入的数字和除表示已读入的数字和除3 3余余0,0,状态状态q q1 1表示已读入的数字和除表示已读入的数字和除3 3余余1,1,状态状态q q2 2表示已读入的数字和除表示已读入的数字和除3 3余余2,2,第18页，本讲稿共53页19College of Computer Science&Technology,BUPT第二节第二节不确定的有限自动机不确定的有限自动机(NFA)NFA)修改修改DFA的模型的模型,使之在某个状态使之在某个状态,对应

16、一个输入对应一个输入,可以有多可以有多个转移个转移,到达不到达不 同的状态同的状态,则称为不确定的有限自动机。则称为不确定的有限自动机。例：例：(1)(2)第19页，本讲稿共53页20College of Computer Science&Technology,BUPT一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元组是一个五元组,M=(Q,T,q0,F).其中其中是是QT-2Q的函数的函数,其余与其余与DFA相同相同.n如果接收一个字符串后如果接收一个字符串后NFA进入一个状态集进入一个状态集,而而此集合中包含此集合中包含一个以上一个以上F中的状态中的状态,则则

17、称称NFA接接收该字符串收该字符串.第20页，本讲稿共53页21College of Computer Science&Technology,BUPT(1)(2)pq r0 q q q,r 1pq r0 p r r 1 p,q 转移图和转移表表示的NFA注意：转移表中的每一项都是一个集合。含空集第21页，本讲稿共53页22College of Computer Science&Technology,BUPT二二、NFANFA的状态转移函数的状态转移函数与与 DFA 唯一不同之处唯一不同之处 :Q T 2Q同样同样,可扩展为可扩展为 (:Q T*2Q)1.(q,)=q 含义:不允许无输入的状态变

18、化.2.(q,a)=p|存在存在r(q,)p(r,a)n含义:(q,a)对应的状态集合是(q,)对应的每个状态下再接收字符a以后可能到达的状态集合的并集.即若若 (q,)=r 1,r 2,r k,则则n (q,a)=(r i,a)n其中其中 T*,a T，r i Q第22页，本讲稿共53页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页24

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

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

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

22、FA，这个DFA的状态对应了NFA的状态集合。即NFA幂集的元素。第27页，本讲稿共53页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 QN S FN 需要证明需要证明:

23、对任何对任何 T*,D(q0 ,)=N(q0,).归纳于归纳于|w|可可证上述命题证上述命题.q S第28页，本讲稿共53页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页30College of Computer Science&Technolo

24、gy,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页31College of Computer Science&Technology,BUPT证明:从 NFA 构造等价的 DFA 设设 N=(QN,T,N,q0,FN)是一个是一个 NFA,通过子集构造法通过子集构造法 得到相应的得到相应的DFA D=(QD,T,D,q0,FD),则则 对任何对任何 T*,D(q0 ,)=N(q0,).证明证明:归纳于归纳于|1 设设|=0,即即 =.由定义知由定义知 D(q

25、0,)=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页32College of Computer Science&Technology,BUPTn 实践中,通过子集构造法得到的 DFA 的状态数目与原NFA 的状态数目大体相当.n n 在较坏的情况下,上述 DFA 的状态数目接近于所有子集的数目.n n 举例 由如下由如下 NFA 构造的构造的 DFA

26、的状态数目为的状态数目为2n子集构造法得到的状态数q0q1q2qn第32页，本讲稿共53页33College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为什么会引出带为什么会引出带转换转换的的NFA？n与NFA的目的一样，也是为了表达简单直观。n例：表示接受字符串或由若干个0,或接若干个1,或再接若干个2的自动机？n问题：如何构造设计这个自动机呢？q0q1q2012第33页，本讲稿共53页34College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为

27、什么会引出带为什么会引出带转换转换的的NFA？（？（续续）n可以用来识别关键字集合，程序语言中的应用n例：设计识别关键字web,ebay.n问题：如何构造设计这个自动机呢？第34页，本讲稿共53页35College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn一、定义一、定义概念:当输入空串(无输入)时，也能引起状态的转移.例：输入输入“002”时的转移格局：时的转移格局：q0q1q2012第35页，本讲稿共53页36College of Computer Science&Technology,BUPT-NFA 的形式定义

28、一个一个 -NFA 是一个五元组是一个五元组 A=(Q,T,q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NFA 的不同之处的不同之处 :Q (T )2Q第36页，本讲稿共53页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

29、)=,n(q2，2)=q2,q2,(q2，)=,q0q1q2012第37页，本讲稿共53页38College of Computer Science&Technology,BUPT-NFA 如何接受输入符号串q1q0q2q3q5 ,+,q4 该该 -NFA 可以接受的字符串如：可以接受的字符串如：3.14 +.314 314.第38页，本讲稿共53页39College of Computer Science&Technology,BUPT二、-闭包（closure）概念定义定义1：状态状态 q 的的 -闭包闭包，记为，记为 -CLOSURE 或或ECLOSE，定义为从，定义为从 q 经所有的经

30、所有的 路径可以到达的状态路径可以到达的状态集合（包括集合（包括q自身），自身），如：如：q0q1q2012 -CLOSURE(q0)=q0,q1,q2 -CLOSURE(q1)=q1,q2 -CLOSURE(q2)=q2 第39页，本讲稿共53页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页，本讲稿共

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

32、E（q0q0，q1q1，1 1）-CLOSURE-CLOSURE（q1 q1）q1q1，q2q2q0q1q2012第42页，本讲稿共53页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)，因为因为

33、(q，a)表示由表示由q出发，只沿着标出发，只沿着标a 的路径所能到达的状态，的路径所能到达的状态，而而(q，a)表示由表示由q出发，沿着标出发，沿着标a(包括包括转换在内转换在内)的路径所能到达的状态的路径所能到达的状态.第43页，本讲稿共53页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

34、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页45College of Computer Science&Technology,BUPT三、-NFA 的 语 言 设一个设一个 -NFA M=(Q,T,q0,F)定义定义 M 的语言：的语言：L(M)=|(q0,)F 即即满足满足(q0，)含有含有F的一个状态的一个状态 第45页，本讲稿共53页46College of Computer Science&Technology,B

35、UPT四、四、-NFA与与NFA的等价的等价1.-NFANFA具有转移的NFA是不具转移的NFA的一般情况,所以只要证明下面的定理即可:定定理理:如如果果L被被一一个个具具有有 转转移移的的NFA接接收收,那那么么L可可被一个不具被一个不具 转移的转移的NFA 接收接收.证证明明思思路路:构构造造一一个个不不具具 转转移移的的NFA,证证明明其其接接收收具有具有 转移的转移的NFA所接受的语言所接受的语言.第46页，本讲稿共53页47College of Computer Science&Technology,BUPT从 -NFA 构造等价的 无 NFAn 设设 M=(Q,T,q0,F)是一个

36、是一个 -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页48College of Computer Science&Technology,BUPT从 -NFA 构造等价的 无 NFA 证明证明:采用归纳法证明采用归纳法证明1（q0，）（q0，

37、），），|=1|=1。当当|w|=0,即即 w=时，不一定相等时，不一定相等.1(q0，)q0，而而(q0，)-CLOSURE(q0)因此，从因此，从|1开始证明开始证明 1.当当|=1时，定义相等。时，定义相等。由由1定义定义 1（q0，a）（q0，a）第48页，本讲稿共53页49College of Computer Science&Technology,BUPT设当设当|=n时，时，1（q0,）=（q0,），），则则当当|=n+1时，时，左侧左侧 1（q0,a）1(1（q0，），a)1(（q0，），），a)由归纳假设由归纳假设1(R，a)设设R（q0，）1(q，a)q R (q，a)q

38、R.由由1定义定义(R，a)(（q0，），），a)R（q0，）(q0，a)右侧右侧再再证证:1（q0，）含含F1的的一一个个状状态态当当且且仅仅当当（q0，）含含F的的一一个个状态状态 （略）（略）第49页，本讲稿共53页50College of Computer Science&Technology,BUPT证明同时展示了一种将证明同时展示了一种将 -NFA转化为转化为NFA的方法的方法.-NFA NFA DFA例：将将 -NFA转换为转换为NFA.（图3.4.1，3.4.3）q0q1q2012q0q1q20120,11,20,1,2根据 1(q,a)=(q,a)进行构造。参见教材第50页，

39、本讲稿共53页51College of Computer Science&Technology,BUPT举例-请同学们完成这个变换过程q1q0q2q3q5 ,+,q4q0 q1q1q1 q4q2q2 q3 q5q3 q5第51页，本讲稿共53页52College of Computer Science&Technology,BUPT有限自动机小结n确定型有限自动机确定型有限自动机DFA；n状态转移图、状态转移表；状态转移图、状态转移表；nDFA接受的语言接受的语言L（M），称为：），称为：正则语言正则语言；n非确定型有限自动机非确定型有限自动机NFA；n子集构造法，子集构造法，NFA-DFA；n带带转转移的移的NFA；1、我们需要将注意力集中到正则语言上来，2、需要采用“代数”的方法，从另一个角度来研究正则语言。第52页，本讲稿共53页53College of Computer Science&Technology,BUPT第53页，本讲稿共53页