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

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

1、计算理论1主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业21.1 有穷自动机有穷自动机q实际示例实际示例自动门控制自动门控制前缓冲区前缓冲区后缓冲区后缓冲区CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器处于控制器处于CLOSED状态，假设如下输入信号：状态，假设如下输入信号：FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHER,考察状态的变化。考察状态的变化。可以给出状态和信号之间的

2、计算。可以给出状态和信号之间的计算。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.1有穷自动机是一个有穷自动机是一个 5 元组元组(Q,q0,F)，其中，其中(1)Q 是一个有穷集合，称为是一个有穷集合，称为状态集

3、状态集。(2)是一个有穷集合，称为是一个有穷集合，称为字母表字母表。(3):QQ是是转移函数转移函数。(4)q0 Q 是是起始状态起始状态。(5)F Q 是是接受状态集接受状态集。6有穷自动机举例例例 给定有穷自动机给定有穷自动机 M1 的状态图。请给出形式化的描述，并确的状态图。请给出形式化的描述，并确定其能识别的语言。定其能识别的语言。M1=(q1,q2,q3,0,1,q1,q2)L(M1)=w|w 至少一个至少一个 1并且在最后的并且在最后的1后面有偶数个后面有偶数个0 q1q2q3100,101若若 A 是机器是机器 M 接受的全部字符串集，则称接受的全部字符串集，则称 A 是机器是机

4、器 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 给定有穷自动机给定有穷自动机 M3 的状态图。请给出形式化的描述，的状态图。请给出形式化的描述，并确定其能识别的语言。并确定其能识别的语言。q1q21001L(M3)=w|w 是空串或以是空串或以 0 结束结束

5、9有穷自动机举例例例1.4 给定有穷自动机给定有穷自动机 M4 的状态图。请给出形式化的描述，的状态图。请给出形式化的描述，并确定其能识别的语言。并确定其能识别的语言。q1abaq2r1r2sbbababa10有穷自动机举例例例1.5 给定有穷自动机给定有穷自动机 M5 的状态图。请给出形式化的描述，的状态图。请给出形式化的描述，并确定其能识别的语言。并确定其能识别的语言。q020,q2q1001,2112,M5 以模以模3的方式记录的方式记录它在输入串中读到它在输入串中读到的数字之和。的数字之和。11有穷自动机举例例例1.6 例例1.5推广。对于每一个推广。对于每一个 i=1，设，设 Ai

6、是所有这种字符串是所有这种字符串的语言，其中数字之和是的语言，其中数字之和是 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计算的形式化定义定义定义定义定义1.71.7如果一个语言如果一个语言被一台有穷自动机识别被一台有穷自动机识别，则称它是，则称它是正则正则语言语言。设设 M=(Q,q0,F)是一台有穷自动机，是一台有穷自动机，w=w1w2wn 是是一个字符串，并且一个字符串，并且 wi 是字母表是字母表 的成员。如果存在

7、的成员。如果存在 Q 中的中的状态序列状态序列 r0,r1,rn，满足下列条件：，满足下列条件：1)r0=q02)(ri,wi+1)=ri+1,i=0,1,n1 rn F则则 M 接受接受 w。13计算的形式化定义举例例例1.8 给定有穷自动机给定有穷自动机 M5 的状态图。令的状态图。令w是字符串是字符串1022012给出给出M5对对w计算时进入的状态序列。计算时进入的状态序列。q020,q2q1001,2112,14设计有穷自动机例例：设计有穷自动机：设计有穷自动机 E1，假设字母表是，假设字母表是0,1，识别的语言由，识别的语言由所有含有奇数个所有含有奇数个 1 的字符串组成。的字符串组

8、成。qoddqeven101015设计有穷自动机例例1.9 设计有穷自动机设计有穷自动机 E2，使其能识别含有，使其能识别含有 001 作为子串组成作为子串组成的正则语言。的正则语言。q001qq0q00010100,1116正则运算定义定义定义定义1.101.10设设 A 和和 B 是两个语言，定义正则运算并、连接和星号是两个语言，定义正则运算并、连接和星号如下：如下：(1)并：并：AB=x|xA 或或 xB 连接：连接：A B=xy|xA 且且 yB 星号：星号：A*=x1x2xk|k 0 且每一个且每一个xi A 17正则运算例例1.11 设字母表设字母表 是标准的是标准的 26 个字母

9、个字母 a,b,z。又设。又设 A=good,bad,B=boy,girl,求求AB,A B 和和A*。18正则运算定理定理定理定理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=(

10、r1,r2)|r1 F1 或或 r2 F219正则运算定理定理定理定理1.131.13正则语言类在连接运算下封闭。正则语言类在连接运算下封闭。证明思路证明思路 按照定理按照定理1.12证明思路试一下。证明思路试一下。输入：输入：输入：输入：M1接受第一段且接受第一段且 M2 接受第二段时，接受第二段时，M才接受；才接受；？M不知道在什么地方将它的输入分开不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始（什么地方第一段结束，第二段开始)20举例证明定理遇到困难，暂时放下证明定理遇到困难，暂时放下引入不确定性引入不确定性Consider the concatenation:考虑下列连

11、接考虑下列连接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 何处开始？切分问题。何处开始？切分问题。21主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1

12、.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业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,11q4q1q2q30,

13、124非确定性例例1.14 设设 A 是是 0,1 上倒数第三个符号为上倒数第三个符号为 1 的所有字符串组的所有字符串组成的语言，构造非确定性自动机成的语言，构造非确定性自动机。0,11q4q1q2q30,10,125非确定性例例1.15 考虑图示的考虑图示的 NFA N，它的输入字母表，它的输入字母表 0由一个符号由一个符号组成。只含一个符号的字母表称为组成。只含一个符号的字母表称为一元字母表一元字母表。考虑它。考虑它接受的语言。接受的语言。0 000026非确定性例例1.16 考虑图示的考虑图示的 NFA N。运行这台机器，判断其是否识别。运行这台机器，判断其是否识别、a、baba、ba

14、a、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 是是接受状态集接受状态集。28NFA 的形式化描述举例例例1.18 给出图示的给出图示的 NFA 的形式化描述。的形式化描述。10,0,11q4q1q2q30,129NFA 计算的形式化定义设设 N=(Q,q0,F

15、)是一台是一台 NFA，w=w1w2wn 是一个是一个字符串，并且字符串，并且 wi 是字母表是字母表 的成员。如果存在的成员。如果存在 Q 中的状态中的状态序列序列 r0,r1,rn，满足下列条件：，满足下列条件：1)r0=q02)ri+1 (ri,wi+1)=,i=0,1,n1 rn F则则 N 接受接受 w。30NFA与DFA的等价性定理定理定理定理1.191.19每一台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。1q1q2q3q511q1 q2,q3,q5q11q2q3q511q4112q033q1,q4q03q2,q3,q5

16、q51231NFA与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，令，令 (R,a)=q Q|存在存在 r R,使得使得 q(r,a)(3)q0=q0(4)F =R Q|R 包含包含 N 的一个接受状态的一个接受状态 32NFA与DFA的等价性定理定理定理定理1.191.19每一

17、台非确定型有穷自动机都等价于某一台确定型有每一台非确定型有穷自动机都等价于某一台确定型有穷自动机穷自动机。考虑考虑 N 有有 箭头。箭头。对于对于 M 的任意一个状态的任意一个状态 R，定义，定义 E(R)为从为从 R 出发只沿着出发只沿着 箭头可以达到的状态集合，包括箭头可以达到的状态集合，包括 R 本身的所有成员在内。本身的所有成员在内。E(R)=q|从从 R 出发沿着出发沿着 0 或多个或多个 箭头可以到达箭头可以到达 q 修改修改 M 的转移函数的转移函数 (R,a)=q Q|存在存在 r R,使得使得 q E(r,a)q0=E(q0)33NFA与DFA的等价性推论推论推论推论1.20

18、1.20一个语言是正则的，当且仅当有一台非确定型有穷自一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它动机识别它。34NFA 转换成等价的 DFA 举例例例1.21 将图示的将图示的 NFA N 转换成等价的转换成等价的 DFA。aa,bb123a 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,311,22a1,331,2,32,3bababa,bababa,bab35在正则运算下的封闭性定理定理定理定理1.221.22正则语言类在并运算下封闭正则语言类在并运算下封闭。N

19、N2N1设设 N1=(Q1,1,q1,F1)N2=(Q2,2,q2,F2)构造构造N=(Q,q0,F)36NFA与DFA的等价性定理定理定理定理1.231.23正则语言类在连接运算下封闭正则语言类在连接运算下封闭。NN2N137NFA与DFA的等价性定理定理定理定理1.241.24正则语言类在星运算下封闭正则语言类在星运算下封闭。NN138DFA和NFA能力等价qDFA机器易算，机器易算，NFA 人易制造，人易制造，通常，人造通常，人造NFA，让机器，让机器把它变成把它变成DFA。q当用并行技术去实现时实际上是用当用并行技术去实现时实际上是用NFA。q当对有指数个节点的树搜索和回溯（可能这里广

20、度优先比深当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用度优先好），是用DFA。q直观解释：对应于直观解释：对应于NFA这样的简单并行程序中可以串行化。这样的简单并行程序中可以串行化。39主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业40正则表达式的引入q算术运算：算术运算：(5+3)4q考察：考察：(01)0*q(01)0*q *描述该字母表上的所有字符串组成的语言。描述该字母表上的所有字符串组成的语言。q *1 描述所有以描述所有以1结尾的字符串组成的语言。结尾的

21、字符串组成的语言。41正则表达式举例例例1.25 正则表达式的例子正则表达式的例子(01)*。若若 =0,1，则可以用，则可以用 作为作为(01)的缩写。的缩写。*表示该字母表上的所有字符串组成的语言。表示该字母表上的所有字符串组成的语言。*1 是包含所有以是包含所有以 1 结尾的字符串的语言。结尾的字符串的语言。(0 *)(*1)由所有以由所有以 0 开始或者以开始或者以 1 结尾的字符串组成。结尾的字符串组成。42正则表达式的形式化定义定义定义定义定义1.261.26称称 R 是一个正则表达式，如果是一个正则表达式，如果 R 是是(1)a，这里，这里 a 是字母表是字母表 中的一个元素；中

22、的一个元素；(2)；(3)(4)R1R2，这里，这里 R1 和和 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

23、 =R(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一个语言是正则的，则可以用正则表达式描述它。一个

24、语言是正则的，则可以用正则表达式描述它。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例例1.30 把正则表达式把正则表达式(aba)*转换成一台转换成一台 NFA。

25、(1)a(5)(aba)*(2)b(3)ababa(4)aba 48正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式描述它。一个语言是正则的，则可以用正则表达式描述它。引入广义非确定型有穷自动机引入广义非确定型有穷自动机GNFA：(1)转移箭头可以用任何正则表达式转移箭头可以用任何正则表达式作标号。作标号。(2)起始状态有射到其它每一个状态的箭头，但是没有从任起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。何其它状态射入的箭头。(3)有唯一的一个接受状态，并且它有从其它每一个状态射有唯一的一个接受状态，并且它有从其它每一个

26、状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。个接受状态和起始状态不同。(4)除起始状态和接受状态外，每一个状态到自身和到其它除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。每一个状态都有一个箭头。49广义非确定型有穷自动机(GNFA)qSqA01*00*110110 子自动机50广义非确定型有穷自动机(GNFA)定义定义定义定义1.331.33GNFA M=(Q,qstart,qaccept)(1)Q 是有穷的状态集。是有穷的状态集。(2)是输入字母表。是输入字母表。(3):(Q-q

27、accept)(Q-qstart)R 是转移函数。是转移函数。(4)qstart 是起始状态。是起始状态。(5)qaccept 是接受状态。是接受状态。其中其中 R 是正则表达式。是正则表达式。自动机的自动机的 边边 推广为推广为 RE(子程序子程序,子自动机）子自动机）通过增加新的起始状态和新的接受状态，可以将通过增加新的起始状态和新的接受状态，可以将DFA转换成转换成GNFA。51将 GNFA 转换为等价的正则表达式qiqjqripR4R3R1R2qiqj(R1)(R2)*(R3)(R4)52正则表达式与有穷自动机的等价性引理引理引理引理1.321.32一个语言是正则的，则可以用正则表达式

28、描述它。一个语言是正则的，则可以用正则表达式描述它。证明思路分两步：证明思路分两步：1 RL 有有 DFA M识别（定义），把识别（定义），把DFA 转化称广义的转化称广义的GDFA2把广义的把广义的GDFA转化称正则表达式转化称正则表达式 RE3详见教材详见教材p43-4553主要内容主要内容1.1 有穷自动机有穷自动机1.2 非确定性非确定性1.3 正则表达式正则表达式1.4 非正则语言非正则语言 本章小结本章小结 作业作业54非正则语言对于如下的语言，是否能找到识别该语言的对于如下的语言，是否能找到识别该语言的 DFA？B=0n1n|n0 C=w|w 中中 0 和和 1 的个数相等的个数

29、相等 D=w|w 中中 01 和和 10 作为子串出现的次数相同作为子串出现的次数相同 55非正则语言q0qmqk56泵引理(pumping lemma)定理定理定理定理1.371.37若若 A 是一个正则语言，则存在一个数是一个正则语言，则存在一个数 p(泵长度泵长度)使使得，如果得，如果 s 是是 A 中任一长度不小于中任一长度不小于 p 的字符串的字符串，那，那么么 s 可以被分成可以被分成 3 段，段，s=xyz，满足下述条件：，满足下述条件：对于每一个对于每一个 i 0,xyizA(2)|y|0(3)|xy|p我们总能够在离我们总能够在离 s 的开始处不太远的地方找到一个非空的的开始

30、处不太远的地方找到一个非空的串串 y，然后可以把它看作一个，然后可以把它看作一个“泵泵”，重复，重复 y 任意多次，任意多次，或者去掉它，而所得到的结果串仍然属于或者去掉它，而所得到的结果串仍然属于A。57泵引理的证明设设 M=(Q,q1,F)是一台识别是一台识别 A 的的 DFA，并设并设 p 是是 M 的状态数。的状态数。设设 s=s1s2sn 是是 A 中长度为中长度为 n 的字符串，这里的字符串，这里 np。又设又设 r1,r2,rn+1 是是 M 在处理在处理 s 的过程中进入的状态序列，的过程中进入的状态序列，因而因而 ri+1=(ri,si)，1in。该序列的长度为该序列的长度为

31、 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。58泵引理的证明由于由于 x 把把 M 从从 r1 带到带到 rj,y 把把 M 从从 rj 带到带到 rj，z 把把 M 从从 rj 带到带到rn+1，而，而 rn+1

32、是一个接受状态，是一个接受状态，故故对于对于 i 0，M 接受接受 xyiz。已知已知 j l，故，故|y|0，又已知又已知 l p+1，故，故|xy|p。于是，满足泵引理的于是，满足泵引理的3个条件。个条件。59泵引理的应用例例1.38 设设 B=0n1n|n0。用泵引理证明。用泵引理证明 B 不是正则的。不是正则的。假设假设 B 是正则的是正则的，令令 p 是由泵引理给出的泵长度是由泵引理给出的泵长度。选择选择 s=0p1p 按照泵引理所述，可令按照泵引理所述，可令 s=xyz使得对于任意的使得对于任意的 i 1，串，串 xyiz 在在 B 中。下面考虑中。下面考虑 3 种情况：种情况：(

33、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 的成员，矛盾。的成

34、员，矛盾。综上，综上，B 不是正则的。不是正则的。60泵引理的应用例例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

35、+k1p注意到注意到 k1，所以，所以，p+kp。这就是说，这就是说，0p+k1p B这与泵引理矛盾。这与泵引理矛盾。所以，所以，B 不是不是 正则的。正则的。61泵引理的应用例例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主要内容主要内容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