計(jì)算理論與算法分析設(shè)計(jì)：CH2有窮自動機(jī)

CH2有窮自動機(jī)

11/6/202212.1確定型有窮自動機(jī)有窮狀態(tài)自動機(jī)(Finite-stateAutomation簡稱FA)是具有離散的輸入\輸出系統(tǒng)的數(shù)學(xué)模型。系統(tǒng)內(nèi)部具有有窮個(gè)狀態(tài)，系統(tǒng)的狀態(tài)概括了對過去輸入狀況的處理信息，系統(tǒng)只需根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入就可以決定系統(tǒng)的后繼行為，系統(tǒng)處理了當(dāng)前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生變化。電梯控制裝置、文本編輯程序、編譯技術(shù)中的詞法分析程序，計(jì)算機(jī)以及人腦都是有窮狀態(tài)系統(tǒng)。11/6/20222輸入帶：有窮控制器：運(yùn)行開始時(shí)，讀寫頭指向最左邊的字符，控制器處于開始指定的初始狀態(tài)根據(jù)最后的狀態(tài)表明是否接受被輸入的字符串11/6/20223

1-91,3,5,7,92.1確定型有窮自動機(jī)104397TAS1,3,5,7,9輸入帶有窮控制器讀頭0-911/6/20224定義2.1.1

一個(gè)確定有窮自動機(jī)DFA是一個(gè)五元組M=(K,,δ,s,F)其中，K：是非空有窮狀態(tài)集,其中的每個(gè)元素稱為一個(gè)狀態(tài)；：是有窮輸入字母表，它的每一個(gè)元素稱為一個(gè)輸入符號；δ

：是一個(gè)單值映射KK，也稱狀態(tài)轉(zhuǎn)換函數(shù)，δ(q,x)=q意指：當(dāng)現(xiàn)行狀態(tài)為q，面臨的輸入符號為x時(shí)，將轉(zhuǎn)到下一狀態(tài)q，q稱為q的一個(gè)后繼狀態(tài)；s

K稱之為開始狀態(tài)；FK稱為終止?fàn)顟B(tài)集，至少由一個(gè)終止?fàn)顟B(tài)組成。11/6/20225

DFA轉(zhuǎn)換矩陣:

該矩陣列表示狀態(tài)集；輸入字母表；δ（q,a）的值。即某個(gè)狀態(tài)面臨某列輸入字符所唯一轉(zhuǎn)向的下一個(gè)狀態(tài)。該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣

DFA轉(zhuǎn)換矩陣11/6/202262.1確定型有窮自動機(jī)

abab表2-111/6/202272.1確定型有窮自動機(jī)

abab11/6/202282.1確定型有窮自動機(jī)

11/6/202292.1確定型有窮自動機(jī)

11/6/2022102.1確定型有窮自動機(jī)qabababab表2-211/6/2022112.1確定型有窮自動機(jī)11/6/202212狀態(tài)轉(zhuǎn)換圖一個(gè)DFA也可表示成一張狀態(tài)轉(zhuǎn)換圖。DFA狀態(tài)：用圓圈節(jié)點(diǎn)表示；初始狀態(tài)節(jié)點(diǎn)：用“右向雙(單)箭頭”表示；終止?fàn)顟B(tài)節(jié)點(diǎn)：用“雙圈”表示；狀態(tài)變遷：用單向弧線表示，上面必須標(biāo)記激勵變遷的符號。11/6/202213練習(xí)q1q2q3000,1111101q1狀態(tài):M1有3個(gè)狀態(tài)q1,q2,q3起始狀態(tài)q1:用指向它的無出發(fā)點(diǎn)的箭頭標(biāo)示接受狀態(tài)q2:用雙圈標(biāo)示轉(zhuǎn)移:從一個(gè)狀態(tài)指向另一個(gè)狀態(tài)的箭頭.運(yùn)行:從起始狀態(tài)開始根據(jù)輸入和轉(zhuǎn)移箭頭進(jìn)行.輸出:輸入讀完處于接受狀態(tài)則接受,否則拒絕.被M1接受的串有什么特點(diǎn)？M111/6/202214練習(xí)設(shè)A是DFAM接受的全部字符串組成的集合,則稱A是DFAM的語言,記作L(M)=A.又稱M識別A.q1q2q3000,111M1注意:無論在哪個(gè)狀態(tài),讀到1后一定會進(jìn)入狀態(tài)q2.L(M1)={w|w是由0,1組成的字符串,至少含有一個(gè)1,

并且最后一個(gè)1后面含有偶數(shù)個(gè)0}11/6/202215有限自動機(jī)的設(shè)計(jì)(難點(diǎn))把自己當(dāng)作自動機(jī)需要記住的關(guān)鍵信息設(shè)計(jì)識別下列語言的DFA:{w{0,1}*:w含有子串001}11/6/202216課堂練習(xí)習(xí)題2.1.1設(shè)M是一臺確定型有窮自動機(jī)。恰好在什么情況下eL(M)?證明你的答案。11/6/2022172.2非確定型有窮自動機(jī)11/6/202218(ab∪aba)*11/6/2022192.2非確定型有窮自動機(jī)

11/6/2022202.2非確定型有窮自動機(jī)因?yàn)?KK是一個(gè)函數(shù),所以DFA在計(jì)算的每步以唯一的方式進(jìn)入下一個(gè)狀態(tài)所以有限自動機(jī)又稱為確定型有限自動機(jī)(DFA)現(xiàn)在來引入非確定型的有限自動機(jī)(NFA)q1q2q3q40,110,10,1NFA的特點(diǎn):一個(gè)輸入可對應(yīng)0至多個(gè)輸出轉(zhuǎn)移箭頭上的符號可以是空串11/6/2022212.2非確定型有窮自動機(jī)

11/6/2022222.2非確定型有窮自動機(jī)例2.2.1：圖2-7描述了一臺非確定性有窮自動機(jī)，接受含有模式bb或bab出現(xiàn)的所有字符串的集合。還有幾個(gè)非確定性有窮自動機(jī)也接受這個(gè)集合。11/6/2022232.2非確定型有窮自動機(jī)

11/6/202224當(dāng)輸入bababab時(shí)，會有幾個(gè)不同的序列，如使用（q0,a,q0）和（q0,b,q0）這個(gè)輸入串可以讓M從q0轉(zhuǎn)移到接受狀態(tài)q4,(三種方法)11/6/20222511/6/2022262.2非確定型有窮自動機(jī)

11/6/2022272.2非確定型有窮自動機(jī)

11/6/20222811/6/202229

11/6/2022302.2非確定型有窮自動機(jī)

11/6/202231NFA與DFA等價(jià)定理:每個(gè)NFA都有一臺等價(jià)的DFA.11/6/202232NFA的確定化:子集法對于一個(gè)NFA，由于狀態(tài)轉(zhuǎn)換函數(shù)是一個(gè)多值函數(shù)，因此總存在一些狀態(tài)q，對于它們有(q,a)={q1,q2,q3,…qn},它們是NFA狀態(tài)集合的一個(gè)子集，為了NFA轉(zhuǎn)化為DFA，把狀態(tài)集合{q1,q2,q3,…qn}看作一個(gè)狀態(tài)A，也就是說讓DFA的每一個(gè)狀態(tài)代表NFA狀態(tài)集合的某個(gè)子集，這個(gè)DFA使用它的狀態(tài)去記錄在NFA讀入輸入符號之后可能到達(dá)的所有狀態(tài)的集合，這樣就可以把NFA轉(zhuǎn)化為DFA了。這種構(gòu)造方法稱為子集法。11/6/202233NFA的確定化:子集法(1)首先將從NFAN的初態(tài)S出發(fā)經(jīng)過任意條ε弧所能到達(dá)的狀態(tài)組成的集合作為確定化后的DFAM的初態(tài)S′。

(2)從S′出發(fā)，經(jīng)過對任意輸入符號a∈∑的狀態(tài)轉(zhuǎn)移所能到達(dá)的狀態(tài)（包括讀入輸入符號a之后所有可能的ε轉(zhuǎn)移所能到達(dá)的狀態(tài)）所組成的集合作為M的新狀態(tài)。

（3）如此重復(fù)，直到不在有新的狀態(tài)出現(xiàn)為止。

（4）在所產(chǎn)生的狀態(tài)中，含有原NFA終態(tài)的子集作DFA的終態(tài)。11/6/202234NFA的確定化:子集法E(q):M從狀態(tài)q開始,不讀入任何輸入能夠到達(dá)的所有狀態(tài)的集合.特點(diǎn):1.E(q)非空.2.包括任意次的e動作到達(dá)的所有狀態(tài).11/6/20223511/6/20223611/6/20223711/6/202238練習(xí):P40圖2-6確定化11/6/20223911/6/2022402.3有窮自動機(jī)與正則表達(dá)式11/6/2022412.3有窮自動機(jī)與正則表達(dá)式定理2.3.2一個(gè)語言是正則的當(dāng)且僅當(dāng)它被有窮自動機(jī)接受.11/6/2022422.3有窮自動機(jī)與正則表達(dá)式練習(xí)畫出正則表達(dá)式

（a|b)*(aa|bb)(a|b)*對應(yīng)的NFA11/6/202243正則表達(dá)式到NFA的轉(zhuǎn)換（1）替換成（2）替換成（3）替換成11/6/202244NFA到正則表達(dá)式的轉(zhuǎn)換具體操作如下：首先，對NFAM進(jìn)行拓廣(廣義FA)，在M的狀態(tài)轉(zhuǎn)換圖中，新設(shè)置一個(gè)唯一的開始狀態(tài)S和唯一的終止?fàn)顟B(tài)Z，并允許狀態(tài)轉(zhuǎn)換圖中弧上可以為正規(guī)表達(dá)式。然后，從開始狀態(tài)S到原來所有的開始狀態(tài)連接弧，再從原來所有的終止?fàn)顟B(tài)到Z狀態(tài)也連接弧。修改后,構(gòu)成了一個(gè)新的NFA，它只有一個(gè)初態(tài)結(jié)點(diǎn)S和一個(gè)終態(tài)結(jié)點(diǎn)Z，這個(gè)新的NFAM′顯然和原NFAM等價(jià)。11/6/202245NFA到正則表達(dá)式的轉(zhuǎn)換（1）替換成（2）替換成（3）替換成11/6/202246NFA到正則表達(dá)式的轉(zhuǎn)換11/6/202247NFA到正則表達(dá)式的轉(zhuǎn)換11/6/202248練習(xí):P40圖2-6寫出正則表達(dá)式11/6/202249正則表達(dá)式的運(yùn)算性質(zhì)設(shè)e1、e2和e3都是上的正則表達(dá)式，則①e1e2=e2e1(交換律)②(e1e2)e3=e1(e2e3),(e1e2)e3=e1(e2e3)（結(jié)合律）③e1(e2e3)=e1e2e1e3,(e1e2)e3=e1e3e2e3（分配律）④e1=e1=e1⑤()*=(空集的閉包是空串)⑥e1=e1=

⑦e1*=e1|e1*⑧(e1*)*=e1