計算理論與算法分析設(shè)計-有窮自動機

CH2有窮自動機

2024/7/32

of1582.1確定型有窮自動機有窮狀態(tài)自動機(Finite-stateAutomation簡稱FA)是具有離散的輸入\輸出系統(tǒng)的數(shù)學模型。系統(tǒng)內(nèi)部具有有窮個狀態(tài)，系統(tǒng)的狀態(tài)概括了對過去輸入狀況的處理信息，系統(tǒng)只需根據(jù)當前所處的狀態(tài)和面臨的輸入就可以決定系統(tǒng)的后繼行為，系統(tǒng)處理了當前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生變化。電梯控制裝置、文本編輯程序、編譯技術(shù)中的詞法分析程序，計算機以及人腦都是有窮狀態(tài)系統(tǒng)。2024/7/33

of158輸入帶：有窮控制器：運行開始時，讀寫頭指向最左邊的字符，控制器處于開始指定的初始狀態(tài)根據(jù)最后的狀態(tài)表明是否接受被輸入的字符串2024/7/34

of158

1-91,3,5,7,92.1確定型有窮自動機104397TAS1,3,5,7,9輸入帶有窮控制器讀頭0-92024/7/35

of158定義2.1.1

一個確定有窮自動機DFA是一個五元組M=(K,

,δ,s,F)其中，K：是非空有窮狀態(tài)集,其中的每個元素稱為一個狀態(tài)；

：是有窮輸入字母表，它的每一個元素稱為一個輸入符號；δ

：是一個單值映射KK，也稱狀態(tài)轉(zhuǎn)換函數(shù)，δ(q,x)=q

意指：當現(xiàn)行狀態(tài)為q，面臨的輸入符號為x時，將轉(zhuǎn)到下一狀態(tài)q

，q

稱為q的一個后繼狀態(tài)；s

K稱之為開始狀態(tài)；FK稱為終止狀態(tài)集，至少由一個終止狀態(tài)組成。2024/7/36

of158

DFA轉(zhuǎn)換矩陣:

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

DFA轉(zhuǎn)換矩陣2024/7/37

of1582.1確定型有窮自動機

abab表2-12024/7/38

of1582.1確定型有窮自動機

abab2024/7/39

of1582.1確定型有窮自動機

2024/7/310

of1582.1確定型有窮自動機

2024/7/311

of1582.1確定型有窮自動機qabababab表2-22024/7/312

of1582.1確定型有窮自動機2024/7/313

of158狀態(tài)轉(zhuǎn)換圖一個DFA也可表示成一張狀態(tài)轉(zhuǎn)換圖。DFA狀態(tài)：用圓圈節(jié)點表示；初始狀態(tài)節(jié)點：用“右向雙(單)箭頭”表示；終止狀態(tài)節(jié)點：用“雙圈”表示；狀態(tài)變遷：用單向弧線表示，上面必須標記激勵變遷的符號。2024/7/314

of158練習q1q2q3000,1111101q1狀態(tài):M1有3個狀態(tài)q1,q2,q3起始狀態(tài)q1:用指向它的無出發(fā)點的箭頭標示接受狀態(tài)q2:用雙圈標示轉(zhuǎn)移:從一個狀態(tài)指向另一個狀態(tài)的箭頭.運行:從起始狀態(tài)開始根據(jù)輸入和轉(zhuǎn)移箭頭進行.輸出:輸入讀完處于接受狀態(tài)則接受,否則拒絕.被M1接受的串有什么特點？M12024/7/315

of158練習設(shè)A是DFAM接受的全部字符串組成的集合,則稱A是DFAM的語言,記作L(M)=A.又稱M識別A.q1q2q3000,111M1注意:無論在哪個狀態(tài),讀到1后一定會進入狀態(tài)q2.L(M1)={w|w是由0,1組成的字符串,至少含有一個1,

并且最后一個1后面含有偶數(shù)個0}2024/7/316

of158有限自動機的設(shè)計(難點)把自己當作自動機需要記住的關(guān)鍵信息設(shè)計識別下列語言的DFA:{w

{0,1}*:w含有子串001}2024/7/317

of158課堂練習習題2.1.1設(shè)M是一臺確定型有窮自動機。恰好在什么情況下e

L(M)?證明你的答案。2024/7/318

of1582.2非確定型有窮自動機2024/7/319

of158(ab∪aba)*2024/7/320

of1582.2非確定型有窮自動機

2024/7/321

of1582.2非確定型有窮自動機因為

:KK是一個函數(shù),所以DFA在計算的每步以唯一的方式進入下一個狀態(tài)所以有限自動機又稱為確定型有限自動機(DFA)現(xiàn)在來引入非確定型的有限自動機(NFA)q1q2q3q40,110,

10,1NFA的特點:一個輸入可對應(yīng)0至多個輸出轉(zhuǎn)移箭頭上的符號可以是空串

2024/7/322

of1582.2非確定型有窮自動機

2024/7/323

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

of1582.2非確定型有窮自動機

2024/7/325

of158當輸入bababab時，會有幾個不同的序列，如使用（q0,a,q0）和（q0,b,q0）這個輸入串可以讓M從q0轉(zhuǎn)移到接受狀態(tài)q4,(三種方法)2024/7/326

of1582024/7/327

of1582.2非確定型有窮自動機

2024/7/328

of1582.2非確定型有窮自動機

2024/7/329

of1582024/7/330

of158

2024/7/331

of1582.2非確定型有窮自動機

2024/7/332

of158NFA與DFA等價定理:每個NFA都有一臺等價的DFA.2024/7/333

of158NFA的確定化:子集法對于一個NFA，由于狀態(tài)轉(zhuǎn)換函數(shù)

是一個多值函數(shù)，因此總存在一些狀態(tài)q，對于它們有

(q,a)={q1,q2,q3,…qn},它們是NFA狀態(tài)集合的一個子集，為了NFA轉(zhuǎn)化為DFA，把狀態(tài)集合{q1,q2,q3,…qn}看作一個狀態(tài)A，也就是說讓DFA的每一個狀態(tài)代表NFA狀態(tài)集合的某個子集，這個DFA使用它的狀態(tài)去記錄在NFA讀入輸入符號之后可能到達的所有狀態(tài)的集合，這樣就可以把NFA轉(zhuǎn)化為DFA了。這種構(gòu)造方法稱為子集法。2024/7/334

of158NFA的確定化:子集法(1)首先將從NFAN的初態(tài)S出發(fā)經(jīng)過任意條ε弧所能到達的狀態(tài)組成的集合作為確定化后的DFAM的初態(tài)S′。

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

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

（4）在所產(chǎn)生的狀態(tài)中，含有原NFA終態(tài)的子集作DFA的終態(tài)。2024/7/335

of158NFA的確定化:子集法E(q):M從狀態(tài)q開始,不讀入任何輸入能夠到達的所有狀態(tài)的集合.特點:1.E(q)非空.2.包括任意次的e動作到達的所有狀態(tài).2024/7/336

of1582024/7/337

of1582024/7/338

of1582024/7/339

of158練習:P40圖2-6確定化2024/7/340

of1582024/7/341

of1582.3有窮自動機與正則表達式2024/7/342

of1582.3有窮自動機與正則表達式定理2.3.2一個語言是正則的當且僅當它被有窮自動機接受.2024/7/343

of1582.3有窮自動機與正則表達式練習畫出正則表達式

（a|b)*(aa|bb)(a|b)*對應(yīng)的NFA2024/7/344

of158正則表達式到NFA的轉(zhuǎn)換（1）替換成（2）替換成（3）替換成2024/7/345

of158NFA到正則表達式的轉(zhuǎn)換具體操作如下：首先，對NFAM進行拓廣(廣義FA)，在M的狀態(tài)轉(zhuǎn)換圖中，新設(shè)置一個唯一的開始狀態(tài)S和唯一的終止狀態(tài)Z，并允許狀態(tài)轉(zhuǎn)換圖中弧上可以為正規(guī)表達式。然后，從開始狀態(tài)S到原來所有的開始狀態(tài)連接

弧，再從原來所有的終止狀態(tài)到Z狀態(tài)也連接

弧。修改后,構(gòu)成了一個新的NFA，它只有一個初態(tài)結(jié)點S和一個終態(tài)結(jié)點Z，這個新的NFAM′顯然和原NFAM等價。2024/7/346

of158NFA到正則表達式的轉(zhuǎn)換（1）替換成（2）替換成（3）替換成2024/7/347

of158NFA到正則表達式的轉(zhuǎn)換2024/7/348

of158NFA到正則表達式的轉(zhuǎn)換2024/7/349

of158練習:P40圖2-6寫出正則表達式2024/7/350

of158正則表達式的運算性質(zhì)設(shè)e1、e2和e3都是

上的正則表達式，則

①e1

e2=e2

e1(交換律)②(e1e2)e3=e1(e2e3),(e1

e2)

e3=e1

(e2

e3)（結(jié)合律）

③e1(e2

e3)=e1e2

e1e3,(e1

e2)e3=e1e3

e2e3（分配律）

④

e1=e1

=e1⑤(

)*=

(空集的閉包是空串)⑥

e1=e1

=

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

⑨e1