形式语言与自动机.ppt

1、1,计算理论,第1章 正则语言,韩启龙,2,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,3,3,什么是 “Computer”?计算模型（Computational Model）理想计算机准确地刻画了某些特征，同时忽略一些特征。因此，针对关注的特征，采用不同的计算模型。最简单的模型自动机Automation(自动机)DFANFA,1.1 有穷自动机,现实计算机-复杂难直接建立易于处理的数学理论引入“计算模型”,4,什么是 “有穷自动机”?描述能力和资源及其有限的计算机模型。从数学角度考虑“有穷自动机”只做抽象的描述，不涉及任何具体的应用接收输

2、入：字符串输出：是非型如此有限，能做什么？很多事情（机电设备核心部位）自动门控制器实例,1.1 有穷自动机,5,1.1 有穷自动机,实际示例自动门控制,控制器处于CLOSED状态，假设如下输入信号：FRONT, REAR, NEITHER, FRONT, BOTH, NEITHER, REAR, NEITHER, 考察状态的变化。可以给出状态和信号之间的计算。,6,状态图,7,状态图,q1 q2 q2 q3 q2 = “accept”,on input “1101”, the machine goes:,010: reject11: accept010100100100100: accept0

3、10000010010: reject: reject,1、接受以1结尾的任何0、1串2、最后一个1的后面有偶数个0的任何0、1串3、拒绝其他的0、1串,8,1.1 有穷自动机,用C语言描述 FA,Char *input ,*pCurr /全局量Bool FA_func( ) start:q1: if (*pCurr=0) goto q1; else if (*pCurr=1) goto q2;q2: if (*pCurr=0) goto q3; else if (*pCurr=1) goto q2q3: if (*pCurr=0 | *pCurr=1) goto q2;自动机对应于只有if,

4、goto，无数组，无内部变量的程序；程序不如图形直观，程序容易使用超标的资源（内存，栈，数组等）,9,有穷自动机的形式定义,定义1.1,有穷自动机是一个 5 元组 ( Q, , , q0, F )，其中(1) Q 是一个有穷集合，称为状态集。(2) 是一个有穷集合，称为字母表。(3) : QQ是转移函数。(4) q0Q 是起始状态。(5) FQ 是接受状态集。,介绍写定义的方法：元组式，递归式Let 式 : Let, It is said to be . If .,10,有穷自动机举例,例 给定有穷自动机 M1 的状态图。请给出形式化的描述，并确定其能识别的语言。,M1 = ( q1, q2

5、, q3 , 0,1 , , q1, q2 ),L(M1) = w | w 至少一个 1并且在最后的1后面有偶数个0 ,若 A 是机器 M 接受的全部字符串集，则称 A 是机器 M 的语言，记作 L(M)=A，又称 M 识别 A 或 M 接受 A。,11,有穷自动机举例,例1.2 给定有穷自动机 M2 的状态图。请给出形式化的描述，并确定其能识别的语言。,M2 = ( q1, q2 , 0,1 , , q1, q2 ),L(M2) = w | w 以 1 结束,12,有穷自动机举例,例1.3 给定有穷自动机 M3 的状态图。请给出形式化的描述，并确定其能识别的语言。,L(M3) = w | w

6、 是空串或以 0 结束,13,有穷自动机举例,例1.4 给定有穷自动机 M4 的状态图。请给出形式化的描述，并确定其能识别的语言。,q1,a,b,a,q2,r1,r2,s,b,b,a,b,a,b,a,14,有穷自动机举例,例1.5 给定有穷自动机 M5 的状态图。请给出形式化的描述，并确定其能识别的语言。,q0,2,0,q2,q1,0,0,1,2,1,1,2,M5 以模3的方式记录它在输入串中读到的数字之和。,15,有穷自动机举例,例1.6 例1.5推广。对于每一个 i =1，设 Ai 是所有这种字符串的语言，其中数字之和是 i 的倍数。,M=( Q, , , q0, F )Q=q0, q1,

7、 , qn-1 (qj , 0) = qj (qj , 1) = qk , k = j+1 mod i (qj , 2) = qk , k = j+2 mod i (qj , ) = q0 , k = j+1 mod i,16,计算的形式化定义,设 M = (Q, , , q0, F) 是一台有穷自动机， w = w1w2wn 是一个字符串，并且 wi 是字母表 的成员。如果存在 Q 中的状态序列 r0, r1, , rn，满足下列条件：1) r0 = q02) (ri , wi+1) = ri+1 , i = 0, 1, , n1 rn F则 M 接受 w。,17,计算的形式化定义举例,例1

8、.8 给定有穷自动机 M5 的状态图。令w是字符串1022012给出M5对w计算时进入的状态序列。,18,设计有穷自动机,例：设计有穷自动机 E1，假设字母表是0,1，识别的语言由所有含有奇数个 1 的字符串组成。,qodd,qeven,19,设计有穷自动机,例1.9 设计有穷自动机 E2，使其能识别含有 001 作为子串组成的正则语言。,q001,q,q0,q00,20,正则运算,定义1.10,设 A 和 B 是两个语言，定义正则运算并、连接和星号如下： 并： AB = x | xA 或 xB 连接：AB = xy | xA 且 yB 星号：A* = x1x2xk | k 0 且每一个xi

9、A ,21,正则运算,例1.11 设字母表 是标准的 26 个字母 a, b, , z。又设 A=good, bad, B=boy, girl, 求AB , AB 和A*。,22,正则运算,定理1.12,正则语言类在并运算下封闭。,如果A1和A2是正则语言，则A1A2也是正则语言。设 M1 识别 A1， M2 识别 A2。利用M1，M2构造M。为了识别A1A2和，机器M必须恰好在M1或M2接受的时候接受他的输入串。M模拟M1和M2并且当这两个模拟中有一个接受时，M接受。,23,正则运算,定理1.12,正则语言类在并运算下封闭。,如果A1和A2是正则语言，则A1A2也是正则语言。设 M1 识别

10、A1， M2 识别 A2。并设M1=(Q1, , 1,q1, F1) 和 M2=(Q2, , 2, q2, F2)构造识别A1A2 的 M=(Q, , , q0, F)Q = Q1Q2 = (r1, r2) | r1Q1 且 r2Q2(r1, r2), a ) = (1(r1,a), 2(r2,a) )q0 = (q1, q2)F = (r1, r2) | r1F1 或 r2F2,REVIEW(2011-03-07),确定有限自动机的形式化定义( Q, , , q0, F )机器识别语言计算的形式化定义,24,若 A 是机器 M 接受的全部字符串集，则称 A 是机器 M 的语言，记作 L(M)

11、=A，又称 M 识别 A 或 M 接受 A。,设 M = (Q, , , q0, F) 是一台有穷自动机， w = w1w2wn 是一个字符串，并且 wi 是字母表 的成员。如果存在 Q 中的状态序列 r0, r1, , rn，满足下列条件：1) r0 = q02) (ri , wi+1) = ri+1 , i = 0, 1, , n1 rn F则 M 接受 w。,REVIEW(2011-03-07),正则语言如果一个语言被一台有穷自动机识别，则称它是正则语言。正则运算：并、连接和星号,25,定理1.12,正则语言类在并运算下封闭。,如果A1和A2是正则语言，则A1A2也是正则语言。设 M1

12、识别 A1， M2 识别 A2。利用M1，M2构造M。为了识别A1A2和，机器M必须恰好在M1或M2接受的时候接受他的输入串。M模拟M1和M2并且当这两个模拟中有一个接受时，M接受。,26,正则运算,定理1.13,正则语言类在连接运算下封闭。,证明思路 按照定理1.12证明思路试一下。输入：M1接受第一段且 M2 接受第二段时，M才接受；,？,M不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始),27,举例,证明定理遇到困难，暂时放下引入不确定性,Consider the concatenation: 考虑下列连接1,01,11,001,011, 0,000,00000,(Tha

13、t is: the bit strings that end with a “1”,followed by an odd number of 0s.),Problem is: given a string w, how does the automaton know where the L1 partstops and the L2 substring starts? 如何知道L1 何处停止？ L2 何处开始？切分问题。,28,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,29,非确定性,确定性：机器处于给定状态并读入下一个输入符，可以知道机

14、器的下一个状态是什么确定的；不确定性:任何一个点，下一个状态可能存在若干个选择；不确定性体现在:转换规则一入多出, 是空字无入转态,30,非确定性,不确定性表现：q11 Y ? Y有两个可能状态: q1,q2 导致 q2 自动漂移到 q3,是否接受 “0110” 和 ”1”,0110q1 q1 q2 q3 q4 q41q1, q2 ,q3,NFA如何计算？见P28页,31,非确定性,例1.14 设 A 是 0, 1 上倒数第三个符号为 1 的所有字符串组成的语言，构造非确定性自动机。,q4,q1,q2,q3,NFA如何进行计算？P28-29,32,非确定性,例1.15 考虑图示的 NFA N

15、，它的输入字母表 0由一个符号组成。只含一个符号的字母表称为一元字母表。考虑它接受的语言。,0,0,0,0,0,33,非确定性,例1.16 考虑图示的 NFA N 。运行这台机器，判断其是否识别、a、baba、baa、b、bb、babba。,34,非确定型有穷自动机的形式定义,定义1.17,非确定型有穷自动机 (NFA) 是一个 5 元组 ( Q, , , q0, F )，其中(1) Q 是有穷的状态集。(2) 是有穷的字母表。(3) : QP(Q)是转移函数。(4) q0Q 是起始状态。(5) FQ 是接受状态集。,35,NFA 的形式化描述举例,例1.18 给出图示的 NFA 的形式化描述

16、。,36,NFA 计算的形式化定义,设 N = (Q, , , q0, F) 是一台 NFA， w = w1w2wn 是一个字符串，并且 wi 是字母表 的成员。如果存在 Q 中的状态序列 r0, r1, , rn，满足下列条件：1) r0 = q02) ri+1 (ri , wi+1) = , i = 0, 1, , n1 rn F则 N 接受 w。,37,NFA与DFA的等价性,q1 q2, q3, q5,q1 ,q4,q2 ,q3 ,q5,q5,1,2,38,NFA与DFA的等价性,设 N = (Q, , , q0, F) 是识别语言 A 的NFA。假设 N 没有 箭头。构造识别 A 的

17、 DFA M = (Q, , , q0, F )(1) Q=P(Q)（P（Q）是Q的所有子集组成的集合）(2) 对于 RQ 和 a，令 (R,a)= qQ | 存在 rR, 使得 q(r,a) (3) q0= q0 (4) F = RQ | R 包含 N 的一个接受状态 ,39,NFA与DFA的等价性,考虑 N 有 箭头。对于 M 的任意一个状态 R，定义 E(R) 为从 R 出发只沿着 箭头可以达到的状态集合，包括 R 本身的所有成员在内。E(R) = q | 从 R 出发沿着 0 或多个 箭头可以到达 q 修改 M 的转移函数 (R,a)= qQ | 存在 rR, 使得 qE(r,a) q

18、0=E(q0),40,NFA与DFA的等价性,推论1.20,一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它。,41,NFA 转换成等价的 DFA 举例,例1.21 将图示的 NFA N 转换成等价的 DFA。,Q = , 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3 E(1) = 1, 3 F = 1, 1,2, 1,3, 1,2,3 考察 2,1,3,1,2,2,3, 1,2,3, , 1,3,1,1,2,2,a,1, 3,3,1,2,3,2,3,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,42,在正则运算下的封闭性,定理1.22,正则语言类在并运算下

19、封闭。,N,N2,N1,设 N1 = (Q1, , 1, q1, F1)N2 = (Q2, , 2, q2, F2)构造N = (Q, , , q0, F),43,NFA与DFA的等价性,定理1.23,正则语言类在连接运算下封闭。,N,N2,N1,44,NFA与DFA的等价性,定理1.24,正则语言类在星运算下封闭。,N,N1,45,DFA和NFA能力等价,DFA机器易算，NFA 人易制造， 通常，人造NFA，让机器把它变成DFA。当用并行技术去实现时实际上是用NFA。当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用DFA。直观解释：对应于NFA这样的简单并行程序中可以串行

20、化。,46,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,47,正则表达式的引入,算术运算：(5+3) 4考察：(01)0*正则表达式在计算机科学应用中有着重要的作用。在涉及文本的应用中，用户可能要搜索满足某种模式的字符串。正则表达式提供了描述这种模式的有力方法。(01) 0* * 描述该字母表上的所有字符串组成的语言。 *1 描述所有以1结尾的字符串组成的语言。,算术表达式的值32；正则表达式的值是一个语言,48,正则表达式举例,例1.25 正则表达式的例子 (01)*。,若 = 0, 1 ，则可以用 作为 (01) 的缩写。 * 表示该字

21、母表上的所有字符串组成的语言。 *1 是包含所有以 1 结尾的字符串的语言。(0 * )( *1) 由所有以 0 开始或者以 1 结尾的字符串组成。,49,正则表达式的形式化定义,定义1.26,称 R 是一个正则表达式，如果 R 是(1) a，这里 a 是字母表 中的一个元素；(2) ；(3) (4) R1R2，这里 R1 和 R2 是正则表达式；(5) R1R2 ，这里 R1 和 R2 是正则表达式；(6) R1* ，这里 R1 是正则表达式；,50,正则表达式举例,例1.27 在下面的例子中假定字母表 是 0, 1 。,(1) 0*10* (2) *1 *(3) *001 *(4) (01

22、+)*(5) ()*：长度为偶数的字符串(6) ( )*：长度是3的整数倍(7) 0110(8) 0 *01 *10 1(9) (0)1*=01* 1*(10) (0)(1)=0,1,01, (11) 1*= ：把空集连接到任何集合上得到空集(12) *=,51,关于正则表达式的说明,(1) R = R(2) R = R(3) R = R 可能不成立例如，如果R=0，那么L(R)=0，而L(R )=0, (4) R = R 可能不成立例如，如果R=0，那么L(R)=0，而L(R )= ,52,正则表达式与有穷自动机的等价性,REVIEW(2011-03-09),不确定性有限自动机不确定性体现在

23、:转换规则一入多出, 是空字无入转态非确定型有穷自动机的形式定义( Q, , , q0, F ) : QP(Q)是转移函数。NFA 计算的形式化定义NFA与DFA的等价性定理：每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它,53,REVIEW(2011-03-09),NFA与DFA的等价性定理：每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它将NFA转换成等价的 DFA？证明正则语言类的并、连接、星运算的封闭性。正则表达式可以用正则运算符构造描述语言的表达式称为正则

24、表达式正则表达式的形式化定义R：（a， ， ， R1R2 ， R1R2 ， R1*）定理：一个语言是正则的，当且仅当可以用正则表达式描述它。,54,55,正则表达式与有穷自动机的等价性,把 R 转换成一台 NFA N。考虑 R 的 6 种情况。(1) R = a(2) R = (3) R = (4) R= R1R2(5) R= R1 R2(6) R=R1*,(1) N = (q1, q2, , , q1, q2)当 r q1 或 b a 时，(q1, a)=q2， (r, b)= ,思路：如果正则表达式R描述某种语言A。如果能将R转换成一台识别A的NFA即可。,使用正则语言类在正则运算下封闭的

25、证明中给出构造,56,正则表达式转换成 NFA,例1.30 把正则表达式 (aba)* 转换成一台 NFA。,(1) a,(5) (aba)*,(2) b,(3) ab,(4) aba,57,正则表达式与有穷自动机的等价性,引入广义非确定型有穷自动机GNFA：(1) 转移箭头可以用任何正则表达式作标号。(2) 起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。 (3) 有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。 (4) 除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。,

26、思路：A正则被一台DFA接受；DFA正则表达式即可。,58,广义非确定型有穷自动机(GNFA),定义1.33,GNFA M = (Q, , , qstart, qaccept)Q 是有穷的状态集。(2) 是输入字母表。(3) :(Q-qaccept)(Q-qstart) R 是转移函数。 (4) qstart 是起始状态。 (5) qaccept 是接受状态。其中 R 是正则表达式。自动机的 边 推广为 RE (子程序,子自动机）,59,广义非确定型有穷自动机(GNFA),子自动机,60,GNFA与NFA,二者等价通过增加新的起始状态和新的接受状态，可以将DFA转换成GNFA。,证明思路分两步

27、：1 RL 有 DFA M识别（定义），把DFA 转化称广义的GDFA把广义的GDFA转化称正则表达式 RE（略）详见教材p43-45,61,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,62,非正则语言,要了解有穷自动机的能力，必须同时了解它们的局限性。对于如下的语言，是否能找到识别该语言的 DFA？B= 0n1n | n0 如果找到DFA，必须记住输入中读取多少个0。由于0个数没有限制，机器必须记住无穷多个可能。有穷状态不可能。需要证明.（看起来需要无穷存储的语言并不一定需要无穷存储）C= w | w 中 0 和 1 的个数相等 不是正则

28、的；D= w | w 中 01 和 10 作为子串出现的次数相同 正则。,63,非正则语言,证明非正则性的技术源于一个关于正则语言的定理泵引理，该定理指出所有的正则语言都有一种特殊的性质，如果一个语言没有这个性质，则其不是正则的。,性质：语言中的所有字符串只要它的长度不小于某个特定值泵长度，就可以被抽取。每一个这样的字符串都包括一段子串，把这段子串重复任意次，得到的字符串仍在这个语言中。,64,泵引理(pumping lemma),定理1.37,若 A 是一个正则语言，则存在一个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s = x

29、yz，满足下述条件： 对于每一个 i 0, xyizA (2) | y | 0(3) | xy | p,我们总能够在离 s 的开始处不太远的地方找到一个非空的串 y，然后可以把它看作一个“泵”，重复 y 任意多次，或者去掉它，而所得到的结果串仍然属于A。,正则语言是靠打圈，来描述（有某种规律的）无限集合,65,泵引理的证明,证明思路：设 M = (Q, , , q1, F) 是一台识别 A 的 DFA，另泵长度 p 是 M 的状态数。要证明A中任意长度不小于p的字符串s可以划分成3段xyz，且满足定理中的3个条件。若A中没有长度不小于p的字符串自然成立；若sA的长度不小于p，考虑M对输入 s

30、的计算中经过的状态序列。从起始状态q1开始，然后到q3，到q20，再到q9等等，一直到结束进入状态q13，由于s属于A，M接受s，因此q13是接受状态。若s的长度为n，则状态序列q1q3q20q9,q13的长度为n+1。由于n不小于p，故序列中一定出现重复状态，假设q9重复出现。现在将s划分成3段x、y、z。,66,泵引理的证明,x是q9前面的部分，y是两个q9之间的部分，z是s的剩余部分。因此，x把M从状态q1带到q9，y把M从状态q9带回q9，z把M从q9带到接受状态q13。1、假设对输入xyyz运行M。已知x将M从q1带到q9，第一个y将q9带回q9，第二个同样带回q9，接着将z带到q1

31、3。M接受xyyz，类似对任意i，接受xyiz。2、y是s在状态q9出现的两个不同地点之间的部分，|y|0。3、为了使条件3成立，确保q9是序列中第一个重复的状态。根据鸽巢定理，有|xy|0，又已知 l p+1，故 | xy | p。于是，满足泵引理的3个条件。,69,泵引理的应用,例1.38 设 B= 0n1n | n0。用泵引理证明 B 不是正则的。,假设 B 是正则的，令 p 是由泵引理给出的泵长度。选择 s = 0p1p 按照泵引理所述，可令 s = xyz使得对于任意的 i 1，串 xyiz 在 B 中。下面考虑 3 种情况：(1) 字符串 y 只包含 0。在这种情况下，字符串 xy

32、yz 中的 0 比1 多，从而不是 B 的成员，矛盾。(2) 字符串 y 只包含 1。在这种情况下，字符串 xyyz 中的 1 比0 多，从而不是 B 的成员，矛盾。(3) 字符串 y 既包含 0 也包含 1。在这种情况下，字符串 xyyz 中的 0 和1 的个数可能相等，但是在0的前面会出现1。因此，xyyz 不是 B 的成员，矛盾。综上，B 不是正则的。,70,泵引理的应用,例1.38 设 B= 0n1n | n0。用泵引理证明 B 不是正则的。,假设 B 是正则的，令 p 是由泵引理给出的泵长度。选择 s = 0p1p ，按照泵引理所述，可令 s = xyz 根据泵引理，有 | xy |

33、 p，因此 y=0k，k1此时有 x = 0p-k-j , z=0j1p从而有 xyiz = 0p-k-j (0k)i 0j1p = 0p+(i-1)k1p 当 i =2 时，我们有：xy2z=0p+(2-1)k1p = 0p+k1p注意到 k1，所以，p+kp。这就是说，0p+k1pL这与泵引理矛盾。所以，B 不是 正则的。,71,泵引理的应用,例1.39 设 C= w | w 中 0 和 1 的个数相同。用泵引理证明 B 不是正则的。,72,泵引理的应用,例1.40 设 F = w w | w 0, 1* 。用泵引理证明 B 不是正则的。,73,泵引理的应用,例1.41 设 D = | n0 。用泵引理证明 B 不是正则的。,74,泵引理的应用,例1.42 设 E = 0i1j | i j 。用泵引理证明 B 不是正则的。,75,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,76,本章小结,有穷自动机 DFA M = (Q, , , q0, F)非确定型有穷自动机 NFA正则表达式正则语言泵引理,77,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,1.6, 1.7, 1.19, 1.29, 1.37,