形式语言自动机有限自动机PPT课件

《形式语言自动机有限自动机PPT课件》由会员分享，可在线阅读，更多相关《形式语言自动机有限自动机PPT课件（54页珍藏版）》请在装配图网上搜索。

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

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

3、lege of Computer Science&Technology,BUPTMGWC（处于左岸的子集（处于左岸的子集处于右岸的子集处于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)4College of Computer Science&Technology,BUPT二、有限自动机的概念二、有限自动机的概念有限自动机的概念有限自动机的概念n具有离散 输入 输出系统的一种数学模型(可以没有输出，比较特殊的也可以没有输入).n有限的状态n状态+输入状态转移n每次转换的后继状态都唯一 DFAn每次转换的后继状态不唯一 NFA5College of Com

4、puter Science&Technology,BUPTFA FA 的模型的模型 FA可以理解成一个控制器可以理解成一个控制器,它读一条输入带上它读一条输入带上的字符。的字符。101101有限有限控制器控制器(1)控制器包括有限状态控制器包括有限状态;(2)从左到右依次读取字符从左到右依次读取字符;(3)状态状态+激励激励 状态迁移状态迁移(根据当前所处状态和输入字符根据当前所处状态和输入字符进行状态转移进行状态转移)6College of Computer Science&Technology,BUPT 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个

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

6、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 q0q1q2q3Start011011009College of Computer 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

7、 (q3,0)=q1,(q3,1)=q2 q0 F=q0,q3 10College of Computer Science&Technology,BUPT四、四、扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串函数：函数：接收一个字符串的状态转移函数。接收一个字符串的状态转移函数。:Q T*Q 对任何对任何q Q，定义：，定义：1.(q,)=q 2.若若是一个字符串是一个字符串,a是一个字符是一个字符定义定义:(q,a)=(q,),a)对于对于DFA:(q,a)=(q,),a)=(q,a)，即对，即对于单个字符时于单个字符时和和是相等的。为了方便，以后在是相等的。为了方便，以后在不引起

8、混淆时用不引起混淆时用代替代替 11College 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)=q3q0q1q2q3Start0110110012College of Computer Science&Technology,BUPTDFADFA接受的语言接受的语言n被被DFA接收的字符串接

9、收的字符串:输入结束后使输入结束后使DFA的状态到达终的状态到达终止状态。否则该字符串不能被止状态。否则该字符串不能被D FA接收接收.nDFA接收的语言接收的语言:被被DFA接收的字符串的集合接收的字符串的集合.L(M)=(q0,)F n例：例：T=0，112Start0110接收含有奇数个接收含有奇数个0的任意串的任意串13College of Computer Science&Technology,BUPT五、格局五、格局n为描述有限自动机的工作过程，对于它在某为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当一时刻的工作状态，可用两个信息表明：当前状态前状态q

10、，待输入字符串，待输入字符串。两者构成一个瞬。两者构成一个瞬时描述，用（时描述，用（q,）表示，称为格局。）表示，称为格局。n初始格局：（初始格局：（q0,)n终止格局：终止格局：(q,),q F14College of Computer Science&Technology,BUPTn如图，接受如图，接受001010的格局的格局（q0,001010）(q2,01010)(q0,1010)(q1,010)(q3,10)(q2,0)(q0,)n格局数量是无限的。格局数量是无限的。n有限状态自动机是无记忆的。有限状态自动机是无记忆的。例如接受例如接受0010101111和接受和接受01011111

11、时，都可以进入格时，都可以进入格局局(q0,1111)。格局示例格局示例q0q1q2q3Start0110110015College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n自动机的设计是一个创造过程，没有简单的算法或过程。自动机的设计是一个创造过程，没有简单的算法或过程。n技巧：假设自己是机器，思考如何去实现机器的任务技巧：假设自己是机器，思考如何去实现机器的任务。n为判断到目前为止所看到的字符串是否满足某个语言，须估为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。算出读一个字符串时需要

12、记住哪些关键的东西。（找出状态）（找出状态）例例1：构造自动机识别所有由奇数个构造自动机识别所有由奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。关键关键：不需要记住所看到的整个字符串，只需记住至此所看到不需要记住所看到的整个字符串，只需记住至此所看到的的a、b个数是偶数还是奇数。个数是偶数还是奇数。q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb16College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n例例2：构造有限自动机：构造有限自动机M，识别识别0,1上的语言上的语言nL=x000y|x,y0.1*n

13、分析：该语言特点是每个串都包分析：该语言特点是每个串都包含连续含连续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),),17College of

14、Computer 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表示已读入的

15、数字和除表示已读入的数字和除3 3余余1,1,状态状态q q2 2表示已读入的数字和除表示已读入的数字和除3 3余余2,2,18College of Computer Science&Technology,BUPT第二节第二节不确定的有限自动机不确定的有限自动机(NFA)(NFA)修改修改DFA的模型的模型,使之在某个状态使之在某个状态,对应一个输入对应一个输入,可以有可以有多个转移多个转移,到达不到达不 同的状态同的状态,则称为不确定的有限自动机。则称为不确定的有限自动机。例：例：Startpr0,10q1(1)Startp0,11qr0,1(2)19College of Computer

16、Science&Technology,BUPT一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元组是一个五元组,M=(Q,T,q0,F).其中其中是是QT-2Q的函数的函数,其余与其余与DFA相同相同.n如果接收一个字符串后如果接收一个字符串后NFA进入一个状态集进入一个状态集,而此集合中包含而此集合中包含一个以上一个以上F中的状态中的状态,则称则称NFA接收该字符串接收该字符串.20College of Computer Science&Technology,BUPTStartpr0,10q1(1)Startp0,11qr0,1(2)pq r0 q q q,r 1

17、pq r0 p r r 1 p,q 转移图和转移表表示的转移图和转移表表示的NFANFA注意：转移表中的每一项都是一个集合。含空集21College 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以后可能到达的状态集合的并集.即若若 (q,)=r 1,r 2,

18、r k,则则 (q,a)=(r i,a)其中其中 T*,a T，r i Q22College 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扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串Startpr0,10q123College of Computer Science&Technology,BUPTNFA 接受的语言接受的语言 设一个设一个 NFA A=(Q,T,q0,F)定义定义 A 的语言：的

19、语言：L(A)=(q0,)F 24College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性n为什么要讨论等价性？问题的提出为什么要讨论等价性？问题的提出nNFA识别语言的复杂性，参见教材P59的例子。需回溯和智能才能识别句子。nDFA具有结构简单清晰的特点。n是否存在NFA-DFA的转换方法？n如果找到这样的转换方法，是否正确和普适？一般研究方法：找到一种方法（构造方法）或性一般研究方法：找到一种方法（构造方法）或性质，然后证明该方法质，然后证明该方法/性质的正确性。所谓定理性质的正确性。所谓定理就是被证明是正确的性质

20、。就是被证明是正确的性质。25College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性nDFA是是NFA的特例的特例,所以所以NFA必然能接收必然能接收DFA能接能接收的语言收的语言.因此证明等价性只要能够证明一个因此证明等价性只要能够证明一个NFA所能接收的语言必能被另一个所能接收的语言必能被另一个DFA所接收。所接收。n关键问题：是否能构造出这样的关键问题：是否能构造出这样的DFA？n分析思路：分析思路：n基于 :Q T 2Q ，将转移后的“集合”作为新的状态，表示为q1,q2,qm,注意：集合-状态。n新的转移函

21、数的构造。n新的终止状态集合的确定26College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性1.定理定理:设一个设一个NFA接受语言接受语言L,那么必然存在一个那么必然存在一个DFA接受接受L。2.证明证明:n策略:对于任意一个NFA,构造一个接收它所能接收语言的DFA，这个DFA的状态对应了NFA的状态集合。即NFA幂集的元素。27College of Computer Science&Technology,BUPT从从 NFA 构造等价的构造等价的 DFA (子集构造法子集构造法)设设 L 是某个是某个 NFA

22、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 需要证明需要证明:对任何对任何 T*,D(q0 ,)=N(q0,).归纳于归纳于|w|可可证上述命题证上述命题.q S28College of Computer Science&Technology,BUPTpq r0 q q q,r 10 q 1 p q r p,q p,r

23、 q,r p,q,r q q,r q q,r q q q,r q q,r Startp0,10q1q,r1010 子集构造法举例子集构造法举例1 1、初始的、初始的NFANFA2 2、子集构造，计算状态可达、子集构造，计算状态可达3 3、经筛选后的、经筛选后的DFADFA29College 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 Startp1p,q10100p,q,rp,r01子集构造法举例子集构造法举例Startp0,11q

24、r0,130College 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(q0,)=N(q0,)=q0.2 设设|=n+1,并并 =xa,a T.注意到注意到|x|=n.假设假设 D(q0 ,x)=N(q0,x)=p1,p2,pk .则则 D

25、(q0 ,)=D(D(q0 ,x),a)=D(p1,p2,pk,a)=N(pi,a).=N(q0,)i=1k31College of Computer Science&Technology,BUPT 实践中实践中,通过子集构造法得到的通过子集构造法得到的 DFA 的状态数目的状态数目与与原原NFA 的状态数目的状态数目大体大体相当相当.在较坏的情况下在较坏的情况下,上述上述 DFA 的状态数目接近于所有的状态数目接近于所有子集的数目子集的数目.举例举例 由如下由如下 NFA 构造的构造的 DFA 的状态数目为的状态数目为2n子集构造法得到的状态数子集构造法得到的状态数Start0,110,10

26、,10,1.q0q1q2qn32College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为什么会引出带为什么会引出带转换的转换的NFA？n与NFA的目的一样，也是为了表达简单直观。n例：表示接受字符串或由若干个0,或接若干个1,或再接若干个2的自动机？n问题：如何构造设计这个自动机呢？q0q1q2012q2q00q22q00q1q033College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn为什么会引出带为什么会引出带转换的转换的NFA？（续）？（

27、续）n可以用来识别关键字集合，程序语言中的应用n例：设计识别关键字web,ebay.n问题：如何构造设计这个自动机呢？34College of Computer Science&Technology,BUPT第四节第四节有有 转换的转换的NFANFAn一、定义一、定义概念:当输入空串(无输入)时，也能引起状态的转移.例：q2q00q22q00q1q0输入输入“002”时的转移格局：时的转移格局：q0q1q201235College of Computer Science&Technology,BUPT -NFA 的形式定义的形式定义 一个一个 -NFA 是一个五元组是一个五元组 A=(Q,T,

28、q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NFA 的不同之处的不同之处 :Q (T )2Q36College of Computer Science&Technology,BUPT -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，)=,q0q1q201237College of

29、Computer Science&Technology,BUPT -NFA 如何接受输入符号串如何接受输入符号串Start0,1,.,9.0,1,.,90,1,.,90,1,.,9.q1q0q2q3q5 ,+,q4 该该 -NFA 可以接受的字符串如：可以接受的字符串如：3.14 +.314 314.38College 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 39College 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，q240College of Computer Science&Technolo

31、gy,BUPTIa Ia 概念：概念：对于状态子集对于状态子集I Q，任意，任意aT，定义，定义Ia如下：如下：Ia=-Closure(P)其中其中P=（I，a）.即即P是从是从I中的状态经过一中的状态经过一条标条标a的边可以到达的状态集合的边可以到达的状态集合 41College 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（q1 q1）q1q1，q2q2q0q

32、1q201242College 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)表示由表示由q出发，只沿着标出发，只沿着标a 的路径所能到达的状态，的路径所能到达的状态

33、，而而(q，a)表示由表示由q出发，沿着标出发，沿着标a(包括包括转换在内转换在内)的路径所能到达的状态的路径所能到达的状态.43College 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(q1q3)q1，q2 q3q1，q2，q3 同理：同理：(q0，aa)q3q q0 0q q2 2q q3 3q q1 1aba

34、b-CLOSURE(q0)q0，q2-CLOSURE(q1)q1，q2-CLOSURE(q2)q2-CLOSURE(q3)q344College of Computer Science&Technology,BUPT三、三、-NFA 的的 语语 言言 设一个设一个 -NFA M=(Q,T,q0,F)定义定义 M 的语言：的语言：L(M)=|(q0,)F 即即 满足满足(q0，)含有含有F的一个状态的一个状态 45College of Computer Science&Technology,BUPT四、四、-NFA与与NFA的等价的等价1.-NFANFA具有转移的NFA是不具转移的NFA的一般情

35、况,所以只要证明下面的定理即可:定理定理:如果如果L被一个具有被一个具有 转移的转移的NFA接收接收,那那么么L可被一个不具可被一个不具 转移的转移的NFA 接收接收.证明思路证明思路:构造一个不具构造一个不具 转移的转移的NFA,证明其证明其接收具有接收具有 转移的转移的NFA所接受的语言所接受的语言.46College of Computer Science&Technology,BUPT从从 -NFA 构造等价的构造等价的 无无 NFA 设设 M=(Q,T,q0,F)是一个是一个 -NFA,可构造一个无可构造一个无 的的 NFA M1=(Q,T,1,q0,F1),构造思路：构造思路：状态

36、集合不变；状态集合不变；转移函数的构造；转移函数的构造；对任何对任何 a T,1(q,a)=(q,a)-构造方法构造方法 (注意注意与与的区别与联系。而的区别与联系。而1和和1是相等的。是相等的。)3.F1 Fq0 若若-CLOSURE(q0)F F 否则否则47College of Computer Science&Technology,BUPT从从 -NFA 构造等价的构造等价的 无无 NFA 证明证明:采用归纳法证明采用归纳法证明1（q0，）（q0，），），|=1|=1。当当|w|=0,即即 w=时，不一定相等时，不一定相等.1(q0，)q0，而而(q0，)-CLOSURE(q0)因此，

37、从因此，从|1开始证明开始证明 当当|=1时，定义相等。时，定义相等。由由1定义定义 1（q0，a）（q0，a）48College 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 R.由由1定义定义(R，a)(（q0，），），a)R（q0，）(q0，a)右侧右侧再证再证:1（q0，）含）含F1的一个状态当且仅当的一个状态当且仅当（q0，）含）含F的

38、一个状态的一个状态 （略）（略）49College 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)进行构造。参见教材50College of Computer Science&Technology,BUPT举例举例-请同学们完成这个变换过程请同学们完成这个变换过程Start0,1,.,9.0,1,.,90,1,.,

39、90,1,.,9.q1q0q2q3q5 ,+,q4Startq0 q1+,-q10,1,.,9q1 q4.q20,1,.,9.0,1,.,9.q2 q3 q50,1,.,9q3 q50,1,.,90,1,.,951College of Computer Science&Technology,BUPT有限自动机小结n确定型有限自动机确定型有限自动机DFA；n状态转移图、状态转移表；状态转移图、状态转移表；nDFA接受的语言接受的语言L（M），称为：），称为：正则语言正则语言；n非确定型有限自动机非确定型有限自动机NFA；n子集构造法，子集构造法，NFA-DFA；n带带转移的转移的NFA；1、我们需要将注意力集中到正则语言上来，2、需要采用“代数”的方法，从另一个角度来研究正则语言。52College of Computer Science&Technology,BUPT精品课件精品课件！53College of Computer Science&Technology,BUPT精品课件精品课件！54College of Computer Science&Technology,BUPT