計(jì)算理論導(dǎo)引正則語(yǔ)言

計(jì)算理論導(dǎo)引正則語(yǔ)言1第一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五主要內(nèi)容1.1有窮自動(dòng)機(jī)1.2非確定性1.3正則表達(dá)式1.4非正則語(yǔ)言 本章小結(jié) 作業(yè)2第二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五1.1有窮自動(dòng)機(jī)實(shí)際示例—自動(dòng)門(mén)控制前緩沖區(qū)后緩沖區(qū)CLOSEDFRONTOPENNEITHERFRONTREARBOTHREARBOTHNEITHER控制器處于CLOSED狀態(tài)，假設(shè)如下輸入信號(hào)：

FRONT,REAR,NEITHER,FRONT,BOTH,NEITHER,REAR,NEITHER,考察狀態(tài)的變化。可以給出狀態(tài)和信號(hào)之間的計(jì)算。3第三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五狀態(tài)圖q1q2q3100,101狀態(tài)變換規(guī)則

起始狀態(tài)接受狀態(tài)4第四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五狀態(tài)圖q1q2q3100,101q1q2q2q3q2=“accept”oninput“1101”,themachinegoes:010:reject11:accept010100100100100:accept010000010010:reject:reject5第五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)的形式定義定義1.1有窮自動(dòng)機(jī)是一個(gè)5

元組(Q,,,q0,F)，其中(1)Q是一個(gè)有窮集合，稱(chēng)為狀態(tài)集。(2)

是一個(gè)有窮集合，稱(chēng)為字母表。(3):QQ是轉(zhuǎn)移函數(shù)。(4)q0Q是起始狀態(tài)。(5)FQ是接受狀態(tài)集。6第六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例給定有窮自動(dòng)機(jī)M1

的狀態(tài)圖。請(qǐng)給出形式化的描述，并確定其能識(shí)別的語(yǔ)言。M1=({q1,q2,q3},{0,1},,q1,q2

)L(M1)={w|w至少一個(gè)1并且在最后的1后面有偶數(shù)個(gè)0}q1q2q3100,101若A是機(jī)器M接受的全部字符串集，則稱(chēng)

A是機(jī)器M的語(yǔ)言，記作

L(M)=A，又稱(chēng)

M識(shí)別A

或

M接受A。7第七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例1.2

給定有窮自動(dòng)機(jī)M2

的狀態(tài)圖。請(qǐng)給出形式化的描述，并確定其能識(shí)別的語(yǔ)言。q1q21001M2=({q1,q2},{0,1},,q1,q2

)L(M2)={w|w以1結(jié)束}8第八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例1.3

給定有窮自動(dòng)機(jī)M3

的狀態(tài)圖。請(qǐng)給出形式化的描述，并確定其能識(shí)別的語(yǔ)言。q1q21001L(M3)={w|w是空串或以0結(jié)束}9第九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例1.4

給定有窮自動(dòng)機(jī)M4

的狀態(tài)圖。請(qǐng)給出形式化的描述，并確定其能識(shí)別的語(yǔ)言。q1abaq2r1r2sbbababa10第十頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例1.5

給定有窮自動(dòng)機(jī)M5

的狀態(tài)圖。請(qǐng)給出形式化的描述，并確定其能識(shí)別的語(yǔ)言。q020,<RESET>q2q1001,<RESET>2112,<RESET>M5

以模3的方式記錄它在輸入串中讀到的數(shù)字之和。11第十一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五有窮自動(dòng)機(jī)舉例例1.6

例1.5推廣。對(duì)于每一個(gè)i>=1，設(shè)Ai是所有這種字符串的語(yǔ)言，其中數(shù)字之和是i

的倍數(shù)。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+1modi12第十二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五計(jì)算的形式化定義定義1.7如果一個(gè)語(yǔ)言被一臺(tái)有窮自動(dòng)機(jī)識(shí)別，則稱(chēng)它是正則語(yǔ)言。設(shè)M=(Q,,,q0,F)是一臺(tái)有窮自動(dòng)機(jī)，w=w1w2…wn

是一個(gè)字符串，并且wi

是字母表

的成員。如果存在Q中的狀態(tài)序列r0,r1,…,rn，滿(mǎn)足下列條件：1)r0=q02)(ri,wi+1)=ri+1,i=0,1,…,n–1

rnF則M

接受

w。13第十三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五計(jì)算的形式化定義舉例例1.8

給定有窮自動(dòng)機(jī)M5

的狀態(tài)圖。令w是字符串10<RESET>22<RESET>012

給出M5對(duì)w計(jì)算時(shí)進(jìn)入的狀態(tài)序列。q020,<RESET>q2q1001,<RESET>2112,<RESET>14第十四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五設(shè)計(jì)有窮自動(dòng)機(jī)例：設(shè)計(jì)有窮自動(dòng)機(jī)E1，假設(shè)字母表是{0,1}，識(shí)別的語(yǔ)言由所有含有奇數(shù)個(gè)1的字符串組成。qoddqeven101015第十五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五設(shè)計(jì)有窮自動(dòng)機(jī)例1.9

設(shè)計(jì)有窮自動(dòng)機(jī)E2，使其能識(shí)別含有001作為子串組成的正則語(yǔ)言。q001qq0q00010100,1116第十六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則運(yùn)算定義1.10設(shè)A和B是兩個(gè)語(yǔ)言，定義正則運(yùn)算并、連接和星號(hào)如下：并：A∪B={x|x∈A或x∈B

}

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

}

星號(hào)：A*={x1x2…xk|k≤

0且每一個(gè)xi∈A}17第十七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則運(yùn)算例1.11

設(shè)字母表是標(biāo)準(zhǔn)的26個(gè)字母{a,b,…,z}。又設(shè)

A={good,bad},B={boy,girl},求A∪B,AB和A*。18第十八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則運(yùn)算定理1.12正則語(yǔ)言類(lèi)在并運(yùn)算下封閉。如果A1和A2是正則語(yǔ)言，則A1∪A2也是正則語(yǔ)言。設(shè)M1識(shí)別A1，M2識(shí)別A2。并設(shè)M1=(Q1,,1,q1,F1)和M2=(Q2,,2,q2,F2)構(gòu)造識(shí)別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}19第十九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則運(yùn)算定理1.13正則語(yǔ)言類(lèi)在連接運(yùn)算下封閉。證明思路

按照定理1.12證明思路試一下。輸入：M1接受第一段且M2接受第二段時(shí)，M才接受；？M不知道在什么地方將它的輸入分開(kāi)（什么地方第一段結(jié)束，第二段開(kāi)始)20第二十頁(yè)，共六十八頁(yè)，編輯于2023年，星期五舉例證明定理遇到困難，暫時(shí)放下

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

stopsandtheL2substringstarts?如何知道L1何處停止？L2何處開(kāi)始？切分問(wèn)題。21第二十一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五主要內(nèi)容1.1有窮自動(dòng)機(jī)1.2非確定性1.3正則表達(dá)式1.4非正則語(yǔ)言 本章小結(jié) 作業(yè)22第二十二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定性非確定性體現(xiàn)在 轉(zhuǎn)換規(guī)則——一入多出, 是空字——無(wú)入轉(zhuǎn)態(tài)q2q1q311q1q223第二十三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定性不確定性表現(xiàn)：q11

Y

?

Y有兩個(gè)可能狀態(tài):q1,q2導(dǎo)致q2自動(dòng)漂移到q3

是否接受“0110”和”1”0110——q1q1q2q3q4q41——{q1,q2,q3}10,0,11q4q1q2q30,124第二十四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定性例1.14

設(shè)A是

{0,1}上倒數(shù)第三個(gè)符號(hào)為1的所有字符串組成的語(yǔ)言，構(gòu)造非確定性自動(dòng)機(jī)。0,11q4q1q2q30,10,125第二十五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定性例1.15

考慮圖示的NFAN

，它的輸入字母表{0}由一個(gè)符號(hào)組成。只含一個(gè)符號(hào)的字母表稱(chēng)為一元字母表?？紤]它接受的語(yǔ)言。0000026第二十六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定性例1.16

考慮圖示的NFAN

。運(yùn)行這臺(tái)機(jī)器，判斷其是否識(shí)別ε、a、baba、baa、b、bb、babba。aa,bbq1q2q3a27第二十七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非確定型有窮自動(dòng)機(jī)的形式定義定義1.17非確定型有窮自動(dòng)機(jī)(NFA)是一個(gè)5

元組(Q,,,q0,F)，其中(1)Q是有窮的狀態(tài)集。(2)

是有窮的字母表。(3):QεP(Q)是轉(zhuǎn)移函數(shù)。(4)q0Q是起始狀態(tài)。(5)FQ是接受狀態(tài)集。28第二十八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA的形式化描述舉例例1.18

給出圖示的NFA的形式化描述。10,0,11q4q1q2q30,129第二十九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA計(jì)算的形式化定義設(shè)N=(Q,,,q0,F)是一臺(tái)NFA，w=w1w2…wn

是一個(gè)字符串，并且wi

是字母表的成員。如果存在Q中的狀態(tài)序列r0,r1,…,rn，滿(mǎn)足下列條件：1)r0=q02)ri+1

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

rnF則N接受

w。30第三十頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.19每一臺(tái)非確定型有窮自動(dòng)機(jī)都等價(jià)于某一臺(tái)確定型有窮自動(dòng)機(jī)。1q1q2q3q511{q1}→{q2,q3,q5}q11q2q3q511q4112q033q1,q4q03q2,q3

,q5q51231第三十一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.19每一臺(tái)非確定型有窮自動(dòng)機(jī)都等價(jià)于某一臺(tái)確定型有窮自動(dòng)機(jī)。設(shè)N=(Q,,,q0,F)是識(shí)別語(yǔ)言A的NFA。假設(shè)N沒(méi)有箭頭。構(gòu)造識(shí)別A的DFAM=(Q,,,q0,F)(1)Q=P(Q)(2)對(duì)于RQ和a，令(R,a)={qQ|存在rR,使得q(r,a)}(3)q0={q0}(4)F={RQ|R包含N的一個(gè)接受狀態(tài)}32第三十二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.19每一臺(tái)非確定型有窮自動(dòng)機(jī)都等價(jià)于某一臺(tái)確定型有窮自動(dòng)機(jī)?？紤]N有箭頭。對(duì)于M的任意一個(gè)狀態(tài)R，定義E(R)為從R出發(fā)只沿著箭頭可以達(dá)到的狀態(tài)集合，包括R本身的所有成員在內(nèi)。E(R)={q|從R出發(fā)沿著0或多個(gè)箭頭可以到達(dá)q}修改M的轉(zhuǎn)移函數(shù)(R,a)={qQ|存在rR,使得qE((r,a))}q0=E({q0})33第三十三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性推論1.20一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)有一臺(tái)非確定型有窮自動(dòng)機(jī)識(shí)別它。34第三十四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA轉(zhuǎn)換成等價(jià)的DFA舉例例1.21

將圖示的NFAN

轉(zhuǎn)換成等價(jià)的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,bab35第三十五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五在正則運(yùn)算下的封閉性定理1.22正則語(yǔ)言類(lèi)在并運(yùn)算下封閉。NN2N1設(shè) N1=(Q1,,1,q1,F1) N2=(Q2,,2,q2,F2)構(gòu)造 N=(Q,,,q0,F)36第三十六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.23正則語(yǔ)言類(lèi)在連接運(yùn)算下封閉。NN2N137第三十七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.24正則語(yǔ)言類(lèi)在星運(yùn)算下封閉。NN138第三十八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五DFA和NFA能力等價(jià)DFA機(jī)器易算，NFA人易制造，通常，人造NFA，讓機(jī)器把它變成DFA。當(dāng)用并行技術(shù)去實(shí)現(xiàn)時(shí)實(shí)際上是用NFA。當(dāng)對(duì)有指數(shù)個(gè)節(jié)點(diǎn)的樹(shù)搜索和回溯（可能這里廣度優(yōu)先比深度優(yōu)先好），是用DFA。直觀解釋?zhuān)簩?duì)應(yīng)于NFA這樣的簡(jiǎn)單并行程序中可以串行化。39第三十九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五主要內(nèi)容1.1有窮自動(dòng)機(jī)1.2非確定性1.3正則表達(dá)式1.4非正則語(yǔ)言 本章小結(jié) 作業(yè)40第四十頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式的引入算術(shù)運(yùn)算：(5+3)×4考察：(0∪1)0*(0∪1)0** 描述該字母表上的所有字符串組成的語(yǔ)言。*1描述所有以1結(jié)尾的字符串組成的語(yǔ)言。41第四十一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式舉例例1.25

正則表達(dá)式的例子(0∪1)*。若

={0,1}，則可以用作為(0∪1)的縮寫(xiě)。*

表示該字母表上的所有字符串組成的語(yǔ)言。*1

是包含所有以1結(jié)尾的字符串的語(yǔ)言。(0*)∪(*1)

由所有以0開(kāi)始或者以1結(jié)尾的字符串組成。42第四十二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式的形式化定義定義1.26稱(chēng)R是一個(gè)正則表達(dá)式，如果R是(1)a，這里a是字母表中的一個(gè)元素；(2)；(3)

(4)R1∪R2，這里R1和R2是正則表達(dá)式；(5)R1R2

，這里R1

和R2

是正則表達(dá)式；(6)R1*

，這里R1

是正則表達(dá)式；43第四十三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式舉例例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)*={}44第四十四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五關(guān)于正則表達(dá)式的說(shuō)明(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

)=45第四十五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性定理1.28一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)可以用正則表達(dá)式描述它。引理1.29如果一個(gè)語(yǔ)言可以用正則表達(dá)式描述，那么它是正則的。引理1.32一個(gè)語(yǔ)言是正則的，則可以用正則表達(dá)式描述它。46第四十六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性引理1.29如果一個(gè)語(yǔ)言可以用正則表達(dá)式描述，那么它是正則的。把R轉(zhuǎn)換成一臺(tái)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})當(dāng)r≠q1或b≠a時(shí)，(q1,a)={q2}，(r,b)=47第四十七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式轉(zhuǎn)換成NFA例1.30

把正則表達(dá)式(ab∪a)*

轉(zhuǎn)換成一臺(tái)NFA。(1)a(5)(ab∪a)*(2)b(3)ababa(4)ab∪a48第四十八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性引理1.32一個(gè)語(yǔ)言是正則的，則可以用正則表達(dá)式描述它。引入廣義非確定型有窮自動(dòng)機(jī)GNFA：(1)轉(zhuǎn)移箭頭可以用任何正則表達(dá)式作標(biāo)號(hào)。(2)起始狀態(tài)有射到其它每一個(gè)狀態(tài)的箭頭，但是沒(méi)有從任何其它狀態(tài)射入的箭頭。(3)有唯一的一個(gè)接受狀態(tài)，并且它有從其它每一個(gè)狀態(tài)射入的箭頭，但是沒(méi)有射到任何其它狀態(tài)的箭頭。此外，這個(gè)接受狀態(tài)和起始狀態(tài)不同。(4)除起始狀態(tài)和接受狀態(tài)外，每一個(gè)狀態(tài)到自身和到其它每一個(gè)狀態(tài)都有一個(gè)箭頭。49第四十九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五廣義非確定型有窮自動(dòng)機(jī)(GNFA)qSqA01*00*110110子自動(dòng)機(jī)50第五十頁(yè)，共六十八頁(yè)，編輯于2023年，星期五廣義非確定型有窮自動(dòng)機(jī)(GNFA)定義1.33GNFAM=(Q,,,qstart,qaccept)Q是有窮的狀態(tài)集。(2)是輸入字母表。(3):(Q-{qaccept})(Q-{qstart})R是轉(zhuǎn)移函數(shù)。

(4)qstart

是起始狀態(tài)。(5)qaccept

是接受狀態(tài)。其中R是正則表達(dá)式?！詣?dòng)機(jī)的邊推廣為

RE(子程序,子自動(dòng)機(jī)）通過(guò)增加新的起始狀態(tài)和新的接受狀態(tài)，可以將DFA轉(zhuǎn)換成GNFA。51第五十一頁(yè)，共六十八頁(yè)，編輯于2023年，星期五將GNFA轉(zhuǎn)換為等價(jià)的正則表達(dá)式qiqjqripR4R3R1R2qiqj(R1)(R2)*(R3)∪(R4)52第五十二頁(yè)，共六十八頁(yè)，編輯于2023年，星期五正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性引理1.32一個(gè)語(yǔ)言是正則的，則可以用正則表達(dá)式描述它。證明思路分兩步：1RL有DFAM識(shí)別（定義），把DFA轉(zhuǎn)化稱(chēng)廣義的GDFA把廣義的GDFA轉(zhuǎn)化稱(chēng)正則表達(dá)式RE詳見(jiàn)教材p43-4553第五十三頁(yè)，共六十八頁(yè)，編輯于2023年，星期五主要內(nèi)容1.1有窮自動(dòng)機(jī)1.2非確定性1.3正則表達(dá)式1.4非正則語(yǔ)言 本章小結(jié) 作業(yè)54第五十四頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非正則語(yǔ)言對(duì)于如下的語(yǔ)言，是否能找到識(shí)別該語(yǔ)言的DFA？B={0n1n|n≥0}C={w|w中0和1的個(gè)數(shù)相等}D={w|w中01和10作為子串出現(xiàn)的次數(shù)相同}55第五十五頁(yè)，共六十八頁(yè)，編輯于2023年，星期五非正則語(yǔ)言q0qmqk56第五十六頁(yè)，共六十八頁(yè)，編輯于2023年，星期五泵引理(pumpinglemma)

定理1.37若A是一個(gè)正則語(yǔ)言，則存在一個(gè)數(shù)p

(泵長(zhǎng)度)使得，如果s是A中任一長(zhǎng)度不小于p的字符串，那么s可以被分成3段，s=xyz，滿(mǎn)足下述條件：對(duì)于每一個(gè)i

0,xyiz∈A

(2)|

y

|0(3)|

xy

|≤p我們總能夠在離s

的開(kāi)始處不太遠(yuǎn)的地方找到一個(gè)非空的串y，然后可以把它看作一個(gè)“泵”，重復(fù)y

任意多次，或者去掉它，而所得到的結(jié)果串仍然屬于A。57第五十七頁(yè)，共六十八頁(yè)，編輯于2023年，星期五泵引理的證明設(shè)M=(Q,,,q1,F)是一臺(tái)識(shí)別A的DFA，并設(shè)p是M的狀態(tài)數(shù)。設(shè)s=s1s2…sn

是A中長(zhǎng)度為n的字符串，這里n≥p。又設(shè)r1,r2,…,rn+1是M在處理s的過(guò)程中進(jìn)入的狀態(tài)序列，因而ri+1=(ri,si)，1≤i≤n。該序列的長(zhǎng)度為n+1，不小于p+1。根據(jù)鴿巢原理，在該序列的前p+1個(gè)元素中，一定有兩個(gè)相同的狀態(tài)。設(shè)第1個(gè)是rj，第2個(gè)是rl。由于rl出現(xiàn)在序列的前p+1個(gè)位置中，而且序列是從r1開(kāi)始的，故有l(wèi)

≤p+1。此時(shí)，令x=s1…sj-1，y=sj…sl-1，z=sl…sn。58第五十八頁(yè)，共六十八頁(yè)，編輯于2023年，星期五泵引理的證明由于x把M從r1帶到rj,y把M從rj

帶到rj，z把M從rj帶到rn+1，而rn+1是一個(gè)接受狀態(tài)，故對(duì)于i≥0，M接受xyiz。已知j≠

l，故|y|>0，又已知l

≤p+1，故|xy|≤

p。于是，滿(mǎn)足泵引理的3個(gè)條件。59第五十九頁(yè)，共六十八頁(yè)，編輯于2023年，星期五泵引理的應(yīng)用例1.38

設(shè)B={0n1n|n≥0}。用泵引理證明B不是正則的。假設(shè)B

是正則的，令p是由泵引理給出的泵長(zhǎng)度。選擇s=0p1p

按照泵引理所述，可令s=xyz使得對(duì)于任意的i≥1，串xyiz在B

中。下面考慮3種情況：(1)字符串y

只包含0。在這種情況下，字符串xyyz中的0比1多，從而不是B

的成員，矛盾。(2) 字符串y

只包含1。在這種情況下，字符串xyyz中的1比0多，從而不