形式语言与自动机ch31-33资料课件

12024/6/17College of Computer Science&Technology,BUPT第三章第三章 有限自动机与右线性文法有限自动机与右线性文法本章主要内容本章主要内容n确定有限自确定有限自动机机n非确定有限自非确定有限自动机机n确定与非确定有限自确定与非确定有限自动机的等价性机的等价性n右右线性文法和有限自性文法和有限自动机的等价性机的等价性n右右线性文法的性性文法的性质(泵浦定理浦定理)n使用使用归纳法法进行行证明的方法明的方法22024/6/17College of Computer Science&Technology,BUPT第一节第一节 有限自动机有限自动机一、有限状一、有限状态系系统的概念的概念n状状态:状状态是可以将事物是可以将事物区分区分开的一种开的一种标识。n具有离散状具有离散状态的系的系统：如数字：如数字电路路(0,1)，十字路口的十字路口的红绿灯。离散状灯。离散状态系系统的状的状态数数是有限的。是有限的。n具有具有连续状状态的系的系统：比如水：比如水库的水位，室的水位，室内温度等可以内温度等可以连续变化，即有无化，即有无穷个状个状态。n有限状有限状态系系统必然是离散状必然是离散状态系系统（而且状（而且状态数有限），因数有限），因为只有有限个状只有有限个状态。32024/6/17College of Computer Science&Technology,BUPTn实例例 一一个个人人带着着一一头狼狼，一一头羊羊，以以及及一一棵棵青青菜菜，处于于河河的的左左岸岸。有有一一条条小小船船,每每次次只只能能携携带人人和和其其余余的的三三者者之之一一。人人和和他他的的伴伴随随品品都都希希望望渡渡到到河河的的右右岸岸，而而每每摆渡渡一一次次，人人仅能能带其其中中之之一一。然然而而如如果果人人留留下下狼狼和和羊羊不不论在在左左岸岸还是是在在右右岸岸，狼狼肯肯定定会会吃吃掉掉羊羊。类似似地地，如如果果单独独留留下下羊羊和和菜菜，羊羊也也肯肯定定会会吃吃掉掉菜菜。如如何何才才能能既既渡渡过河河而而羊羊和和菜菜又又不不被被吃吃掉掉呢呢?42024/6/17College of Computer Science&Technology,BUPTMGWC（处处于于左左岸岸的的子子集集处于右岸的子集处于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)52024/6/17College of Computer Science&Technology,BUPT二、有限自动机的概念二、有限自动机的概念有限自有限自动机的概念机的概念n具有具有离散离散 输输入入 输输出出系系统的的一种一种数学模型数学模型(可可以以没没有有输输出出，比比较较特特殊殊的的也也可可以以没没有有输输入入).n有限有限的状的状态态n状状态+输入入状状态转移移n每次每次转换的后的后继状状态都唯一都唯一 DFAn每次每次转换的后的后继状状态不唯一不唯一 NFA62024/6/17College of Computer Science&Technology,BUPTFA的模型的模型 FA可以理解成一个控制器，它可以理解成一个控制器，它读一条一条输入入带上的字符。上的字符。101101有限有限控制器控制器(1)控制器包括有限状态；控制器包括有限状态；(2)从左到右依次读取字符；从左到右依次读取字符；(3)状态状态+激励激励 状态迁移状态迁移(根据当前所处状态和输入字符根据当前所处状态和输入字符进行状态转移进行状态转移)72024/6/17College of Computer Science&Technology,BUPT 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合有限自动机的五要素有限自动机的五要素q0q1q2q382024/6/17College of Computer Science&Technology,BUPT三、三、DFA的形式定义的形式定义定义:DFA是一个五元组 M=(Q,T,q0,F)nQ:有限的状有限的状态集合集合nT:有限的有限的输入字母表入字母表n:转换函数函数(状状态转移集合移集合):QT Qnq0:初始状初始状态，q0 QnF:终止状止状态集集,F Q 92024/6/17College of Computer Science&Technology,BUPT转转 移移 图图 表表 示示 的的 DFA 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 q0q1q2q3102024/6/17College of Computer Science&Technology,BUPT转转 移移 表表 表表 示示 的的 DFA 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 112024/6/17College 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)，即即对于于单个字符个字符时和和是相等的。是相等的。为了方便，以后在了方便，以后在不引起混淆不引起混淆时用用代替代替 122024/6/17College 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)=q3q0q1q2q3132024/6/17College of Computer Science&Technology,BUPTDFA接受的语言接受的语言n被被DFA接接收收的的字字符符串串:输入入结束束后后使使DFA的的状状态到到达达终止状止状态。否。否则该字符串不能被字符串不能被D FA接收接收.nDFA接收的接收的语言言:被被DFA接收的字符串的集合接收的字符串的集合.L(M)=w (q0,w)F n例：例：T=0，1接收含有奇数个接收含有奇数个0的任意串的任意串142024/6/17College of Computer Science&Technology,BUPT五、格局五、格局n为描描述述有有限限自自动机机的的工工作作过程程，对于于它它在在某某一一时刻刻的的工工作作状状态，可可用用两两个个信信息息表表明明：当当前前状状态q，待待输入入字字符符串串w。两两者者构构成成一一个个瞬瞬时描述，用（描述，用（q,w）表示，称表示，称为格局。格局。n初始格局：（初始格局：（q0,w)n终止格局：止格局：(q,),q F152024/6/17College 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)。格局示例格局示例q0q1q2q3162024/6/17College of Computer Science&Technology,BUPTn如果如果对某个某个q F,有有(q0,w)(q,),则称称输入字符串入字符串w是可被确定的有限自是可被确定的有限自动机接受的。机接受的。172024/6/17College of Computer Science&Technology,BUPT设计有限自动机设计有限自动机n自自动机的机的设计是一个是一个创造造过程，没有程，没有简单的算法或的算法或过程。程。n技巧：假技巧：假设自己是机器，思考如何去自己是机器，思考如何去实现机器的任机器的任务。n为判断到目前判断到目前为止所看到的字符串是否止所看到的字符串是否满足某个足某个语言，言，须估估算出算出读一个字符串一个字符串时需要需要记住哪些关住哪些关键的的东西。西。例：例：构造自构造自动机，机，识别所有由奇数个所有由奇数个a和奇数个和奇数个b组成的字符串。成的字符串。关关键：不需要：不需要记住所看到的整个字符住所看到的整个字符串串，只需，只需记住至此所看到住至此所看到的的a、b个数是偶数个数是偶数还是奇数。是奇数。q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb182024/6/17College of Computer Science&Technology,BUPT第二节第二节不确定的有限自动机不确定的有限自动机(NFA)修改修改DFA的模型，使之在某个状的模型，使之在某个状态，对应一个一个输入，入，可以有多个可以有多个转移，移，到达不到达不 同的状同的状态，则称称为不确定的有不确定的有限自限自动机。机。例：例：(1)(2)192024/6/17College of Computer Science&Technology,BUPT一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元是一个五元组组，M=(Q,T,q0,F)。其中其中是是QT-2Q的函数，其余与的函数，其余与DFA相同。相同。n如果接收一个字符串后如果接收一个字符串后NFA进进入一个状入一个状态态集，集，而此集合中包含而此集合中包含一个以上一个以上F中的状中的状态态，则则称称NFA接收接收该该字符串。字符串。202024/6/17College of Computer Science&Technology,BUPT(1)(2)pq r0 q q q,r 1pq r0 p r r 1 p,q 转移图和转移表表示的转移图和转移表表示的NFA212024/6/17College of Computer Science&Technology,BUPT格局示例格局示例n如如图所示，用格局序列描述自所示，用格局序列描述自动机的工作机的工作过程，程，当当输入字符串是入字符串是0111011时，则有有222024/6/17College of Computer Science&Technology,BUPT二二、NFA的状态转移函数的状态转移函数与与 DFA 唯一不同之处唯一不同之处 :Q 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,r k,则 (q,a)=(r i,a)其中其中 T*,a T，r i Q232024/6/17College 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扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串242024/6/17College of Computer Science&Technology,BUPTNFA 接受的语言接受的语言 设一个设一个 NFA A=(Q,T,q0,F)定义定义 A 的语言的语言:L(A)=w (q0,w)F 252024/6/17College of Computer Science&Technology,BUPT第三节第三节 NFA与与DFA的等价性的等价性nDFA是是NFA的特例，所以的特例，所以NFA必然能接收必然能接收DFA能接收能接收的的语语言。言。因此因此证证明等价性只要能明等价性只要能够证够证明一个明一个NFA所能所能接收的接收的语语言必能被另一个言必能被另一个DFA所接收所接收。1.定理：定理：设设一个一个NFA接受接受语语言言L，那么必然存在一个，那么必然存在一个DFA接受接受L。2.证证明明:n策策略略：对对于于任任意意一一个个NFA，构构造造一一个个接接收收它它所所能能接接收收语语言言的的DFA，这这个个DFA的的状状态态对对应应了了NFA的的状状态态集合。集合。262024/6/17College of Computer Science&Technology,BUPT从从 NFA 构造等价的构造等价的 DFA (子集构造法子集构造法)设设 L 是是某某个个 NFA MN=(QN,T,N,q0,FN)的的语语言言,则存在一个则存在一个 DFA MD,满足满足 L(MD)=L(MN)=L.证明证明:定义定义 M D=(QD,T,D,q0,FD),其中其中 QD=S S QN =2 Q 对对 S QD 和和 a T,D(S,a)=N(q,a)，FD=S S QN S FN 需要证明需要证明:对任何对任何w T*,D(q0 ,w)=N(q0,w).归纳于归纳于|w|可可证上述命题证上述命题.q S272024/6/17College 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 子集构造法举例子集构造法举例282024/6/17College 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 子集构造法举例子集构造法举例292024/6/17College of Computer Science&Technology,BUPT证明证明:从从 NFA 构造等价的构造等价的 DFA 设设 MN=(QN,T,N,q0,FN)是一个是一个 NFA,通过子集构造法通过子集构造法 得到相应的得到相应的DFA MD=(QD,T,D,q0,FD),则则 对对任任何何w T*,D(q0 ,w)=N(q0,w).证明证明:归纳于归纳于|w|1 设设|w|=0,即即 w=.由定义知由定义知 D(q0 ,)=N(q0,)=q0 .2 设设|w|=n+1,并并 w=xa,a T.注意到注意到|x|=n.假设假设 D(q0 ,x)=N(q0,x)=p1,p2,pk .则则 D(q0 ,w)=D(D(q0 ,x),a)=D(p1,p2,pk,a)=N(pi,a).=N(q0,w)i=1k302024/6/17College of Computer Science&Technology,BUPT 实践中实践中,通过子集构造法得到的通过子集构造法得到的 DFA 的状态数目的状态数目与与原原NFA 的状态数目的状态数目大体大体相当相当.在较坏的情况下在较坏的情况下,上述上述 DFA 的状态数目接近于所有的状态数目接近于所有子集的数目子集的数目.举例举例 由如下由如下 NFA 构造的构造的 DFA 的状态数目至少为的状态数目至少为2n子集构造法得到的状态数子集构造法得到的状态数q0q1q2qn312024/6/17College of Computer Science&Technology,BUPT作业：作业：P48 习题习题8 ，P120 习题习题14人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。