计算理论导引正则语言

计算理论导引正则语言第一页，共六十八页，2022年，8月28日1主要内容1.1有穷自动机1.2非确定性1.3正则表达式1.4非正则语言 本章小结 作业第二页，共六十八页，2022年，8月28日21.1有穷自动机实际示例—自动门控制前缓冲区后缓冲区CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器处于CLOSED状态，假设如下输入信号：

FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHER,考察状态的变化。可以给出状态和信号之间的计算。第三页，共六十八页，2022年，8月28日3状态图q1q2q3100,101状态变换规则

起始状态接受状态第四页，共六十八页，2022年，8月28日4状态图q1q2q3100,101q1q2q2q3q2=“accept”oninput“1101”,themachinegoes:010:reject11:accept:reject第五页，共六十八页，2022年，8月28日5有穷自动机的形式定义定义1.1有穷自动机是一个5

元组(Q,,,q0,F)，其中(1)Q是一个有穷集合，称为状态集。(2)

是一个有穷集合，称为字母表。(3):QQ是转移函数。(4)q0Q是起始状态。(5)FQ是接受状态集。第六页，共六十八页，2022年，8月28日6有穷自动机举例例给定有穷自动机M1

的状态图。请给出形式化的描述，并确定其能识别的语言。M1=({q1,q2,q3},{0,1},,q1,q2

)L(M1)={w|w至少一个1并且在最后的1后面有偶数个0}q1q2q3100,101若A是机器M接受的全部字符串集，则称

A是机器M的语言，记作

L(M)=A，又称

M识别A

或

M接受A。第七页，共六十八页，2022年，8月28日7有穷自动机举例例1.2

给定有穷自动机M2

的状态图。请给出形式化的描述，并确定其能识别的语言。q1q21001M2=({q1,q2},{0,1},,q1,q2

)L(M2)={w|w以1结束}第八页，共六十八页，2022年，8月28日8有穷自动机举例例1.3

给定有穷自动机M3

的状态图。请给出形式化的描述，并确定其能识别的语言。q1q21001L(M3)={w|w是空串或以0结束}第九页，共六十八页，2022年，8月28日9有穷自动机举例例1.4

给定有穷自动机M4

的状态图。请给出形式化的描述，并确定其能识别的语言。q1abaq2r1r2sbbababa第十页，共六十八页，2022年，8月28日10有穷自动机举例例1.5

给定有穷自动机M5

的状态图。请给出形式化的描述，并确定其能识别的语言。q020,<RESET>q2q1001,<RESET>2112,<RESET>M5

以模3的方式记录它在输入串中读到的数字之和。第十一页，共六十八页，2022年，8月28日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+1modi

(qj

,2)=qk,k=j+2modi

(qj

,<RESET>)=q0

,k=j+1modi第十二页，共六十八页，2022年，8月28日12计算的形式化定义定义1.7如果一个语言被一台有穷自动机识别，则称它是正则语言。设M=(Q,,,q0,F)是一台有穷自动机，w=w1w2…wn

是一个字符串，并且wi

是字母表

的成员。如果存在Q中的状态序列r0,r1,…,rn，满足下列条件：1)r0=q02)(ri,wi+1)=ri+1,i=0,1,…,n–1

rnF则M

接受

w。第十三页，共六十八页，2022年，8月28日13计算的形式化定义举例例1.8

给定有穷自动机M5

的状态图。令w是字符串10<RESET>22<RESET>012

给出M5对w计算时进入的状态序列。q020,<RESET>q2q1001,<RESET>2112,<RESET>第十四页，共六十八页，2022年，8月28日14设计有穷自动机例：设计有穷自动机E1，假设字母表是{0,1}，识别的语言由所有含有奇数个1的字符串组成。qoddqeven1010第十五页，共六十八页，2022年，8月28日15设计有穷自动机例1.9

设计有穷自动机E2，使其能识别含有001作为子串组成的正则语言。q001qq0q00010100,11第十六页，共六十八页，2022年，8月28日16正则运算定义1.10设A和B是两个语言，定义正则运算并、连接和星号如下：并：A∪B={x|x∈A或x∈B

}

连接：AB={xy|x∈A且y∈B

}

星号：A*={x1x2…xk|k≤

0且每一个xi∈A}第十七页，共六十八页，2022年，8月28日17正则运算例1.11

设字母表是标准的26个字母{a,b,…,z}。又设

A={good,bad},B={boy,girl},求A∪B,AB和A*。第十八页，共六十八页，2022年，8月28日18正则运算定理1.12正则语言类在并运算下封闭。如果A1和A2是正则语言，则A1∪A2也是正则语言。设M1识别A1，M2识别A2。并设M1=(Q1,,1,q1,F1)和M2=(Q2,,2,q2,F2)构造识别A1∪A2的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}第十九页，共六十八页，2022年，8月28日19正则运算定理1.13正则语言类在连接运算下封闭。证明思路按照定理1.12证明思路试一下。输入：M1接受第一段且M2接受第二段时，M才接受；？M不知道在什么地方将它的输入分开（什么地方第一段结束，第二段开始)第二十页，共六十八页，2022年，8月28日20举例证明定理遇到困难，暂时放下

——引入不确定性Considertheconcatenation:考虑下列连接{1,01,11,001,011,…}•{0,000,00000,…}(Thatis:thebitstringsthatendwitha“1”,followedbyanoddnumberof0’s.)Problemis:givenastringw,howdoestheautomatonknowwheretheL1part

stopsandtheL2substringstarts?如何知道L1何处停止？L2何处开始？切分问题。第二十一页，共六十八页，2022年，8月28日21主要内容1.1有穷自动机1.2非确定性1.3正则表达式1.4非正则语言 本章小结 作业第二十二页，共六十八页，2022年，8月28日22非确定性非确定性体现在 转换规则——一入多出, 是空字——无入转态q2q1q311q1q2第二十三页，共六十八页，2022年，8月28日23非确定性不确定性表现：q11

Y

?

Y有两个可能状态:q1,q2导致q2自动漂移到q3

是否接受“0110”和”1”0110——q1q1q2q3q4q41——{q1,q2,q3}10,0,11q4q1q2q30,1第二十四页，共六十八页，2022年，8月28日24非确定性例1.14

设A是

{0,1}上倒数第三个符号为1的所有字符串组成的语言，构造非确定性自动机。0,11q4q1q2q30,10,1第二十五页，共六十八页，2022年，8月28日25非确定性例1.15

考虑图示的NFAN

，它的输入字母表{0}由一个符号组成。只含一个符号的字母表称为一元字母表。考虑它接受的语言。00000第二十六页，共六十八页，2022年，8月28日26非确定性例1.16

考虑图示的NFAN

。运行这台机器，判断其是否识别ε、a、baba、baa、b、bb、babba。aa,bbq1q2q3a第二十七页，共六十八页，2022年，8月28日27非确定型有穷自动机的形式定义定义1.17非确定型有穷自动机(NFA)是一个5

元组(Q,,,q0,F)，其中(1)Q是有穷的状态集。(2)

是有穷的字母表。(3):QεP(Q)是转移函数。(4)q0Q是起始状态。(5)FQ是接受状态集。第二十八页，共六十八页，2022年，8月28日28NFA的形式化描述举例例1.18

给出图示的NFA的形式化描述。10,0,11q4q1q2q30,1第二十九页，共六十八页，2022年，8月28日29NFA计算的形式化定义设N=(Q,,,q0,F)是一台NFA，w=w1w2…wn

是一个字符串，并且wi

是字母表的成员。如果存在Q中的状态序列r0,r1,…,rn，满足下列条件：1)r0=q02)ri+1

(ri,wi+1)=,i=0,1,…,n–1

rnF则N接受

w。第三十页，共六十八页，2022年，8月28日30NFA与DFA的等价性定理1.19每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。1q1q2q3q511{q1}→{q2,q3,q5}q11q2q3q511q4112q033q1,q4q03q2,q3

,q5q512第三十一页，共六十八页，2022年，8月28日31NFA与DFA的等价性定理1.19每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。设N=(Q,,,q0,F)是识别语言A的NFA。假设N没有箭头。构造识别A的DFAM=(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的一个接受状态}第三十二页，共六十八页，2022年，8月28日32NFA与DFA的等价性定理1.19每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。考虑N有箭头。对于M的任意一个状态R，定义E(R)为从R出发只沿着箭头可以达到的状态集合，包括R本身的所有成员在内。E(R)={q|从R出发沿着0或多个箭头可以到达q}修改M的转移函数(R,a)={qQ|存在rR,使得qE((r,a))}q0=E({q0})第三十三页，共六十八页，2022年，8月28日33NFA与DFA的等价性推论1.20一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它。第三十四页，共六十八页，2022年，8月28日34NFA转换成等价的DFA举例例1.21

将图示的NFAN

转换成等价的DFA。aa,bb123aQ={,{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}bababa,bababa,bab第三十五页，共六十八页，2022年，8月28日35在正则运算下的封闭性定理1.22正则语言类在并运算下封闭。NN2N1设 N1=(Q1,,1,q1,F1) N2=(Q2,,2,q2,F2)构造 N=(Q,,,q0,F)第三十六页，共六十八页，2022年，8月28日36NFA与DFA的等价性定理1.23正则语言类在连接运算下封闭。NN2N1第三十七页，共六十八页，2022年，8月28日37NFA与DFA的等价性定理1.24正则语言类在星运算下封闭。NN1第三十八页，共六十八页，2022年，8月28日38DFA和NFA能力等价DFA机器易算，NFA人易制造，通常，人造NFA，让机器把它变成DFA。当用并行技术去实现时实际上是用NFA。当对有指数个节点的树搜索和回溯（可能这里广度优先比深度优先好），是用DFA。直观解释：对应于NFA这样的简单并行程序中可以串行化。第三十九页，共六十八页，2022年，8月28日39主要内容1.1有穷自动机1.2非确定性1.3正则表达式1.4非正则语言 本章小结 作业第四十页，共六十八页，2022年，8月28日40正则表达式的引入算术运算：(5+3)×4考察：(0∪1)0*(0∪1)0** 描述该字母表上的所有字符串组成的语言。*1描述所有以1结尾的字符串组成的语言。第四十一页，共六十八页，2022年，8月28日41正则表达式举例例1.25

正则表达式的例子(0∪1)*。若

={0,1}，则可以用作为(0∪1)的缩写。*

表示该字母表上的所有字符串组成的语言。*1

是包含所有以1结尾的字符串的语言。(0*)∪(*1)

由所有以0开始或者以1结尾的字符串组成。第四十二页，共六十八页，2022年，8月28日42正则表达式的形式化定义定义1.26称R是一个正则表达式，如果R是(1)a，这里a是字母表中的一个元素；(2)；(3)

(4)R1∪R2，这里R1和R2是正则表达式；(5)R1R2

，这里R1

和R2

是正则表达式；(6)R1*

，这里R1

是正则表达式；第四十三页，共六十八页，2022年，8月28日43正则表达式举例例1.27

在下面的例子中假定字母表是

{0,1}。(1)0*10*

(2)

*1*(3)

*001*(4)(01+)*(5)()*(6)(

)*(7)01∪10(8)0*0∪1*1∪0∪1(9)(0∪)1*=01*

∪1*(10)(0∪)(1∪)={0,1,10,}(11)1*=(12)*={}第四十四页，共六十八页，2022年，8月28日44关于正则表达式的说明(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

)=第四十五页，共六十八页，2022年，8月28日45正则表达式与有穷自动机的等价性定理1.28一个语言是正则的，当且仅当可以用正则表达式描述它。引理1.29如果一个语言可以用正则表达式描述，那么它是正则的。引理1.32一个语言是正则的，则可以用正则表达式描述它。第四十六页，共六十八页，2022年，8月28日46正则表达式与有穷自动机的等价性引理1.29如果一个语言可以用正则表达式描述，那么它是正则的。把R转换成一台NFA

N。考虑R的6种情况。(1)R=a(2)R=(3)R=(4)R=

R1∪R2(5)R=

R1R2(6)R=R1*aq2q1(1)N=({q1,q2},,,q1,{q2})当r≠q1或b≠a时，(q1,a)={q2}，(r,b)=第四十七页，共六十八页，2022年，8月28日47正则表达式转换成NFA例1.30

把正则表达式(ab∪a)*

转换成一台NFA。(1)a(5)(ab∪a)*(2)b(3)ababa(4)ab∪a第四十八页，共六十八页，2022年，8月28日48正则表达式与有穷自动机的等价性引理1.32一个语言是正则的，则可以用正则表达式描述它。引入广义非确定型有穷自动机GNFA：(1)转移箭头可以用任何正则表达式作标号。(2)起始状态有射到其它每一个状态的箭头，但是没有从任何其它状态射入的箭头。(3)有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到任何其它状态的箭头。此外，这个接受状态和起始状态不同。(4)除起始状态和接受状态外，每一个状态到自身和到其它每一个状态都有一个箭头。第四十九页，共六十八页，2022年，8月28日49广义非确定型有穷自动机(GNFA)qSqA01*00*110110子自动机第五十页，共六十八页，2022年，8月28日50广义非确定型有穷自动机(GNFA)定义1.33GNFAM=(Q,,,qstart,qaccept)Q是有穷的状态集。(2)是输入字母表。(3):(Q-{qaccept})(Q-{qstart})R是转移函数。

(4)qstart

是起始状态。(5)qaccept

是接受状态。其中R

是正则表达式。※自动机的边推广为

RE(子程序,子自动机）通过增加新的起始状态和新的接受状态，可以将DFA转换成GNFA。第五十一页，共六十八页，2022年，8月28日51将GNFA转换为等价的正则表达式qiqjqripR4R3R1R2qiqj(R1)(R2)*(R3)∪(R4)第五十二页，共六十八页，2022年，8月28日52正则表达式与有穷自动机的等价性引理1.32一个语言是正则的，则可以用正则表达式描述它。证明思路分两步：1RL有DFAM识别（定义），把DFA转化称广义的GDFA把广义的GDFA转化称正则表达式RE详见教材p43-45第五十三页，共六十八页，2022年，8月28日53主要内容1.1有穷自动机1.2非确定性1.3正则表达式1.4非正则语言 本章小结 作业第五十四页，共六十八页，2022年，8月28日54非正则语言对于如下的语言，是否能找到识别该语言的DFA？B={0n1n|n≥0}C={w|w中0和1的个数相等}D={w|w中01和10作为子串出现的次数相同}第五十五页，共六十八页，2022年，8月28日55非正则语言q0qmqk第五十六页，共六十八页，2022年，8月28日56泵引理(pumpinglemma)

定理1.37若A是一个正则语言，则存在一个数p

(泵长度)使得，如果s是A中任一长度不小于p的字符串，那么s可以被分成3段，s=xyz，满足下述条件：对于每一个i

0,xyiz∈A

(2)|

y

|0(3)|

xy

|≤p我们总能够在离s

的开始处不太远的地方找到一个非空的串y，然后可以把它看作一个“泵”，重复y

任意多次，或者去掉它，而所得到的结果串仍然属于A。第五十七页，共六十八页，2022年，8月28日57泵引理的证明设M=(Q,,,q1,F)是一台识别A的DFA，并设p是M的状态数。设s=s1s2…sn

是A中长度为n的字符串，这里n≥p。又设r1,r2,…,rn+1是M在处理s的过程中进入的状态序列，因而ri+1=(ri,si)，1≤i≤n。该序列的长度为n+1，不小于p+1。根据鸽巢原理，在该序列的前p+1个元素中，一定有两个相同的状态。设第1个是rj，第2个是rl。由于rl出现在序列的前p+1个位置中，而且序列是从r1开始的，故有l

≤p+1。此时，令x=s1…sj-1，y=sj…sl-1，z=sl…sn。第五十八页，共六十八页，2022年，8月28日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个条件。第五十九页，共六十八页，2022年，8月28日59泵引理的应用例1.38

设B={0n1n|n≥0}。用泵引理证明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多，从而不是