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

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

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

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

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

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

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

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

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

L(M)=A，又稱

M識別A

或

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

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

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

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

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

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

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

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

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

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

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

例1.5推廣。對于每一個i>=1，設(shè)Ai是所有這種字符串的語言，其中數(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第十二頁，共六十八頁，編輯于2023年，星期五計(jì)算的形式化定義定義1.7如果一個語言被一臺有窮自動機(jī)識別，則稱它是正則語言。設(shè)M=(Q,,,q0,F)是一臺有窮自動機(jī)，w=w1w2…wn

是一個字符串，并且wi

是字母表

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

rnF則M

接受

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

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

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

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

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

}

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

}

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

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

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

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

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

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

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

Y

?

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

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

設(shè)A是

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

考慮圖示的NFAN

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

考慮圖示的NFAN

。運(yùn)行這臺機(jī)器，判斷其是否識別ε、a、baba、baa、b、bb、babba。aa,bbq1q2q3a27第二十七頁，共六十八頁，編輯于2023年，星期五非確定型有窮自動機(jī)的形式定義定義1.17非確定型有窮自動機(jī)(NFA)是一個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第二十八頁，共六十八頁，編輯于2023年，星期五NFA的形式化描述舉例例1.18

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

是一個字符串，并且wi

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

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

rnF則N接受

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

,q5q51231第三十一頁，共六十八頁，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.19每一臺非確定型有窮自動機(jī)都等價(jià)于某一臺確定型有窮自動機(jī)。設(shè)N=(Q,,,q0,F)是識別語言A的NFA。假設(shè)N沒有箭頭。構(gòu)造識別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的一個接受狀態(tài)}32第三十二頁，共六十八頁，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.19每一臺非確定型有窮自動機(jī)都等價(jià)于某一臺確定型有窮自動機(jī)?？紤]N有箭頭。對于M的任意一個狀態(tài)R，定義E(R)為從R出發(fā)只沿著箭頭可以達(dá)到的狀態(tài)集合，包括R本身的所有成員在內(nèi)。E(R)={q|從R出發(fā)沿著0或多個箭頭可以到達(dá)q}修改M的轉(zhuǎn)移函數(shù)(R,a)={qQ|存在rR,使得qE((r,a))}q0=E({q0})33第三十三頁，共六十八頁，編輯于2023年，星期五NFA與DFA的等價(jià)性推論1.20一個語言是正則的，當(dāng)且僅當(dāng)有一臺非確定型有窮自動機(jī)識別它。34第三十四頁，共六十八頁，編輯于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第三十五頁，共六十八頁，編輯于2023年，星期五在正則運(yùn)算下的封閉性定理1.22正則語言類在并運(yùn)算下封閉。NN2N1設(shè) N1=(Q1,,1,q1,F1) N2=(Q2,,2,q2,F2)構(gòu)造 N=(Q,,,q0,F)36第三十六頁，共六十八頁，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.23正則語言類在連接運(yùn)算下封閉。NN2N137第三十七頁，共六十八頁，編輯于2023年，星期五NFA與DFA的等價(jià)性定理1.24正則語言類在星運(yùn)算下封閉。NN138第三十八頁，共六十八頁，編輯于2023年，星期五DFA和NFA能力等價(jià)DFA機(jī)器易算，NFA人易制造，通常，人造NFA，讓機(jī)器把它變成DFA。當(dāng)用并行技術(shù)去實(shí)現(xiàn)時(shí)實(shí)際上是用NFA。當(dāng)對有指數(shù)個節(jié)點(diǎn)的樹搜索和回溯（可能這里廣度優(yōu)先比深度優(yōu)先好），是用DFA。直觀解釋：對應(yīng)于NFA這樣的簡單并行程序中可以串行化。39第三十九頁，共六十八頁，編輯于2023年，星期五主要內(nèi)容1.1有窮自動機(jī)1.2非確定性1.3正則表達(dá)式1.4非正則語言 本章小結(jié) 作業(yè)40第四十頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式的引入算術(shù)運(yùn)算：(5+3)×4考察：(0∪1)0*(0∪1)0** 描述該字母表上的所有字符串組成的語言。*1描述所有以1結(jié)尾的字符串組成的語言。41第四十一頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式舉例例1.25

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

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

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

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

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

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

，這里R1

和R2

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

，這里R1

是正則表達(dá)式；43第四十三頁，共六十八頁，編輯于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第四十四頁，共六十八頁，編輯于2023年，星期五關(guān)于正則表達(dá)式的說明(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第四十五頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式與有窮自動機(jī)的等價(jià)性定理1.28一個語言是正則的，當(dāng)且僅當(dāng)可以用正則表達(dá)式描述它。引理1.29如果一個語言可以用正則表達(dá)式描述，那么它是正則的。引理1.32一個語言是正則的，則可以用正則表達(dá)式描述它。46第四十六頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式與有窮自動機(jī)的等價(jià)性引理1.29如果一個語言可以用正則表達(dá)式描述，那么它是正則的。把R轉(zhuǎn)換成一臺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第四十七頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式轉(zhuǎn)換成NFA例1.30

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

轉(zhuǎn)換成一臺NFA。(1)a(5)(ab∪a)*(2)b(3)ababa(4)ab∪a48第四十八頁，共六十八頁，編輯于2023年，星期五正則表達(dá)式與有窮自動機(jī)的等價(jià)性引理1.32一個語言是正則的，則可以用正則表達(dá)式描述它。引入廣義非確定型有窮自動機(jī)GNFA：(1)轉(zhuǎn)移箭頭可以用任何正則表達(dá)式作標(biāo)號。(2)起始狀態(tài)有射到其它每一個狀態(tài)的箭頭，但是沒有從任何其它狀態(tài)射入的箭頭。(3)有唯一的一個接受狀態(tài)，并且它有從其它每一個狀態(tài)射入的箭頭，但是沒有射到任何其它狀態(tài)的箭頭。此外，這個接受狀態(tài)和起始狀態(tài)不同。(4)除起始狀態(tài)和接受狀態(tài)外，每一個狀態(tài)到自身和到其它每一個狀態(tài)都有一個箭頭。49第四十九頁，共六十八頁，編輯于2023年，星期五廣義非確定型有窮自動機(jī)(GNFA)qSqA01*00*110110子自動機(jī)50第五十頁，共六十八頁，編輯于2023年，星期五廣義非確定型有窮自動機(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á)式?！詣訖C(jī)的邊推廣為

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

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

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

0,xyiz∈A

(2)|

y

|0(3)|

xy

|≤p我們總能夠在離s

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

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

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

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

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

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

≤p+1，故|xy|≤

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

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

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

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

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

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

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

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