從正則表達(dá)式到有限自動機(jī)

1、從正則表達(dá)式到有限自動機(jī)有限自動機(jī) 有 限 自 動 機(jī) .1 不確定的有限自動機(jī)簡稱NFA一個數(shù)學(xué)模型，它包括：1、有限的狀態(tài)集合S2、輸入符號集合3、轉(zhuǎn)換函數(shù)move : S ( ) P(S)4、狀態(tài)s0是唯一的開場狀態(tài)5、F S是承受狀態(tài)集合識別語言(a|b)*ab 的NFA12開始a0abb一個符號標(biāo)記離開同一狀態(tài)有多條邊輸 入 符 號ab00, 10122狀 態(tài) NFA的轉(zhuǎn)換表 有 限 自 動 機(jī) 識別語言(a|b)*ab 的NFA12開始a0abb.2 確定的有限自動機(jī)簡稱DFA) 一個數(shù)學(xué)模型，包括：1、有限的狀態(tài)集合S2、輸入字母集合3、轉(zhuǎn)換函數(shù)move : S S，且可以是局部

2、函數(shù)4、唯一的開場狀態(tài) s05、承受狀態(tài)集合F S12開始a0abbab識別語言(a|b)*ab 的DFA 有 限 自 動 機(jī) 一個符號標(biāo)記離開同一狀態(tài)只有一條邊 有 限 自 動 機(jī) 例 識別 (a | b)* a b 的DFADFANFANFA到DFA子集構(gòu)造法.3 NFA到DFA的變換 子集構(gòu)造法1、DFA的一個狀態(tài)是NFA的一個狀態(tài)集合2、讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，那么 DFA到達(dá)狀態(tài)s1, s2, , sk 12a開始 0abb00, 1aba0, 2b 有 限 自 動 機(jī) 未畫完 有 限 自 動 機(jī) .3 NFA到DFA的變換 子

3、集構(gòu)造法子集構(gòu)造法-closure(s) 從NFA的狀態(tài)S出發(fā)，只用轉(zhuǎn)換就能到達(dá)的狀態(tài)的集合-closure(T) 從NFA的狀態(tài)集合T中每個狀態(tài)出發(fā)，只用轉(zhuǎn)換就能到達(dá)的狀態(tài)的集合Move(T,a) 狀態(tài)集合T中每個狀態(tài)通過a能到達(dá)的所有狀態(tài)集合19開始0abab6782345子集構(gòu)造法找出U=-closure(T)對于U，以及任意符號a，找出U通過a能到達(dá)的集合V=Move(U,a) ，并計(jì)算V=-closure(V)U通過a到達(dá)的狀態(tài)即為V，U- a - V19開始0abab6782345 有 限 自 動 機(jī) .3 NFA到DFA的變換 子集構(gòu)造法：狀態(tài)轉(zhuǎn)換表的構(gòu)造 例 (a|b)*ab，

4、NFA如下，把它變換為DFA 有 限 自 動 機(jī) 19開始0abab6782345輸入符號ab狀態(tài) 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abA狀態(tài) A = 0, 1, 2, 4, 7 有 限 自 動 機(jī) 19開始0abab678234519開始0abab6782345輸入符號abAB狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 動 機(jī) 輸入符號abABB狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCB狀

5、態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBC狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBBC狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 動 機(jī) 19開始0abab6782345輸入

6、符號abABCBBDC狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBBDCD狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBBDCBCD狀態(tài) A = 0, 1, 2, 4, 7 B = 1,

7、 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBBDCBCDBC狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動 機(jī) 19開始0abab6782345輸入符號abABCBBDCBCDBC狀態(tài) BD開始aAabbabCba 有 限 自 動 機(jī) 19開始0abab678234519開始0abab678234

8、5BD開始aAabbabCba12開始a0abbab識別語言(a|b)*ab 的自動機(jī) 有 限 自 動 機(jī) 19開始0abab6782345BD開始aAabbabCba12開始a0abbab子集構(gòu)造法不一定得到最簡DFA 有 限 自 動 機(jī) 識別語言(a|b)*ab 的自動機(jī)DFA的化簡3.3.4 DFA的化簡構(gòu)造最簡DFA：構(gòu)造狀態(tài)集合的初始劃分 ：兩個子集承受狀態(tài)子集F和非承受狀態(tài)子集S F 有 限 自 動 機(jī) 3.3.4 DFA的化簡構(gòu)造最簡DFA：構(gòu)造狀態(tài)集合的初始劃分：兩個子集承受狀態(tài)子集F和非承受狀態(tài)子集S F應(yīng)用下面的過程構(gòu)造newFor 中的每個子集G ，do begin把G劃

9、分為假設(shè)干子集，G的兩個狀態(tài) s 和 t 在同一子集中，當(dāng)且僅當(dāng)對任意輸入符號 a ，s 和 t 的 a 轉(zhuǎn)換都到 的同一子集中在new 中，用G的劃分代替GEnd 有 限 自 動 機(jī) 3.3.4 DFA的化簡構(gòu)造最簡DFA：構(gòu)造狀態(tài)集合的初始劃分：兩個子集承受狀態(tài)子集F和非承受狀態(tài)子集S F應(yīng)用下面的過程構(gòu)造newFor 中的每個子集G ，do begin把G劃分為假設(shè)干子集，G的兩個狀態(tài) s 和 t 在同一子集中，當(dāng)且僅當(dāng)對任意輸入符號 a ，s 和 t 的 a 轉(zhuǎn)換都到 的同一子集中在new 中，用G的劃分代替GEnd如果new = ，那么final = ；否那么令 = new ，轉(zhuǎn)上步

10、 有 限 自 動 機(jī) 3.3.4 DFA的化簡構(gòu)造最簡DFA：構(gòu)造狀態(tài)集合的初始劃分：兩個子集承受狀態(tài)子集F和非承受狀態(tài)子集S F應(yīng)用下面的過程構(gòu)造newFor 中的每個子集G ，do begin把G劃分為假設(shè)干子集，G的兩個狀態(tài) s 和 t 在同一子集中，當(dāng)且僅當(dāng)對任意輸入符號 a ，s 和 t 的 a 轉(zhuǎn)換都到 的同一子集中在new 中，用G的劃分代替GEnd如果new = ，那么final = ；否那么令 = new ，轉(zhuǎn)上步在final的每個狀態(tài)子集中選一個狀態(tài)代表它，即為最簡DFA的狀態(tài) 有 限 自 動 機(jī) DFA的化簡把G劃分為假設(shè)干子集，G的兩個狀態(tài) s 和 t 在同一子集中，當(dāng)

11、且僅當(dāng)對任意輸入符號 a ，s 和 t 的 a 轉(zhuǎn)換都到同一子集中DFA的化簡構(gòu)造最簡的DFA承受狀態(tài)子集D,非承受狀態(tài)子集A,B,CA,B,C-A,C BBD開始aAabbabCba從正那么表達(dá)式到有限自動機(jī)從正那么式建立識別器的步驟從正那么式構(gòu)造NFA本節(jié)介紹用語法制導(dǎo)的算法，它用正那么式語法構(gòu)造來指導(dǎo)構(gòu)造過程把NFA變成DFA 子集構(gòu)造法，已介紹將DFA化簡 合并不可區(qū)別狀態(tài)，也已介紹3.4 從正那么式到有限自動機(jī)首先構(gòu)造識別和字母表中一個符號的NFA重要特點(diǎn)：僅一個承受狀態(tài)，它沒有向外的轉(zhuǎn)換i開始識別正則式的NFAafif開始識別正則式a的NFA3.4 從正那么式到有限自動機(jī)構(gòu)造識別主

12、算符為選擇的正那么式的NFA重要特點(diǎn)：僅一個承受狀態(tài)，它沒有向外的轉(zhuǎn)換 fi開始識別正則式s | t 的NFAN (s)N (t)3.4 從正那么式到有限自動機(jī)構(gòu)造識別主算符為連接的正那么式的NFA重要特點(diǎn)：僅一個承受狀態(tài)，它沒有向外的轉(zhuǎn)換識別正那么式 st 的NFAiN (s)f開始N (t)3.4 從正那么式到有限自動機(jī)構(gòu)造識別主算符為閉包的正那么式的NFA重要特點(diǎn)：僅一個承受狀態(tài)，它沒有向外的轉(zhuǎn)換N (s)f開始識別正則式 s* 的NFAi3.4 從正那么式到有限自動機(jī)對于加括號的正那么式(s)，使用N(s)本身作為它的NFA3.4 從正那么式到有限自動機(jī)本方法產(chǎn)生的NFA有以下性質(zhì)N(

13、r)的狀態(tài)數(shù)最多是r中符號和算符總數(shù)的兩倍N(r)只有一個承受狀態(tài)，承受狀態(tài)沒有向外的轉(zhuǎn)換3.4 從正那么式到有限自動機(jī)19開始0abab6782345本方法產(chǎn)生的NFA有以下性質(zhì)N(r)的每個狀態(tài)有一個用的符號標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個指向其它結(jié)點(diǎn)的轉(zhuǎn)換3.4 從正那么式到有限自動機(jī)19開始0abab67823453.4 從正那么式到有限自動機(jī) 19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 從正那么式到有限自動機(jī) 19開始0ab678ab2345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab

14、的分解3.4 從正那么式到有限自動機(jī) 19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 從正那么式到有限自動機(jī) 19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 從正那么式到有限自動機(jī) 19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 從正那么式到有限自動機(jī)19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解3.4 從正那么式到有限自動機(jī) 19開始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解 (a|b)*ab的兩個NFA的比較 12開始a 0abb手工構(gòu)造:算法構(gòu)造:3.4 從正那么式到有限自動機(jī)19開始0abab6782345重點(diǎn)從正那么式建立識別器的步驟從正那么式