计算理论导引正则语言精选文档.ppt

《计算理论导引正则语言精选文档.ppt》由会员分享，可在线阅读，更多相关《计算理论导引正则语言精选文档.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算理论导引正则语言1本讲稿第一页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业2本讲稿第二页，共六十八页1.1 有穷自动机有穷自动机q实际示例实际示例自动门控制自动门控制前缓冲区前缓冲区后缓冲区后缓冲区CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器处于控制器处于CLOSED状态，假设如下输入信号：状态，假设如下输入信号：FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHE

2、R,考察状态的变化。考察状态的变化。可以给出状态和信号之间的计算。可以给出状态和信号之间的计算。3本讲稿第三页，共六十八页状态图状态图q1q2q3100,101状态状态变换规则变换规则 起始状态起始状态接受状态接受状态4本讲稿第四页，共六十八页状态图状态图q1q2q3100,101q1 q2 q2 q3 q2 =“accept”on input“1101”,the machine goes:010:reject11:accept010100100100100:accept010000010010:reject:reject5本讲稿第五页，共六十八页有穷自动机的形式定义定义定义定义定义1.11.

3、1有穷自动机是一个有穷自动机是一个 5 元组元组(Q,q0,F)，其中，其中(1)Q 是一个有穷集合，称为是一个有穷集合，称为状态集状态集。(2)是一个有穷集合，称为是一个有穷集合，称为字母表字母表。(3):QQ是是转移函数转移函数。(4)q0 Q 是是起始状态起始状态。(5)F Q 是是接受状态集接受状态集。6本讲稿第六页，共六十八页有穷自动机举例例例 给定有穷自动机给定有穷自动机 M1 的状态图。请给出形式化的描述，并确定其能识别的状态图。请给出形式化的描述，并确定其能识别的语言。的语言。M1=(q1,q2,q3,0,1,q1,q2)L(M1)=w|w 至少一个至少一个 1并且在最后的并且

4、在最后的1后面有偶数个后面有偶数个0 q1q2q3100,101若若 A 是机器是机器 M 接受的全部字符串集，则称接受的全部字符串集，则称 A 是机器是机器 M 的语言，的语言，记记作作 L(M)=A，又称又称 M 识别识别 A 或或 M 接受接受 A。7本讲稿第七页，共六十八页有穷自动机举例例例1.2 给定有穷自动机给定有穷自动机 M2 的状态图。请给出形式化的描述，并确定其能的状态图。请给出形式化的描述，并确定其能识别的语言。识别的语言。q1q21001M2=(q1,q2,0,1,q1,q2)L(M2)=w|w 以以 1 结束结束8本讲稿第八页，共六十八页有穷自动机举例例例1.3 给定有

5、穷自动机给定有穷自动机 M3 的状态图。请给出形式化的描述，并确定的状态图。请给出形式化的描述，并确定其能识别的语言。其能识别的语言。q1q21001L(M3)=w|w 是空串或以是空串或以 0 结束结束9本讲稿第九页，共六十八页有穷自动机举例例例1.4 给定有穷自动机给定有穷自动机 M4 的状态图。请给出形式化的描述，并确定其能的状态图。请给出形式化的描述，并确定其能识别的语言。识别的语言。q1abaq2r1r2sbbababa10本讲稿第十页，共六十八页有穷自动机举例例例1.5 给定有穷自动机给定有穷自动机 M5 的状态图。请给出形式化的描述，并确定的状态图。请给出形式化的描述，并确定其能

6、识别的语言。其能识别的语言。q020,q2q1001,2112,M5 以模以模3的方式记录它的方式记录它在输入串中读到的数在输入串中读到的数字之和。字之和。11本讲稿第十一页，共六十八页有穷自动机举例例例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 i12本讲稿第十二页，共六十八页

7、计算的形式化定义定义定义定义定义1.71.7如果一个语言如果一个语言被一台有穷自动机识别被一台有穷自动机识别，则称它是，则称它是正则正则语言语言。设设 M=(Q,q0,F)是一台有穷自动机，是一台有穷自动机，w=w1w2wn 是一个字是一个字符串，并且符串，并且 wi 是字母表是字母表 的成员。如果存在的成员。如果存在 Q 中的状态序列中的状态序列 r0,r1,rn，满足下列条件：，满足下列条件：1)r0=q02)(ri,wi+1)=ri+1,i=0,1,n1 3)rn F则则 M 接受接受 w。13本讲稿第十三页，共六十八页计算的形式化定义举例例例1.8 给定有穷自动机给定有穷自动机 M5

8、的状态图。令的状态图。令w是字符串是字符串1022012给出给出M5对对w计算时进入的状态序列。计算时进入的状态序列。q020,q2q1001,2112,14本讲稿第十四页，共六十八页设计有穷自动机例例：设计有穷自动机：设计有穷自动机 E1，假设字母表是，假设字母表是0,1，识别的语言由所有，识别的语言由所有含有奇数个含有奇数个 1 的字符串组成。的字符串组成。qoddqeven101015本讲稿第十五页，共六十八页设计有穷自动机例例1.9 设计有穷自动机设计有穷自动机 E2，使其能识别含有，使其能识别含有 001 作为子串组成的正则语作为子串组成的正则语言。言。q001qq0q0001010

9、0,1116本讲稿第十六页，共六十八页正则运算定义定义定义定义1.101.10设设 A 和和 B 是两个语言，定义正则运算并、连接和星号如是两个语言，定义正则运算并、连接和星号如下：下：(1)并：并：AB=x|xA 或或 xB(2)连接：连接：A B=xy|xA 且且 yB(3)星号：星号：A*=x1x2xk|k 0 且每一个且每一个xi A 17本讲稿第十七页，共六十八页正则运算例例1.11 设字母表设字母表 是标准的是标准的 26 个字母个字母 a,b,z。又设。又设 A=good,bad,B=boy,girl,求求AB,A B 和和A*。18本讲稿第十八页，共六十八页正则运算定理定理定理

10、定理1.121.12正则语言类在并运算下正则语言类在并运算下封闭封闭。如果如果A1和和A2是正则语言，则是正则语言，则A1A2也是正则语言。也是正则语言。设设 M1 识别识别 A1，M2 识别识别 A2。并设。并设M1=(Q1,1,q1,F1)和和 M2=(Q2,2,q2,F2)构造识别构造识别A1A2 的的 M=(Q,q0,F)Q=Q1 Q2=(r1,r2)|r1 Q1 且且 r2 Q2(r1,r2),a)=(1(r1,a),2(r2,a)q0=(q1,q2)F=(r1,r2)|r1 F1 或或 r2 F219本讲稿第十九页，共六十八页正则运算定理定理定理定理1.131.13正则语言类在连接

11、运算下封闭。正则语言类在连接运算下封闭。证明思路证明思路 按照定理按照定理1.12证明思路试一下。证明思路试一下。输入：输入：输入：输入：M1接受第一段且接受第一段且 M2 接受第二段时，接受第二段时，M才接受；才接受；？M不知道在什么地方将它的输入分开不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始（什么地方第一段结束，第二段开始)20本讲稿第二十页，共六十八页举例证明定理遇到困难，暂时放下证明定理遇到困难，暂时放下引入不确定性引入不确定性Consider the concatenation:考虑下列连接考虑下列连接1,01,11,001,011,0,000,00000,(Th

12、at 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 何处开始？切分问题。何处开始？切分问题。21本讲稿第二十一页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正

13、则语言 本章小结本章小结 作业作业22本讲稿第二十二页，共六十八页非确定性非确定性q非确定性体现在非确定性体现在转换规则转换规则一入多出一入多出,是空字是空字无入转态无入转态q2q1q311q1q223本讲稿第二十三页，共六十八页非确定性非确定性不确定性表现：q q1 11 1 Y Y?Y Y有两个可能状态有两个可能状态有两个可能状态有两个可能状态:q:q1 1,q,q2 2 导致导致导致导致 q q2 2 自动漂移到自动漂移到自动漂移到自动漂移到 q q3 3 是否接受是否接受“01100110”和和”1”0110q1 q1 q2 q3 q4 q41q1,q2,q310,0,11q4q1q2

14、q30,124本讲稿第二十四页，共六十八页非确定性例例1.14 设设 A 是是 0,1 上倒数第三个符号为上倒数第三个符号为 1 的所有字符串组成的的所有字符串组成的语言，构造非确定性自动机语言，构造非确定性自动机。0,11q4q1q2q30,10,125本讲稿第二十五页，共六十八页非确定性例例1.15 考虑图示的考虑图示的 NFA N，它的输入字母表，它的输入字母表 0由一个符号组成。由一个符号组成。只含一个符号的字母表称为只含一个符号的字母表称为一元字母表一元字母表。考虑它接受的语言。考虑它接受的语言。0 000026本讲稿第二十六页，共六十八页非确定性例例1.16 考虑图示的考虑图示的

15、NFA N。运行这台机器，判断其是否识别。运行这台机器，判断其是否识别、a、baba、baa、b、bb、babba。aa,bbq1q2q3a 27本讲稿第二十七页，共六十八页非确定型有穷自动机的形式定义定义定义定义定义1.171.17非确定型有穷自动机非确定型有穷自动机(NFA)是一个是一个 5 元组元组(Q,q0,F)，其中其中(1)Q 是有穷的是有穷的状态集状态集。(2)是有穷的是有穷的字母表字母表。(3):Q P(Q)是是转移函数转移函数。(4)q0 Q 是是起始状态起始状态。(5)F Q 是是接受状态集接受状态集。28本讲稿第二十八页，共六十八页NFA 的形式化描述举例例例1.18 给

16、出图示的给出图示的 NFA 的形式化描述。的形式化描述。10,0,11q4q1q2q30,129本讲稿第二十九页，共六十八页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 3)rn F则则 N 接受接受 w。30本讲稿第三十页，共六十八页NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机

17、都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。1q1q2q3q511q1 q2,q3,q5q11q2q3q511q4112q033q1,q4q03q2,q3,q5q51231本讲稿第三十一页，共六十八页NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。设设 N=(Q,q0,F)是识别语言是识别语言 A 的的NFA。假设假设 N 没有没有 箭头。箭头。构造识别构造识别 A 的的 DFA M=(Q,q0,F )(1)Q=P(Q)(2)对于对于 R

18、 Q 和和 a，令，令 (R,a)=q Q|存在存在 r R,使得使得 q(r,a)(3)q0=q0(4)F =R Q|R 包含包含 N 的一个接受状态的一个接受状态 32本讲稿第三十二页，共六十八页NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。考虑考虑 N 有有 箭头。箭头。对于对于 M 的任意一个状态的任意一个状态 R，定义，定义 E(R)为从为从 R 出发只沿着出发只沿着 箭头可以箭头可以达到的状态集合，包括达到的状态集合，包括 R 本身的所有成员在内。本身的所有成员在内

19、。E(R)=q|从从 R 出发沿着出发沿着 0 或多个或多个 箭头可以到达箭头可以到达 q 修改修改 M 的转移函数的转移函数 (R,a)=q Q|存在存在 r R,使得使得 q E(r,a)q0=E(q0)33本讲稿第三十三页，共六十八页NFA与DFA的等价性推论推论推论推论1.201.20一个语言是正则的，当且仅当有一台非确定型有穷自动机识一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它别它。34本讲稿第三十四页，共六十八页NFA 转换成等价的 DFA 举例例例1.21 将图示的将图示的 NFA N 转换成等价的转换成等价的 DFA。aa,bb123a Q=,1,2,3,1,2,1

20、,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,311,22a1,331,2,32,3bababa,bababa,bab35本讲稿第三十五页，共六十八页在正则运算下的封闭性定理定理定理定理1.221.22正则语言类在并运算下封闭正则语言类在并运算下封闭。NN2N1设设 N1=(Q1,1,q1,F1)N2=(Q2,2,q2,F2)构造构造N=(Q,q0,F)36本讲稿第三十六页，共六十八页NFA与DFA的等价性定理定理定理定理1.231.23正则语言类在连接运算下封闭正则语言类在连接运算下封闭。NN2N137本

21、讲稿第三十七页，共六十八页NFA与DFA的等价性定理定理定理定理1.241.24正则语言类在星运算下封闭正则语言类在星运算下封闭。NN138本讲稿第三十八页，共六十八页DFA和NFA能力等价qDFA机器易算，机器易算，NFA 人易制造，人易制造，通常，人造通常，人造NFA，让机器把，让机器把它变成它变成DFA。q当用并行技术去实现时实际上是用当用并行技术去实现时实际上是用NFA。q当对有指数个节点的树搜索和回溯（可能这里广度优先比深当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用度优先好），是用DFA。q直观解释：对应于直观解释：对应于NFA这样的简单并行程序中可以串行化。

22、这样的简单并行程序中可以串行化。39本讲稿第三十九页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业40本讲稿第四十页，共六十八页正则表达式的引入q算术运算：算术运算：(5+3)4q考察：考察：(01)0*q(01)0*q *描述该字母表上的所有字符串组成的语言。描述该字母表上的所有字符串组成的语言。q *1 描述所有以描述所有以1结尾的字符串组成的语言。结尾的字符串组成的语言。41本讲稿第四十一页，共六十八页正则表达式举例例例1.25 正则表达式的例子正则表达式的例子(01)*

23、。若若 =0,1，则可以用，则可以用 作为作为(01)的缩写。的缩写。*表示该字母表上的所有字符串组成的语言。表示该字母表上的所有字符串组成的语言。*1 是包含所有以是包含所有以 1 结尾的字符串的语言。结尾的字符串的语言。(0 *)(*1)由所有以由所有以 0 开始或者以开始或者以 1 结尾的字符串组成。结尾的字符串组成。42本讲稿第四十二页，共六十八页正则表达式的形式化定义定义定义定义定义1.261.26称称 R 是一个正则表达式，如果是一个正则表达式，如果 R 是是(1)a，这里，这里 a 是字母表是字母表 中的一个元素；中的一个元素；(2)；(3)(4)R1R2，这里，这里 R1 和和

24、 R2 是正则表达式；是正则表达式；(5)R1 R2，这里，这里 R1 和和 R2 是正则表达式；是正则表达式；(6)R1*，这里，这里 R1 是正则表达式；是正则表达式；43本讲稿第四十三页，共六十八页正则表达式举例例例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)*=44本讲稿第四十四页，共六十八页关于正则表达式的说明(1)R =R(2)R =R(

25、3)R =R 可能不成立可能不成立例如，如果例如，如果R=0，那么，那么L(R)=0，而，而L(R )=0,(4)R =R 可能不成立可能不成立例如，如果例如，如果R=0，那么，那么L(R)=0，而，而L(R )=45本讲稿第四十五页，共六十八页正则表达式与有穷自动机的等价性定理定理定理定理1.281.28一个语言是正则的，当且仅当可以用正则表达式描一个语言是正则的，当且仅当可以用正则表达式描述它。述它。引理引理引理引理1.291.29如果一个语言可以用正则表达式描述，那么它是正如果一个语言可以用正则表达式描述，那么它是正则的。则的。引理引理引理引理1.321.32一个语言是正则的，则可以用正

26、则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。46本讲稿第四十六页，共六十八页正则表达式与有穷自动机的等价性引理引理引理引理1.291.29如果一个语言可以用正则表达式描述，那么它是正如果一个语言可以用正则表达式描述，那么它是正则的。则的。把把 R 转换成一台转换成一台 NFA N。考虑考虑 R 的的 6 种情况。种情况。(1)R=a(2)R=(3)R=(4)R=R1R2(5)R=R1 R2(6)R=R1*aq2q1(1)N=(q1,q2,q1,q2)当当 r q1 或或 b a 时，时，(q1,a)=q2，(r,b)=47本讲稿第四十七页，共六十八页正则表达式转换成 NFA例例

27、1.30 把正则表达式把正则表达式(aba)*转换成一台转换成一台 NFA。(1)a(5)(aba)*(2)b(3)ababa(4)aba 48本讲稿第四十八页，共六十八页正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。引入广义非确定型有穷自动机引入广义非确定型有穷自动机GNFA：(1)转移箭头可以用任何正则表达式转移箭头可以用任何正则表达式作标号。作标号。(2)起始状态有射到其它每一个状态的箭头，但是没有从任何其起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。它状态射入

28、的箭头。(3)有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。状态不同。(4)除起始状态和接受状态外，每一个状态到自身和到其它每一除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。个状态都有一个箭头。49本讲稿第四十九页，共六十八页广义非确定型有穷自动机(GNFA)qSqA01*00*110110 子自动机50本讲稿第五十页，共六十八页广义非确定型有穷自动机(GNFA)定义定义定义定义

29、1.331.33GNFA M=(Q,qstart,qaccept)(1)Q 是有穷的状态集。是有穷的状态集。(2)是输入字母表。是输入字母表。(3):(Q-qaccept)(Q-qstart)R 是转移函数。是转移函数。(4)qstart 是起始状态。是起始状态。(5)qaccept 是接受状态。是接受状态。其中其中 R 是正则表达式。是正则表达式。自动机的自动机的 边边 推广为推广为 RE(子程序子程序,子自动机）子自动机）通过增加新的起始状态和新的接受状态，可以将通过增加新的起始状态和新的接受状态，可以将DFA转换成转换成GNFA。51本讲稿第五十一页，共六十八页将 GNFA 转换为等价的

30、正则表达式qiqjqripR4R3R1R2qiqj(R1)(R2)*(R3)(R4)52本讲稿第五十二页，共六十八页正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。证明思路分两步：证明思路分两步：1 RL 有有 DFA M识别（定义），把识别（定义），把DFA 转化称广义的转化称广义的GDFA2把广义的把广义的GDFA转化称正则表达式转化称正则表达式 RE详见教材详见教材p43-4553本讲稿第五十三页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则

31、表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业54本讲稿第五十四页，共六十八页非正则语言对于如下的语言，是否能找到识别该语言的对于如下的语言，是否能找到识别该语言的 DFA？B=0n1n|n0 C=w|w 中中 0 和和 1 的个数相等的个数相等 D=w|w 中中 01 和和 10 作为子串出现的次数相同作为子串出现的次数相同 55本讲稿第五十五页，共六十八页非正则语言q0qmqk56本讲稿第五十六页，共六十八页泵引理(pumping lemma)定理定理定理定理1.371.37若若 A 是一个正则语言，则存在一个数是一个正则语言，则存在一个数 p(泵长度泵长度)使得

32、，使得，如果如果 s 是是 A 中任一长度不小于中任一长度不小于 p 的字符串的字符串，那么，那么 s 可以被可以被分成分成 3 段，段，s=xyz，满足下述条件：，满足下述条件：(1)对于每一个对于每一个 i 0,xyizA(2)|y|0(3)|xy|p我们总能够在离我们总能够在离 s 的开始处不太远的地方找到一个非空的的开始处不太远的地方找到一个非空的串串 y，然后可以把它看作一个，然后可以把它看作一个“泵泵”，重复，重复 y 任意多次，任意多次，或者去掉它，而所得到的结果串仍然属于或者去掉它，而所得到的结果串仍然属于A。57本讲稿第五十七页，共六十八页泵引理的证明设设 M=(Q,q1,F

33、)是一台识别是一台识别 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 出现在序列

34、的前出现在序列的前 p+1 个位置中，而且序列是从个位置中，而且序列是从 r1 开始的，开始的，故有故有 l p+1。此时，令此时，令 x=s1sj-1，y=sjsl-1，z=slsn。58本讲稿第五十八页，共六十八页泵引理的证明由于由于 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个条件。个条件。59

35、本讲稿第五十九页，共六十八页泵引理的应用例例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)字字符符串串

36、 y 只只包包含含 1。在在这这种种情情况况下下，字字符符串串 xyyz 中中的的 1 比比0 多多，从而不是从而不是 B 的成员，矛盾。的成员，矛盾。(3)字字符符串串 y 既既包包含含 0 也也包包含含 1。在在这这种种情情况况下下，字字符符串串 xyyz 中中的的 0 和和1 的的个个数数可可能能相相等等，但但是是在在0的的前前面面会会出出现现1。因因此此，xyyz 不不是是 B 的成员，矛盾。的成员，矛盾。综上，综上，B 不是正则的。不是正则的。60本讲稿第六十页，共六十八页泵引理的应用例例1.38 设设 B=0n1n|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。假设

37、假设 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+k1p B这与泵引理矛盾。这与泵引理矛盾。所以，所以，B 不是不是 正则的。正则的。61本

38、讲稿第六十一页，共六十八页泵引理的应用例例1.39 设设 C=w|w 中中 0 和和 1 的个数相同的个数相同。用泵引理证明。用泵引理证明 B 不是正则不是正则的。的。62本讲稿第六十二页，共六十八页泵引理的应用例例1.40 设设 F=w w|w 0,1*。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。63本讲稿第六十三页，共六十八页泵引理的应用例例1.41 设设 D=|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。64本讲稿第六十四页，共六十八页泵引理的应用例例1.42 设设 E=0i1j|i j。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。65本讲稿第

39、六十五页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业66本讲稿第六十六页，共六十八页本章小结q有穷自动机有穷自动机 DFA M=(Q,q0,F)q非确定型有穷自动机非确定型有穷自动机 NFAq正则表达式正则表达式q正则语言正则语言q泵引理泵引理67本讲稿第六十七页，共六十八页主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业1.6,1.7,1.19,1.29,1.37 68本讲稿第六十八页，共六十八页