形式语言与自动机ch31-33

1、12022-7-2College of Computer Science & Technology, BUPT第三章第三章 有限自动机与右线性文法有限自动机与右线性文法本章主要内容本章主要内容n确定有限自动机确定有限自动机n非确定有限自动机非确定有限自动机n确定与非确定有限自动机的等价性确定与非确定有限自动机的等价性n右线性文法和有限自动机的等价性右线性文法和有限自动机的等价性n右线性文法的性质右线性文法的性质(泵浦定理泵浦定理)n使用归纳法进行证明的方法使用归纳法进行证明的方法22022-7-2College of Computer Science & Technology,

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

3、态。态数有限），因为只有有限个状态。32022-7-2College of Computer Science & Technology, BUPTn实例实例 一个人带着一头狼，一头羊，以及一棵一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船青菜，处于河的左岸。有一条小船, ,每次只能每次只能携带人和其余的三者之一。人和他的伴随品携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似在左岸还是在右岸，

4、狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢呢? ?42022-7-2College of Computer Science & Technology, BUPTMGWC（处于左岸的子集（处于左岸的子集处于右岸的子集处于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)52022-7-2College of Computer Science & Technology, BUPT二、有限自动机的概念二、有限自动机的

5、概念有限自动机的概念有限自动机的概念n具有具有离散离散 输入输入 输出输出系统的系统的一种一种数学模型数学模型(可以没有输出，比较特殊的也可以没有输可以没有输出，比较特殊的也可以没有输入入).n有限有限的状态的状态n状态状态+输入输入状态转移状态转移n每次转换的后继状态都唯一每次转换的后继状态都唯一 DFAn每次转换的后继状态不唯一每次转换的后继状态不唯一 NFA62022-7-2College of Computer Science & Technology, BUPTFA的模型的模型 FA可以理解成一个控制器，它读一条输可以理解成一个控制器，它读一条输入带上的字符。入带上的字符。1

6、01101有限有限控制器控制器(1) 控制器包括有限状态；控制器包括有限状态；(2) 从左到右依次读取字符；从左到右依次读取字符；(3) 状态状态+激励激励 状态迁移状态迁移 (根据当前所处状态和输入字符根据当前所处状态和输入字符进行状态转移进行状态转移)72022-7-2College of Computer Science & Technology, BUPT 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合有限自动机的五要素有限自动机的五要素q0q1q2q3Start0110110082022-7-2Coll

7、ege of Computer Science & Technology, BUPT三、三、DFA的形式定义的形式定义定义: DFA是一个五元组 M=(Q,T,q0,F)nQ: 有限的状态集合有限的状态集合nT: 有限的输入字母表有限的输入字母表n: 转换函数转换函数(状态转移集合状态转移集合): QT Qnq0: 初始状态，初始状态， q0 QnF: 终止状态集终止状态集, F Q92022-7-2College of Computer Science & Technology, BUPT转转 移移 图图 表表 示示 的的 DFA Q = q0 , q1 , q2 , q3

8、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 q0q1q2q3Start01101100102022-7-2College of Computer Science & Technology, BUPT转转 移移 表表 表表 示示 的的 DFA q0q1q2 q301q2q1q3q0q0q3q1q2 Q = q0 , q1 , q2 , q3 T = 0, 1 (q

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

10、一个字符串是一个字符串, a是一个字符是一个字符定义定义: (q,a)=(q,),a)对于对于DFA:(q,a)=(q, ),a)=(q,a)，即对即对于单个字符时于单个字符时和和是相等的。为了方便，以后在是相等的。为了方便，以后在不引起混淆时用不引起混淆时用代替代替 122022-7-2College of Computer Science & Technology, BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 q0q1q2 q301q2q1q3q0q0q3q1q2 举例举例 (q0 , ) = q0 (q0 , 0) = (q0 , 0) = q2 (q0 ,

11、 00) = (q2 , 0) = q0 (q0 , 001) = (q0 , 1) = q1 (q0 , 0010) = (q1 , 0) = q3q0q1q2q3Start01101100132022-7-2College of Computer Science & Technology, BUPTDFA接受的语言接受的语言n被被DFA接收的字符串接收的字符串: 输入结束后使输入结束后使DFA的状态到达终的状态到达终止状态。否则该字符串不能被止状态。否则该字符串不能被D FA接收接收.nDFA接收的语言接收的语言: 被被DFA接收的字符串的集合接收的字符串的集合.L(M) = w

12、( q0 , w) F n例：例：T = 0，112Start0110接收含有奇数个接收含有奇数个0的任意串的任意串142022-7-2College of Computer Science & Technology, BUPT五、格局五、格局n为描述有限自动机的工作过程，对于它在某为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当一时刻的工作状态，可用两个信息表明：当前状态前状态q，待输入字符串待输入字符串w。两者构成一个瞬两者构成一个瞬时描述，用（时描述，用（q,w）表示，称为格局。表示，称为格局。n初始格局：（初始格局：（q0,w)n终止格局：终止格局：

13、 (q,), q F152022-7-2College 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)。格局示例格局示例q0q1q2q3Start01101100162022-7-

14、2College of Computer Science & Technology, BUPTn如果对某个如果对某个q F,有有(q0,w) (q, ),则称输入字符串则称输入字符串w是可被确定的有限自动机接受的。是可被确定的有限自动机接受的。172022-7-2College of Computer Science & Technology, BUPT设计有限自动机设计有限自动机n自动机的设计是一个创造过程，没有简单的算法或过程。自动机的设计是一个创造过程，没有简单的算法或过程。n技巧：假设自己是机器，思考如何去实现机器的任务技巧：假设自己是机器，思考如何去实现机器的任务。n

15、为判断到目前为止所看到的字符串是否满足某个语言，须估为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。算出读一个字符串时需要记住哪些关键的东西。 例：例：构造自动机，识别所有由奇数个构造自动机，识别所有由奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。关键：不需要记住所看到的整个字符关键：不需要记住所看到的整个字符串串，只需记住至此所看到，只需记住至此所看到的的a、b个数是偶数还是奇数。个数是偶数还是奇数。 q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb182022-7-2College of Computer Scienc

16、e & Technology, BUPT第二节第二节不确定的有限自动机不确定的有限自动机(NFA)修改修改DFA的模型，使之在某个状态，的模型，使之在某个状态， 对应一个输入，可对应一个输入，可以有多个转移，以有多个转移， 到达不到达不 同的状态，同的状态， 则称为不确定的有限自则称为不确定的有限自动机。动机。 例：例：Startpr0, 10q1(1)Startp0, 11qr0, 1(2)192022-7-2College of Computer Science & Technology, BUPT一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五

17、元组，是一个五元组，M=(Q,T,q0,F)。其中其中是是QT-2Q的函数，其余与的函数，其余与DFA相同。相同。n如果接收一个字符串后如果接收一个字符串后NFA进入一个状态集，进入一个状态集，而此集合中包含而此集合中包含一个以上一个以上F中的状态，中的状态， 则则称称NFA接收该字符串。接收该字符串。202022-7-2College of Computer Science & Technology, BUPTStartpr0, 10q1(1)Startp0, 11qr0, 1(2)pq r0 q q q, r 1pq r0 p r r 1 p, q 转移图和转移表表示的转移图和转移

18、表表示的NFA212022-7-2College of Computer Science & Technology, BUPT格局示例格局示例n如图所示，用格局序列描述自动机的工作过程，如图所示，用格局序列描述自动机的工作过程，当输入字符串是当输入字符串是0111011时，则有时，则有Startp0 , 11qr0 , 1( ,011011 )| ( ,11011 )| ( ,1011 )| ( ,011 )| ( ,11 )| ( ,1 )| ( , ) ( ,1011 )| ( ,011 ) ( ,1 )| ( , ) pppppqrqrpp ( , )q222022-7-2Col

19、lege 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 , 则则

20、 ( q , a) = ( r i , a ) 其中其中 T* , a T， r i Q232022-7-2College 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, 10q1242022-7-2College of Computer Sc

21、ience & Technology, BUPTNFA 接受的语言接受的语言 设一个设一个 NFA A = (Q, T, , q0 , F ) 定义定义 A 的语言的语言: L(A) = w ( q0 , w) F 252022-7-2College of Computer Science & Technology, BUPT第三节第三节 NFA与与DFA的等价性的等价性nDFA是是NFA的特例，所以的特例，所以NFA必然能接收必然能接收DFA能接收能接收的语言。的语言。 因此因此证明等价性只要能够证明一个证明等价性只要能够证明一个NFA所所能接收的语言必能被另一个能接收的语言

22、必能被另一个DFA所接收所接收。1.定理：设一个定理：设一个NFA接受语言接受语言L，那么必然存在一个，那么必然存在一个DFA接受接受L。2. 证明证明:n策略：对于任意一个策略：对于任意一个NFA，构造一个接收它所能接，构造一个接收它所能接收语言的收语言的DFA，这个这个DFA的状态对应的状态对应了了NFA的状态的状态集合。集合。262022-7-2College of Computer Science & Technology, BUPT从从 NFA 构造等价的构造等价的 DFA (子集构造法子集构造法) 设设 L 是某个是某个 NFA MN = (QN, T, N , q0 ,

23、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 S272022-7-2College of Computer Science &

24、 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 Startp0, 10q1q,r1010 子集构造法举例子集构造法举例282022-7-2College 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, 11qr0, 1292022-7-2College of Computer Science & Technology, BUPT证明证明:从从 NFA 构造等价的构造