《计算理论导引正则语言精选PPT.ppt》由会员分享，可在线阅读，更多相关《计算理论导引正则语言精选PPT.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算理论导引正则语言1第1页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业2第2页，此课件共68页哦1.1 有穷自动机有穷自动机q实际示例实际示例自动门控制自动门控制前缓冲区前缓冲区后缓冲区后缓冲区CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器处于控制器处于CLOSED状态，假设如下输入信号：状态，假设如下输入信号：FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHE
2、R,考察状态的变化。考察状态的变化。可以给出状态和信号之间的计算。可以给出状态和信号之间的计算。3第3页，此课件共68页哦状态图状态图q1q2q3100,101状态状态变换规则变换规则 起始状态起始状态接受状态接受状态4第4页，此课件共68页哦状态图状态图q1q2q3100,101q1 q2 q2 q3 q2 =“accept”on input“1101”,the machine goes:010:reject11:accept010100100100100:accept010000010010:reject:reject5第5页，此课件共68页哦有穷自动机的形式定义定义定义定义定义1.11.
3、1有穷自动机是一个有穷自动机是一个 5 元组元组(Q,q0,F)，其中，其中(1)Q 是一个有穷集合，称为是一个有穷集合，称为状态集状态集。(2)是一个有穷集合，称为是一个有穷集合，称为字母表字母表。(3):QQ是是转移函数转移函数。(4)q0 Q 是是起始状态起始状态。(5)F Q 是是接受状态集接受状态集。6第6页，此课件共68页哦有穷自动机举例例例 给定有穷自动机给定有穷自动机 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第7页，此课件共68页哦有穷自动机举例例例1.2 给定有穷自动机给定有穷自动机 M2 的状态图。请给出形式化的描述，并确定其的状态图。请给出形式化的描述，并确定其能识别的语言。能识别的语言。q1q21001M2=(q1,q2,0,1,q1,q2)L(M2)=w|w 以以 1 结束结束8第8页，此课件共68页哦有穷自动机举例例例1.3 给定有
5、穷自动机给定有穷自动机 M3 的状态图。请给出形式化的描述，并确定其的状态图。请给出形式化的描述，并确定其能识别的语言。能识别的语言。q1q21001L(M3)=w|w 是空串或以是空串或以 0 结束结束9第9页，此课件共68页哦有穷自动机举例例例1.4 给定有穷自动机给定有穷自动机 M4 的状态图。请给出形式化的描述，并确定其能的状态图。请给出形式化的描述，并确定其能识别的语言。识别的语言。q1abaq2r1r2sbbababa10第10页，此课件共68页哦有穷自动机举例例例1.5 给定有穷自动机给定有穷自动机 M5 的状态图。请给出形式化的描述，并确定其能的状态图。请给出形式化的描述，并确
6、定其能识别的语言。识别的语言。q020,q2q1001,2112,M5 以模以模3的方式记录它的方式记录它在输入串中读到的数在输入串中读到的数字之和。字之和。11第11页，此课件共68页哦有穷自动机举例例例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第12页，此课件共68页
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第13页，此课件共68页哦计算的形式化定义举例例例1.8 给定有穷自动机给定有穷自动机 M5
8、 的状态图。令的状态图。令w是字符串是字符串1022012给出给出M5对对w计算时进入的状态序列。计算时进入的状态序列。q020,q2q1001,2112,14第14页，此课件共68页哦设计有穷自动机例例：设计有穷自动机：设计有穷自动机 E1，假设字母表是，假设字母表是0,1，识别的语言由所有含，识别的语言由所有含有奇数个有奇数个 1 的字符串组成。的字符串组成。qoddqeven101015第15页，此课件共68页哦设计有穷自动机例例1.9 设计有穷自动机设计有穷自动机 E2，使其能识别含有，使其能识别含有 001 作为子串组成的正作为子串组成的正则语言。则语言。q001qq0q000101
9、00,1116第16页，此课件共68页哦正则运算定义定义定义定义1.101.10设设 A 和和 B 是两个语言，定义正则运算并、连接和星号如是两个语言，定义正则运算并、连接和星号如下：下：(1)并：并：AB=x|xA 或或 xB(2)连接：连接：A B=xy|xA 且且 yB(3)星号：星号：A*=x1x2xk|k 0 且每一个且每一个xi A 17第17页，此课件共68页哦正则运算例例1.11 设字母表设字母表 是标准的是标准的 26 个字母个字母 a,b,z。又设。又设 A=good,bad,B=boy,girl,求求AB,A B 和和A*。18第18页，此课件共68页哦正则运算定理定理定
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第19页，此课件共68页哦正则运算定理定理定理定理1.131.13正则语言类在连
11、接运算下封闭。正则语言类在连接运算下封闭。证明思路证明思路 按照定理按照定理1.12证明思路试一下。证明思路试一下。输入：输入：输入：输入：M1接受第一段且接受第一段且 M2 接受第二段时，接受第二段时，M才接受；才接受；？M不知道在什么地方将它的输入分开不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始（什么地方第一段结束，第二段开始)20第20页，此课件共68页哦举例证明定理遇到困难，暂时放下证明定理遇到困难，暂时放下引入不确定性引入不确定性Consider the concatenation:考虑下列连接考虑下列连接1,01,11,001,011,0,000,00000,(T
12、hat 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第21页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正
13、则语言 本章小结本章小结 作业作业22第22页，此课件共68页哦非确定性非确定性q非确定性体现在非确定性体现在转换规则转换规则一入多出一入多出,是空字是空字无入转态无入转态q2q1q311q1q223第23页，此课件共68页哦非确定性非确定性不确定性表现：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,11q4q1q2q3
14、0,124第24页，此课件共68页哦非确定性例例1.14 设设 A 是是 0,1 上倒数第三个符号为上倒数第三个符号为 1 的所有字符串组成的语的所有字符串组成的语言，构造非确定性自动机言，构造非确定性自动机。0,11q4q1q2q30,10,125第25页，此课件共68页哦非确定性例例1.15 考虑图示的考虑图示的 NFA N，它的输入字母表，它的输入字母表 0由一个符号组成。只含由一个符号组成。只含一个符号的字母表称为一个符号的字母表称为一元字母表一元字母表。考虑它接受的语言。考虑它接受的语言。0 000026第26页，此课件共68页哦非确定性例例1.16 考虑图示的考虑图示的 NFA N
15、。运行这台机器，判断其是否识别。运行这台机器，判断其是否识别、a、baba、baa、b、bb、babba。aa,bbq1q2q3a 27第27页，此课件共68页哦非确定型有穷自动机的形式定义定义定义定义定义1.171.17非确定型有穷自动机非确定型有穷自动机(NFA)是一个是一个 5 元组元组(Q,q0,F)，其中其中(1)Q 是有穷的是有穷的状态集状态集。(2)是有穷的是有穷的字母表字母表。(3):Q P(Q)是是转移函数转移函数。(4)q0 Q 是是起始状态起始状态。(5)F Q 是是接受状态集接受状态集。28第28页，此课件共68页哦NFA 的形式化描述举例例例1.18 给出图示的给出图
16、示的 NFA 的形式化描述。的形式化描述。10,0,11q4q1q2q30,129第29页，此课件共68页哦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第30页，此课件共68页哦NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确
17、定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。1q1q2q3q511q1 q2,q3,q5q11q2q3q511q4112q033q1,q4q03q2,q3,q5q51231第31页，此课件共68页哦NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。设设 N=(Q,q0,F)是识别语言是识别语言 A 的的NFA。假设假设 N 没有没有 箭头。箭头。构造识别构造识别 A 的的 DFA M=(Q,q0,F )(1)Q=P(Q)(2)对于对于 R Q 和和 a，令
18、，令 (R,a)=q Q|存在存在 r R,使得使得 q(r,a)(3)q0=q0(4)F =R Q|R 包含包含 N 的一个接受状态的一个接受状态 32第32页，此课件共68页哦NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。考虑考虑 N 有有 箭头。箭头。对于对于 M 的任意一个状态的任意一个状态 R，定义，定义 E(R)为从为从 R 出发只沿着出发只沿着 箭头可箭头可以达到的状态集合，包括以达到的状态集合，包括 R 本身的所有成员在内。本身的所有成员在内。E(R)=q|从从
19、 R 出发沿着出发沿着 0 或多个或多个 箭头可以到达箭头可以到达 q 修改修改 M 的转移函数的转移函数 (R,a)=q Q|存在存在 r R,使得使得 q E(r,a)q0=E(q0)33第33页，此课件共68页哦NFA与DFA的等价性推论推论推论推论1.201.20一个语言是正则的，当且仅当有一台非确定型有穷自动机识一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它别它。34第34页，此课件共68页哦NFA 转换成等价的 DFA 举例例例1.21 将图示的将图示的 NFA N 转换成等价的转换成等价的 DFA。aa,bb123a Q=,1,2,3,1,2,1,3,2,3,1,2,3
20、 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第35页，此课件共68页哦在正则运算下的封闭性定理定理定理定理1.221.22正则语言类在并运算下封闭正则语言类在并运算下封闭。NN2N1设设 N1=(Q1,1,q1,F1)N2=(Q2,2,q2,F2)构造构造N=(Q,q0,F)36第36页，此课件共68页哦NFA与DFA的等价性定理定理定理定理1.231.23正则语言类在连接运算下封闭正则语言类在连接运算下封闭。NN2N137第37页，此课件共68页哦NF
21、A与DFA的等价性定理定理定理定理1.241.24正则语言类在星运算下封闭正则语言类在星运算下封闭。NN138第38页，此课件共68页哦DFA和NFA能力等价qDFA机器易算，机器易算，NFA 人易制造，人易制造，通常，人造通常，人造NFA，让机器把，让机器把它变成它变成DFA。q当用并行技术去实现时实际上是用当用并行技术去实现时实际上是用NFA。q当对有指数个节点的树搜索和回溯（可能这里广度优先比深当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用度优先好），是用DFA。q直观解释：对应于直观解释：对应于NFA这样的简单并行程序中可以串行化。这样的简单并行程序中可以串行化。
22、39第39页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业40第40页，此课件共68页哦正则表达式的引入q算术运算：算术运算：(5+3)4q考察：考察：(01)0*q(01)0*q *描述该字母表上的所有字符串组成的语言。描述该字母表上的所有字符串组成的语言。q *1 描述所有以描述所有以1结尾的字符串组成的语言。结尾的字符串组成的语言。41第41页，此课件共68页哦正则表达式举例例例1.25 正则表达式的例子正则表达式的例子(01)*。若若 =0,1，则可以用，则可以用
23、 作为作为(01)的缩写。的缩写。*表示该字母表上的所有字符串组成的语言。表示该字母表上的所有字符串组成的语言。*1 是包含所有以是包含所有以 1 结尾的字符串的语言。结尾的字符串的语言。(0 *)(*1)由所有以由所有以 0 开始或者以开始或者以 1 结尾的字符串组成。结尾的字符串组成。42第42页，此课件共68页哦正则表达式的形式化定义定义定义定义定义1.261.26称称 R 是一个正则表达式，如果是一个正则表达式，如果 R 是是(1)a，这里，这里 a 是字母表是字母表 中的一个元素；中的一个元素；(2)；(3)(4)R1R2，这里，这里 R1 和和 R2 是正则表达式；是正则表达式；(
24、5)R1 R2，这里，这里 R1 和和 R2 是正则表达式；是正则表达式；(6)R1*，这里，这里 R1 是正则表达式；是正则表达式；43第43页，此课件共68页哦正则表达式举例例例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第44页，此课件共68页哦关于正则表达式的说明(1)R =R(2)R =R(3)R =R 可能不成立可能不成立例如，如
25、果例如，如果R=0，那么，那么L(R)=0，而，而L(R )=0,(4)R =R 可能不成立可能不成立例如，如果例如，如果R=0，那么，那么L(R)=0，而，而L(R )=45第45页，此课件共68页哦正则表达式与有穷自动机的等价性定理定理定理定理1.281.28一个语言是正则的，当且仅当可以用正则表达式描一个语言是正则的，当且仅当可以用正则表达式描述它。述它。引理引理引理引理1.291.29如果一个语言可以用正则表达式描述，那么它是正如果一个语言可以用正则表达式描述，那么它是正则的。则的。引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正
26、则表达式描述它。46第46页，此课件共68页哦正则表达式与有穷自动机的等价性引理引理引理引理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第47页，此课件共68页哦正则表达式转换成 NFA例例1.30 把正则表达式把正则表达式(aba)*转
27、换成一台转换成一台 NFA。(1)a(5)(aba)*(2)b(3)ababa(4)aba 48第48页，此课件共68页哦正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。引入广义非确定型有穷自动机引入广义非确定型有穷自动机GNFA：(1)转移箭头可以用任何正则表达式转移箭头可以用任何正则表达式作标号。作标号。(2)起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。入的箭头。(3)有唯一的一个接受状态，并且它有从其它
28、每一个状态射入的箭头，有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。状态不同。(4)除起始状态和接受状态外，每一个状态到自身和到其它每一除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。个状态都有一个箭头。49第49页，此课件共68页哦广义非确定型有穷自动机(GNFA)qSqA01*00*110110 子自动机50第50页，此课件共68页哦广义非确定型有穷自动机(GNFA)定义定义定义定义1.331.33GNFA M=(Q,qstart,q
29、accept)(1)Q 是有穷的状态集。是有穷的状态集。(2)是输入字母表。是输入字母表。(3):(Q-qaccept)(Q-qstart)R 是转移函数。是转移函数。(4)qstart 是起始状态。是起始状态。(5)qaccept 是接受状态。是接受状态。其中其中 R 是正则表达式。是正则表达式。自动机的自动机的 边边 推广为推广为 RE(子程序子程序,子自动机）子自动机）通过增加新的起始状态和新的接受状态，可以将通过增加新的起始状态和新的接受状态，可以将DFA转换成转换成GNFA。51第51页，此课件共68页哦将 GNFA 转换为等价的正则表达式qiqjqripR4R3R1R2qiqj(R
30、1)(R2)*(R3)(R4)52第52页，此课件共68页哦正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。证明思路分两步：证明思路分两步：1 RL 有有 DFA M识别（定义），把识别（定义），把DFA 转化称广义的转化称广义的GDFA2把广义的把广义的GDFA转化称正则表达式转化称正则表达式 RE详见教材详见教材p43-4553第53页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章
31、小结 作业作业54第54页，此课件共68页哦非正则语言对于如下的语言，是否能找到识别该语言的对于如下的语言，是否能找到识别该语言的 DFA？B=0n1n|n0 C=w|w 中中 0 和和 1 的个数相等的个数相等 D=w|w 中中 01 和和 10 作为子串出现的次数相同作为子串出现的次数相同 55第55页，此课件共68页哦非正则语言q0qmqk56第56页，此课件共68页哦泵引理(pumping lemma)定理定理定理定理1.371.37若若 A 是一个正则语言，则存在一个数是一个正则语言，则存在一个数 p(泵长度泵长度)使得，如果使得，如果 s 是是 A 中任一长度不小于中任一长度不小于
32、 p 的字符串的字符串，那么，那么 s 可以被分成可以被分成 3 段，段，s=xyz，满足下述条件：，满足下述条件：(1)对于每一个对于每一个 i 0,xyizA(2)|y|0(3)|xy|p我们总能够在离我们总能够在离 s 的开始处不太远的地方找到一个非空的的开始处不太远的地方找到一个非空的串串 y，然后可以把它看作一个，然后可以把它看作一个“泵泵”，重复，重复 y 任意多次，任意多次，或者去掉它，而所得到的结果串仍然属于或者去掉它，而所得到的结果串仍然属于A。57第57页，此课件共68页哦泵引理的证明设设 M=(Q,q1,F)是一台识别是一台识别 A 的的 DFA，并设并设 p 是是 M
33、的状态数。的状态数。设设 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 个位置中，而且序列是从个位置中，而且序
34、列是从 r1 开始的，开始的，故有故有 l p+1。此时，令此时，令 x=s1sj-1，y=sjsl-1，z=slsn。58第58页，此课件共68页哦泵引理的证明由于由于 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第59页，此课件共68页哦泵引理的应用例例1.38 设设 B=0n1
35、n|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。假设假设 B 是正则的是正则的，令令 p 是由泵引理给出的泵长度是由泵引理给出的泵长度。选择选择 s=0p1p 按照泵引理所述，可令按照泵引理所述，可令 s=xyz使得对于任意的使得对于任意的 i 1，串，串 xyiz 在在 B 中。下面考虑中。下面考虑 3 种情况：种情况：(1)字字符符串串 y 只只包包含含 0。在在这这种种情情况况下下，字字符符串串 xyyz 中中的的 0 比比1 多多，从从而不是而不是 B 的成员，矛盾。的成员，矛盾。(2)字字符符串串 y 只只包包含含 1。在在这这种种情情况况下下，字字符符串串 xyy
36、z 中中的的 1 比比0 多多，从而不是从而不是 B 的成员，矛盾。的成员，矛盾。(3)字字符符串串 y 既既包包含含 0 也也包包含含 1。在在这这种种情情况况下下，字字符符串串 xyyz 中中的的 0 和和1 的的个个数数可可能能相相等等，但但是是在在0的的前前面面会会出出现现1。因因此此，xyyz 不不是是 B 的成员，矛盾。的成员，矛盾。综上，综上，B 不是正则的。不是正则的。60第60页，此课件共68页哦泵引理的应用例例1.38 设设 B=0n1n|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。假设假设 B 是正则的，令是正则的，令 p 是由泵引理给出的泵长度。是由泵
37、引理给出的泵长度。选择选择 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第61页，此课件共68页哦泵引理的应用例例1.39 设设 C=w|w 中
38、中 0 和和 1 的个数相同的个数相同。用泵引理证明。用泵引理证明 B 不是正不是正则的。则的。62第62页，此课件共68页哦泵引理的应用例例1.40 设设 F=w w|w 0,1*。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。63第63页，此课件共68页哦泵引理的应用例例1.41 设设 D=|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。64第64页，此课件共68页哦泵引理的应用例例1.42 设设 E=0i1j|i j。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。65第65页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业66第66页，此课件共68页哦本章小结q有穷自动机有穷自动机 DFA M=(Q,q0,F)q非确定型有穷自动机非确定型有穷自动机 NFAq正则表达式正则表达式q正则语言正则语言q泵引理泵引理67第67页，此课件共68页哦主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业1.6,1.7,1.19,1.29,1.37 68第68页，此课件共68页哦