计算理论导引1正则语言.ppt

1,计算理论,第1章 正则语言,2,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,3,1.1 有穷自动机,实际示例自动门控制,控制器处于CLOSED状态，假设如下输入信号：FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHER,考察状态的变化。可以给出状态和信号之间的计算。,4,状态图,5,状态图,q1 q2 q2 q3 q2=“accept”,on input“1101”,the machine goes:,010:reject11:accept:reject,6,有穷自动机的形式定义,定义1.1,有穷自动机是一个 5 元组(Q,q0,F)，其中(1)Q 是一个有穷集合，称为状态集。(2)是一个有穷集合，称为字母表。(3):QQ是转移函数。(4)q0Q 是起始状态。(5)FQ 是接受状态集。,7,有穷自动机举例,例 给定有穷自动机 M1 的状态图。请给出形式化的描述，并确定其能识别的语言。,M1=(q1,q2,q3,0,1,q1,q2),L(M1)=w|w 至少一个 1并且在最后的1后面有偶数个0,若 A 是机器 M 接受的全部字符串集，则称 A 是机器 M 的语言，记作 L(M)=A，又称 M 识别 A 或 M 接受 A。,8,有穷自动机举例,例1.2 给定有穷自动机 M2 的状态图。请给出形式化的描述，并确定其能识别的语言。,M2=(q1,q2,0,1,q1,q2),L(M2)=w|w 以 1 结束,9,有穷自动机举例,例1.3 给定有穷自动机 M3 的状态图。请给出形式化的描述，并确定其能识别的语言。,L(M3)=w|w 是空串或以 0 结束,10,有穷自动机举例,例1.4 给定有穷自动机 M4 的状态图。请给出形式化的描述，并确定其能识别的语言。,q1,a,b,a,q2,r1,r2,s,b,b,a,b,a,b,a,11,有穷自动机举例,例1.5 给定有穷自动机 M5 的状态图。请给出形式化的描述，并确定其能识别的语言。,q0,2,0,q2,q1,0,0,1,2,1,1,2,M5 以模3的方式记录它在输入串中读到的数字之和。,12,有穷自动机举例,例1.6 例1.5推广。对于每一个 i=1，设 Ai 是所有这种字符串的语言，其中数字之和是 i 的倍数。,M=(Q,q0,F)Q=q0,q1,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,13,计算的形式化定义,设 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。,14,计算的形式化定义举例,例1.8 给定有穷自动机 M5 的状态图。令w是字符串1022012给出M5对w计算时进入的状态序列。,15,设计有穷自动机,例：设计有穷自动机 E1，假设字母表是0,1，识别的语言由所有含有奇数个 1 的字符串组成。,qodd,qeven,16,设计有穷自动机,例1.9 设计有穷自动机 E2，使其能识别含有 001 作为子串组成的正则语言。,q001,q,q0,q00,17,正则运算,定义1.10,设 A 和 B 是两个语言，定义正则运算并、连接和星号如下：并：AB=x|xA 或 xB 连接：AB=xy|xA 且 yB 星号：A*=x1x2xk|k 0 且每一个xi A,18,正则运算,例1.11 设字母表 是标准的 26 个字母 a,b,z。又设 A=good,bad,B=boy,girl,求AB,AB 和A*。,19,正则运算,定理1.12,正则语言类在并运算下封闭。,如果A1和A2是正则语言，则A1A2也是正则语言。设 M1 识别 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,20,正则运算,定理1.13,正则语言类在连接运算下封闭。,证明思路 按照定理1.12证明思路试一下。输入：M1接受第一段且 M2 接受第二段时，M才接受；,？,M不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始),21,举例,证明定理遇到困难，暂时放下引入不确定性,Consider the concatenation:考虑下列连接1,01,11,001,011,0,000,00000,(That 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 何处开始？切分问题。,22,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,23,非确定性,非确定性体现在转换规则一入多出,是空字无入转态,24,非确定性,不确定性表现：q11 Y?Y有两个可能状态:q1,q2 导致 q2 自动漂移到 q3,是否接受“0110”和”1”,0110q1 q1 q2 q3 q4 q41q1,q2,q3,25,非确定性,例1.14 设 A 是 0,1 上倒数第三个符号为 1 的所有字符串组成的语言，构造非确定性自动机。,q4,q1,q2,q3,26,非确定性,例1.15 考虑图示的 NFA N，它的输入字母表 0由一个符号组成。只含一个符号的字母表称为一元字母表。考虑它接受的语言。,0,0,0,0,0,27,非确定性,例1.16 考虑图示的 NFA N。运行这台机器，判断其是否识别、a、baba、baa、b、bb、babba。,28,非确定型有穷自动机的形式定义,定义1.17,非确定型有穷自动机(NFA)是一个 5 元组(Q,q0,F)，其中(1)Q 是有穷的状态集。(2)是有穷的字母表。(3):QP(Q)是转移函数。(4)q0Q 是起始状态。(5)FQ 是接受状态集。,29,NFA 的形式化描述举例,例1.18 给出图示的 NFA 的形式化描述。,30,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。,31,NFA与DFA的等价性,q1 q2,q3,q5,q1,q4,q2,q3,q5,q5,1,2,32,NFA与DFA的等价性,设 N=(Q,q0,F)是识别语言 A 的NFA。假设 N 没有 箭头。构造识别 A 的 DFA M=(Q,q0,F)(1)Q=P(Q)(2)对于 RQ 和 a，令(R,a)=qQ|存在 rR,使得 q(r,a)(3)q0=q0(4)F=RQ|R 包含 N 的一个接受状态,33,NFA与DFA的等价性,考虑 N 有 箭头。对于 M 的任意一个状态 R，定义 E(R)为从 R 出发只沿着 箭头可以达到的状态集合，包括 R 本身的所有成员在内。E(R)=q|从 R 出发沿着 0 或多个 箭头可以到达 q 修改 M 的转移函数(R,a)=qQ|存在 rR,使得 qE(r,a)q0=E(q0),34,NFA与DFA的等价性,推论1.20,一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它。,35,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,36,在正则运算下的封闭性,定理1.22,正则语言类在并运算下封闭。,N,N2,N1,设 N1=(Q1,1,q1,F1)N2=(Q2,2,q2,F2)构造N=(Q,q0,F),37,NFA与DFA的等价性,定理1.23,正则语言类在连接运算下封闭。,N,N2,N1,38,NFA与DFA的等价性,定理1.24,正则语言类在星运算下封闭。,N,N1,39,DFA和NFA能力等价,DFA机器易算，NFA 人易制造，通常，人造NFA，让机器把它变成DFA。当用并行技术去实现时实际上是用NFA。当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用DFA。直观解释：对应于NFA这样的简单并行程序中可以串行化。,40,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,41,正则表达式的引入,算术运算：(5+3)4考察：(01)0*(01)0*描述该字母表上的所有字符串组成的语言。*1 描述所有以1结尾的字符串组成的语言。,42,正则表达式举例,例1.25 正则表达式的例子(01)*。,若=0,1，则可以用 作为(01)的缩写。*表示该字母表上的所有字符串组成的语言。*1 是包含所有以 1 结尾的字符串的语言。(0*)(*1)由所有以 0 开始或者以 1 结尾的字符串组成。,43,正则表达式的形式化定义,定义1.26,称 R 是一个正则表达式，如果 R 是(1)a，这里 a 是字母表 中的一个元素；(2)；(3)(4)R1R2，这里 R1 和 R2 是正则表达式；(5)R1R2，这里 R1 和 R2 是正则表达式；(6)R1*，这里 R1 是正则表达式；,44,正则表达式举例,例1.27 在下面的例子中假定字母表 是 0,1。,(1)0*10*(2)*1*(3)*001*(4)(01+)*(5)()*(6)()*(7)0110(8)0*01*10 1(9)(0)1*=01*1*(10)(0)(1)=0,1,10,(11)1*=(12)*=,45,关于正则表达式的说明,(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)=,46,正则表达式与有穷自动机的等价性,47,正则表达式与有穷自动机的等价性,把 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)=,48,正则表达式转换成 NFA,例1.30 把正则表达式(aba)*转换成一台 NFA。,(1)a,(5)(aba)*,(2)b,(3)ab,(4)aba,49,正则表达式与有穷自动机的等价性,引入广义非确定型有穷自动机GNFA：(1)转移箭头可以用任何正则表达式作标号。(2)起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。(3)有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。(4)除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。,50,广义非确定型有穷自动机(GNFA),子自动机,51,广义非确定型有穷自动机(GNFA),定义1.33,GNFA M=(Q,qstart,qaccept)Q 是有穷的状态集。(2)是输入字母表。(3):(Q-qaccept)(Q-qstart)R 是转移函数。(4)qstart 是起始状态。(5)qaccept 是接受状态。其中 R 是正则表达式。自动机的 边 推广为 RE(子程序,子自动机）,通过增加新的起始状态和新的接受状态，可以将DFA转换成GNFA。,52,将 GNFA 转换为等价的正则表达式,qi,qj,(R1)(R2)*(R3)(R4),53,正则表达式与有穷自动机的等价性,证明思路分两步：1 RL 有 DFA M识别（定义），把DFA 转化称广义的GDFA把广义的GDFA转化称正则表达式 RE详见教材p43-45,54,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,55,非正则语言,对于如下的语言，是否能找到识别该语言的 DFA？B=0n1n|n0 C=w|w 中 0 和 1 的个数相等 D=w|w 中 01 和 10 作为子串出现的次数相同,56,非正则语言,57,泵引理(pumping lemma),定理1.37,若 A 是一个正则语言，则存在一个数 p(泵长度)使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s=xyz，满足下述条件：对于每一个 i 0,xyizA(2)|y|0(3)|xy|p,我们总能够在离 s 的开始处不太远的地方找到一个非空的串 y，然后可以把它看作一个“泵”，重复 y 任意多次，或者去掉它，而所得到的结果串仍然属于A。,58,泵引理的证明,设 M=(Q,q1,F)是一台识别 A 的 DFA，并设 p 是 M 的状态数。设 s=s1s2sn 是 A 中长度为 n 的字符串，这里 np。又设 r1,r2,rn+1 是 M 在处理 s 的过程中进入的状态序列，因而 ri+1=(ri,si)，1in。该序列的长度为 n+1，不小于p+1。根据鸽巢原理，在该序列的前 p+1 个元素中，一定有两个相同的状态。设第 1 个是 rj，第 2 个是 rl。由于 rl 出现在序列的前 p+1 个位置中，而且序列是从 r1 开始的，故有 l p+1。此时，令 x=s1sj-1，y=sjsl-1，z=slsn。,59,泵引理的证明,由于 x 把 M 从 r1 带到 rj,y 把 M 从 rj 带到 rj，z 把 M 从 rj 带到rn+1，而 rn+1 是一个接受状态，故对于 i 0，M 接受 xyiz。已知 j l，故|y|0，又已知 l p+1，故|xy|p。于是，满足泵引理的3个条件。,60,泵引理的应用,例1.38 设 B=0n1n|n0。用泵引理证明 B 不是正则的。,假设 B 是正则的，令 p 是由泵引理给出的泵长度。选择 s=0p1p 按照泵引理所述，可令 s=xyz使得对于任意的 i 1，串 xyiz 在 B 中。下面考虑 3 种情况：(1)字符串 y 只包含 0。在这种情况下，字符串 xyyz 中的 0 比1 多，从而不是 B 的成员，矛盾。(2)字符串 y 只包含 1。在这种情况下，字符串 xyyz 中的 1 比0 多，从而不是 B 的成员，矛盾。(3)字符串 y 既包含 0 也包含 1。在这种情况下，字符串 xyyz 中的 0 和1 的个数可能相等，但是在0的前面会出现1。因此，xyyz 不是 B 的成员，矛盾。综上，B 不是正则的。,61,泵引理的应用,例1.38 设 B=0n1n|n0。用泵引理证明 B 不是正则的。,假设 B 是正则的，令 p 是由泵引理给出的泵长度。选择 s=0p1p，按照泵引理所述，可令 s=xyz 根据泵引理，有|xy|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+k1pB这与泵引理矛盾。所以，B 不是 正则的。,62,泵引理的应用,例1.39 设 C=w|w 中 0 和 1 的个数相同。用泵引理证明 B 不是正则的。,63,泵引理的应用,例1.40 设 F=w w|w 0,1*。用泵引理证明 B 不是正则的。,64,泵引理的应用,例1.41 设 D=|n0。用泵引理证明 B 不是正则的。,65,泵引理的应用,例1.42 设 E=0i1j|i j。用泵引理证明 B 不是正则的。,66,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,67,本章小结,有穷自动机 DFA M=(Q,q0,F)非确定型有穷自动机 NFA正则表达式正则语言泵引理,68,主要内容,1.1 有穷自动机1.2 非确定性1.3 正则表达式1.4 非正则语言 本章小结 作业,1.6,1.7,1.19,1.29,1.37,