第3章__自動(dòng)機(jī)基礎(chǔ)

1、第第3 3章章 自動(dòng)機(jī)基礎(chǔ)自動(dòng)機(jī)基礎(chǔ) 自動(dòng)機(jī)是一種語言模型，是語言的一種自動(dòng)機(jī)是一種語言模型，是語言的一種識(shí)別工具識(shí)別工具， 其中的其中的 有限自動(dòng)機(jī)有限自動(dòng)機(jī)(Finite Automata) FA 被用來處理被用來處理正規(guī)語言正規(guī)語言，后者是編譯程序設(shè)計(jì)中后者是編譯程序設(shè)計(jì)中詞法分詞法分 析析的對(duì)象。的對(duì)象。 3.1 正規(guī)語言正規(guī)語言及其描述方法及其描述方法 3.2 有限自動(dòng)機(jī)有限自動(dòng)機(jī)的定義與分類的定義與分類 3.3 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換等價(jià)轉(zhuǎn)換 3.4 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的實(shí)現(xiàn)實(shí)現(xiàn) 3.5 正規(guī)語言描述方法間的相互正規(guī)語言描述方法間的相互轉(zhuǎn)換轉(zhuǎn)換 3.1 正規(guī)語言及其描

2、述方法正規(guī)語言及其描述方法 【定義】【定義】 正規(guī)語言正規(guī)語言是指由是指由正規(guī)文法正規(guī)文法定義的語言；定義的語言； 程序設(shè)計(jì)語言中的程序設(shè)計(jì)語言中的單詞單詞，大都屬于此種語言。，大都屬于此種語言。 正規(guī)語言正規(guī)語言有三種等價(jià)的表示方法：有三種等價(jià)的表示方法： (1) 正規(guī)文法正規(guī)文法 (2) 正規(guī)式正規(guī)式 (3) 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 正規(guī)文法正規(guī)文法僅有三種形式的產(chǎn)生式：僅有三種形式的產(chǎn)生式： (1) A - aB (2) A - a (3) A - 【例【例3.1】 G(Z)：A -aA| A= ; A=aA=aaA=aaaA=an ,n0 L(G)= an | n0 正規(guī)文法正規(guī)文法 正

3、規(guī)語言正規(guī)語言 正規(guī)語言判定示例正規(guī)語言判定示例: : 【例【例3.2】 L1 = ambn| m0 ,n1 , 正規(guī)語言正規(guī)語言? 可由正規(guī)文法定義：可由正規(guī)文法定義： G1(S): S - aS|bA ; A - bA| L1 是正規(guī)語言。是正規(guī)語言。 【例【例3.3】 L2 =(ab)n| n1 , 正規(guī)語言正規(guī)語言 ? 可由正規(guī)文法定義：可由正規(guī)文法定義： G2(S): S - aA ; A - bB ; B - aA| L2 是正規(guī)語言。是正規(guī)語言。 【例【例3.4】 L3 =anbn| n0 , 正規(guī)語言正規(guī)語言 ? 不能由正規(guī)文法定義不能由正規(guī)文法定義(正規(guī)文法無法描述正規(guī)文法無

4、法描述a和和b數(shù)數(shù) 量上相等！量上相等！)： L3 不是正規(guī)語言！不是正規(guī)語言！ 3.1.1 正規(guī)語言的另外兩種表示方法 . 正規(guī)式表示法：正規(guī)式表示法： 正規(guī)式正規(guī)式是指由字母表中的符號(hào)，通過以下是指由字母表中的符號(hào)，通過以下 三種運(yùn)算三種運(yùn)算(也可以使用圓括號(hào)也可以使用圓括號(hào))連接起來構(gòu)成的表達(dá)連接起來構(gòu)成的表達(dá) 式式 e ： 閉包閉包( ( * *，+) +) 連接連接 ( .) ( .) 或或( | )( | ) 設(shè)設(shè) val(e),L(e) 分別表示正規(guī)式分別表示正規(guī)式 e 的的值值和和語言，語言， 則：則： L(e)= x| x=val(e) 即即 正規(guī)式表示的語言是該正規(guī)式所有值

5、的集合。正規(guī)式表示的語言是該正規(guī)式所有值的集合。 正規(guī)式正規(guī)式 L3= abnc, bn | n0 ， L2= (ab)n| n1 ，e2=(ab)+ e3= ab*c|b* L1= ambn| m0 ,n1 ，e1= a*b+ . 有限自動(dòng)機(jī)表示法：有限自動(dòng)機(jī)表示法： L3= abnc ,bn|n0 L2= (ab)n|n1 L1= ambn| m0 ,n1 + + b - - a b + + b - - a a + - a b c b b - - FA1: FA2: FA3: 初看起來，有限自動(dòng)機(jī)是帶標(biāo)記的有向圖！初看起來，有限自動(dòng)機(jī)是帶標(biāo)記的有向圖！ 3.1.1 正規(guī)語言的另外兩種表示方

6、法 1,2,3,4 狀態(tài)集狀態(tài)集; 其中：其中： +(開始狀態(tài)開始狀態(tài))； -(結(jié)束狀態(tài)結(jié)束狀態(tài)) a,b,c 字母表字母表； (1,a)=2 變換變換 ( 或或 ); (表示表示1狀態(tài)遇符號(hào)狀態(tài)遇符號(hào)a變到變到2狀態(tài)狀態(tài),)； 有限自動(dòng)機(jī)有限自動(dòng)機(jī)表示法說明：表示法說明： a L3= abnc ,bn|n0 + - a b c b b - - 一個(gè)一個(gè)FA，若存在一條從某開始狀態(tài)，若存在一條從某開始狀態(tài) i 到某結(jié)束狀態(tài)到某結(jié)束狀態(tài) j 的通路，且這條通路上所有邊的標(biāo)記連成的符號(hào)串的通路，且這條通路上所有邊的標(biāo)記連成的符號(hào)串 為為 ，則，則 就是一個(gè)句子；就是一個(gè)句子；所有這樣的所有這樣的

7、的集合，就是的集合，就是 該該 FA 表示的語言表示的語言。 【圖符說明】：【圖符說明】： 【運(yùn)行機(jī)制】：【運(yùn)行機(jī)制】： FA: e = ab*c|b* G(S): S- aA|bB| ，A - bA|c ，B - bB| 正規(guī)語言的三種表示法綜合示例：正規(guī)語言的三種表示法綜合示例： 【例【例3.5】 L = abnc, bn| n0 ,= a,b,c； 【注】凡是能由上述三種方法中的一種表示的語言， 一定是正規(guī)語言；反之，凡是不能由上述三種方法表示 的語言，一定不是正規(guī)語言。 1. 正規(guī)文法描述：正規(guī)文法描述： 2. 正規(guī)式描述正規(guī)式描述: 3. 有限自動(dòng)機(jī)描述：有限自動(dòng)機(jī)描述： + - a

8、 b c b b - - 3.2.1 有限自動(dòng)機(jī)的定義 狀態(tài)狀態(tài) i 遇符號(hào)遇符號(hào) a 時(shí)時(shí)變換為狀態(tài)變換為狀態(tài) j 3.2 有限自動(dòng)機(jī)的定義和分類有限自動(dòng)機(jī)的定義和分類 變換變換(二元函數(shù)二元函數(shù)) ; Q(有限狀態(tài)集有限狀態(tài)集) ; i ij j a a 或或 【定義】【定義】 有限自動(dòng)機(jī)是一種數(shù)學(xué)模型，用于描述有限自動(dòng)機(jī)是一種數(shù)學(xué)模型，用于描述 正規(guī)語言正規(guī)語言, ,可定義為五元組：可定義為五元組： FA=( Q , , S , F , ) (i , a)= j 其中：其中： i , jQ, a+ ; F(結(jié)束狀態(tài)集結(jié)束狀態(tài)集, F Q) ; S(開始狀態(tài)集開始狀態(tài)集, S Q) ; (

9、字母表字母表) ; 即：即： L(FA)= x| i j , x* ,iS,jF FA 存在一條從某初始狀態(tài)存在一條從某初始狀態(tài) i 到某結(jié)束狀態(tài)到某結(jié)束狀態(tài) j 的的連連 續(xù)變換續(xù)變換，且，且每次變換每次變換(=)的邊標(biāo)記連成的符號(hào)串恰好的邊標(biāo)記連成的符號(hào)串恰好 為為 x ；稱稱x為為FA接受，否則拒絕接受，否則拒絕。 令令L(FA)為自動(dòng)機(jī)為自動(dòng)機(jī)FA所描述的正規(guī)語言；則所描述的正規(guī)語言；則 則則 L(FA)的生成的生成 (或識(shí)別或識(shí)別)過程如下過程如下 所示：所示： 如右圖有限自動(dòng)機(jī)：如右圖有限自動(dòng)機(jī)： 3.2.2 有限自動(dòng)機(jī)所描述的語言有限自動(dòng)機(jī)所描述的語言 = x x + - a b

10、 c b b - - 設(shè)設(shè) x=a1 a2an ， ai+ a a1 1 =i1i a a2 2 =i2 a an n =j 則有則有 即：即： 含義是含義是: : L(FA)的生成的生成(或識(shí)別或識(shí)別)過程示例：過程示例： + - a b c b b - - .第一條通路：第一條通路：FA1 = b b + + + + = a a = b b = c c + + = a a = b b = b b = c c .第二條通路：第二條通路：FA2 + + = = a a = c c + + = b b = b b + + L(FA)=abnc, bn| n0 L(FA1)= abnc| n0 L

11、(FA2)= bn| n0 因而因而 接受空串的接受空串的 FA的典型特征！的典型特征！ 【例【例3.6】有限自動(dòng)機(jī)】有限自動(dòng)機(jī) ：FA=( Q,S,F, ) 其中其中: Q=1,2,3,4,=a,b,c, S=1,2, F=3,4 FA 的兩種表現(xiàn)形式：的兩種表現(xiàn)形式： 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖: : 3.2.3 有限自動(dòng)機(jī)的兩種表現(xiàn)形式有限自動(dòng)機(jī)的兩種表現(xiàn)形式 ：(1,a)=2; (1,b)=4;(2,b)=2; (2,c)=3; (2, )=3; (4,b)=4; 變換表變換表: : 變換表結(jié)構(gòu)變換表結(jié)構(gòu)：行行(狀態(tài)狀態(tài))，列列(符號(hào)符號(hào))，表項(xiàng)表項(xiàng)(變換后狀態(tài)變換后狀態(tài)) + - a b

12、c b bb b - + + 4 3 3 2 4 2 1 2 3 4 a bc + + - - - - + + 開始狀態(tài)開始狀態(tài) 結(jié)束狀態(tài)結(jié)束狀態(tài) 【例【例3.7】A= abnc,(ab)n|n0 二二: 變換函數(shù)不單值變換函數(shù)不單值(如如 一一: 開始狀態(tài)不唯一開始狀態(tài)不唯一,不好用不好用! (1,a)=(2|4),也不好用！也不好用！ 3.2.4 有限自動(dòng)機(jī)的分類有限自動(dòng)機(jī)的分類 方法一方法一：聯(lián)合式聯(lián)合式 方法二方法二：組合式組合式1 1 方法三方法三：組合式組合式2 2 + a b b c - + a b b- 比較之：比較之： + a b b c - a b b - 的有限自動(dòng)機(jī)構(gòu)造

13、：的有限自動(dòng)機(jī)構(gòu)造： 三三: 帶有帶有 邊，還是不好用邊，還是不好用! 有好用的嗎有好用的嗎?!?! ？ + a b b c - a a b b - 【例【例3.73.7】構(gòu)造正規(guī)語言】構(gòu)造正規(guī)語言 + a b b c - a a b b a a - - 3.2.4 有限自動(dòng)機(jī)的分類有限自動(dòng)機(jī)的分類 【有限自動(dòng)機(jī)分類】【有限自動(dòng)機(jī)分類】 1. 確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī)(DFA) 特征特征：開始狀態(tài)唯一開始狀態(tài)唯一; 變換函數(shù)單值變換函數(shù)單值; 不帶不帶 邊。邊。 2. 非確定的有限自動(dòng)機(jī)非確定的有限自動(dòng)機(jī)(NFA) (1) 帶有帶有 邊的邊的非確定的有限非確定的有限自動(dòng)機(jī)自動(dòng)機(jī)( NF

14、A) (2) 不帶有不帶有 邊的邊的非確定的有限非確定的有限自動(dòng)機(jī)自動(dòng)機(jī)( NFA) - 不能全部滿足上述特征者！不能全部滿足上述特征者！ 確定的有限自確定的有限自 動(dòng)機(jī)如右圖所示：動(dòng)機(jī)如右圖所示： +a b b - b c b - a a - c c DFA: A= abnc,(ab)n|n0 3.3 有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換等價(jià)轉(zhuǎn)換, ,主要包含兩個(gè)內(nèi)容：主要包含兩個(gè)內(nèi)容： (1) 有限自動(dòng)機(jī)的確定化有限自動(dòng)機(jī)的確定化( NFA=DFA); (2) 有限自動(dòng)機(jī)的最小化有限自動(dòng)機(jī)的最小化( DFA=最小的最小的DFA); 非確定機(jī)非確定機(jī)(N

15、FA) 較易構(gòu)造較易構(gòu)造，但不好用！但不好用！ 確定機(jī)確定機(jī) (DFA) 較難構(gòu)造，但好用！較難構(gòu)造，但好用！ 任何一非確定機(jī)任何一非確定機(jī)NFA，皆可通過有效算，皆可通過有效算 法把其轉(zhuǎn)化為等價(jià)的確定機(jī)法把其轉(zhuǎn)化為等價(jià)的確定機(jī)DFA（二者描（二者描 述的語言相同）。述的語言相同）。 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的最小化最小化, ,又稱有限自動(dòng)機(jī)的又稱有限自動(dòng)機(jī)的化簡化簡；是；是 指：指： 對(duì)給定的確定機(jī)對(duì)給定的確定機(jī)DFA1,構(gòu)造另一個(gè)確定機(jī)構(gòu)造另一個(gè)確定機(jī)DFA2, 使得使得 L(DFA1)=L(DFA2),且且DFA2的狀態(tài)最少。的狀態(tài)最少。 ab* , b+ , L(FA2)=abn,bn|

16、n0 【定義【定義1】設(shè)有兩個(gè)有限自動(dòng)機(jī)】設(shè)有兩個(gè)有限自動(dòng)機(jī)FA1和和FA2，若，若 L(FA1)= L(FA2)則稱則稱FA1與與FA2等價(jià)，記作等價(jià)，記作FA1 FA2。 3.3.1 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的等價(jià)等價(jià) . 兩個(gè)自動(dòng)機(jī)的等價(jià)：兩個(gè)自動(dòng)機(jī)的等價(jià)： + ab b - b b FA2 FA1 L(FA1)=L(FA2) + + ab b - b b b b - FA1 FA2 四條四條通路，分別接受：通路，分別接受： ab+ , ab* , b+ , L(FA1)=abn,bn|n0 二條二條通路，分別接受：通路，分別接受： . . 兩個(gè)狀態(tài)的等價(jià)：兩個(gè)狀態(tài)的等價(jià)： 【定義【定義2

17、】設(shè)】設(shè) i 和和 j 為為FA的兩個(gè)狀態(tài)，若把其的兩個(gè)狀態(tài)，若把其看作初看作初 態(tài)態(tài)，二者接受的符號(hào)串集合相同，則有，二者接受的符號(hào)串集合相同，則有 i j (等價(jià)等價(jià))。 3.3.1 有限自動(dòng)機(jī)的有限自動(dòng)機(jī)的等價(jià)等價(jià) 【例【例2】 FA2 + a b b c - 【例【例1】 FA1: + a b b c - 【注】如何判斷兩個(gè)狀態(tài)的等價(jià)性？稍后再討論。【注】如何判斷兩個(gè)狀態(tài)的等價(jià)性？稍后再討論。 2 4 ？ 3 5 ？4 5 ？ 判斷等價(jià)性：判斷等價(jià)性： 2 3 ？ 2,3節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)構(gòu)成 閉路閉路 2,3等價(jià)等價(jià)；可；可合而為一合而為一 a - b b a a - a a (3) 對(duì)對(duì)

18、 邊，按邊，按 通路通路逆向逆向逐一進(jìn)行：逐一進(jìn)行： 3.3.2 有限自動(dòng)機(jī)的確定化算法有限自動(dòng)機(jī)的確定化算法 . 消除消除 邊算法邊算法( NFA = 或或DFA ): NFA NFA (1) 若存在若存在 閉路，閉路， 則把則把 閉路上各節(jié)閉路上各節(jié) 點(diǎn)點(diǎn)合而為一：合而為一： a b b c - a b b c - (2) 標(biāo)記標(biāo)記隱含的隱含的開始態(tài)開始態(tài)和和結(jié)束態(tài)：結(jié)束態(tài)： 開始態(tài)的開始態(tài)的 通路通路上的節(jié)點(diǎn)：上的節(jié)點(diǎn)：+ + 結(jié)束態(tài)結(jié)束態(tài)逆向逆向 通路通路上節(jié)點(diǎn)：上節(jié)點(diǎn)：- - 刪除一個(gè)刪除一個(gè) 邊；同時(shí)邊；同時(shí) 引進(jìn)引進(jìn)新邊新邊 ： 凡由凡由原原 邊終點(diǎn)邊終點(diǎn)發(fā)出的邊，也要由發(fā)出的邊

19、，也要由其始點(diǎn)其始點(diǎn)發(fā)出。發(fā)出。 (4) 重復(fù)步驟重復(fù)步驟(3)，直到再無，直到再無 邊邊為止。為止。 + c c b b - b b + + + +- - a b b b b c c c c am,ambcn, amcn|m0,n1 L( )=L( )= NFA NFA (2) 標(biāo)記標(biāo)記隱含的隱含的開始態(tài)開始態(tài)和和 結(jié)束態(tài)結(jié)束態(tài)： L( NFA)= ? 消除消除 邊算法示例：邊算法示例： 【例【例3.8】考查】考查 NFA： + a b b c c - (1) 閉路上的節(jié)點(diǎn)閉路上的節(jié)點(diǎn)等價(jià)等價(jià)（ ）, ,可可合而為一；合而為一； (3) 逆序逐一逆序逐一刪除刪除 邊，邊， 同時(shí)同時(shí)引進(jìn)引進(jìn)新

20、邊：新邊： a b b c c - + + - + + a b b c c - + + c c - + + a b b c c -+ + c cc c - + + NFA NFA + + + + + - - + + ， + + ， 3.3.2 有限自動(dòng)機(jī)的確定化算法有限自動(dòng)機(jī)的確定化算法(續(xù)續(xù)1) .把把 化為化為DFADFA算法算法( ( =DFA ) ): : NFA NFA NFA NFA (2) 按按 的變換函數(shù)實(shí)施變換：的變換函數(shù)實(shí)施變換： NFA NFA (qi1,qin ,ak)= (qi1, ak) (qin, ak)=qj1,qjn (3) 若若qj1,qjn 未作為未作為狀

21、態(tài)行狀態(tài)行標(biāo)記，則作新行標(biāo)記；標(biāo)記，則作新行標(biāo)記； a1a2a3 q01,q0n (4) 重復(fù)步驟重復(fù)步驟(2)(3)，直到不再出現(xiàn)新狀態(tài)集為止；，直到不再出現(xiàn)新狀態(tài)集為止； (5) 標(biāo)記標(biāo)記DFA的的開始態(tài)開始態(tài)和和結(jié)束態(tài)結(jié)束態(tài)： 第一行第一行q01,q0n，(右側(cè)右側(cè))標(biāo)記標(biāo)記 + ； 凡是凡是狀態(tài)行狀態(tài)行中含有中含有 的的結(jié)束狀態(tài)結(jié)束狀態(tài)者，者，(右側(cè)右側(cè))標(biāo)記標(biāo)記 - 【注】【注】必要時(shí)，新產(chǎn)生的必要時(shí)，新產(chǎn)生的DFA可用狀態(tài)圖表示。可用狀態(tài)圖表示。 NFA NFA 字母表中符號(hào)字母表中符號(hào) 開始態(tài)集開始態(tài)集 NFA NFA (1) 構(gòu)造構(gòu)造DFA的變換表的變換表(框架框架)： 確定化

22、示例：確定化示例： NFA + a b c - + a b- 【例【例3.9】聯(lián)合】聯(lián)合 式自動(dòng)機(jī)式自動(dòng)機(jī)NFA: 確定化過程確定化過程: DFA: cb a D3F2E5C2,4 G4E5 D3F2F2 E5G4 D3 D3C2,4B2,5 B2,5 + - - - - AB C E F G D+ - ac b a b c c - b b a - - 【注】【注】A,B,C, 狀態(tài)集的代碼狀態(tài)集的代碼 A1,4 NFA確定化練習(xí)確定化練習(xí) 1. 消除消除 邊練習(xí)邊練習(xí) 2. 確定化練習(xí)確定化練習(xí) NFA NFA 1. 消除消除 邊練習(xí)的邊練習(xí)的答案答案 2. 確定化練習(xí)的確定化練習(xí)的答案答案

23、 NFA NFA NFA確定化練習(xí)確定化練習(xí) 01 12 23 33 4,5,6 4,5,6 3 7 73 3.3.3 有限自動(dòng)機(jī)的最小化算法有限自動(dòng)機(jī)的最小化算法 最小有限自動(dòng)機(jī)，是指滿足下述條件的確定最小有限自動(dòng)機(jī)，是指滿足下述條件的確定 有限自動(dòng)機(jī)：有限自動(dòng)機(jī)： (1) 沒有無用狀態(tài)沒有無用狀態(tài)(無用狀態(tài)已刪除無用狀態(tài)已刪除)； (2) 沒有等價(jià)狀態(tài)沒有等價(jià)狀態(tài)(等價(jià)狀態(tài)已合并等價(jià)狀態(tài)已合并)。 .刪除無用狀態(tài)算法刪除無用狀態(tài)算法 【定義】【定義】無用狀態(tài)無用狀態(tài)是指自動(dòng)機(jī)從開始態(tài)出發(fā)，對(duì)是指自動(dòng)機(jī)從開始態(tài)出發(fā)，對(duì) 任何符號(hào)串都不能到達(dá)的狀態(tài)。任何符號(hào)串都不能到達(dá)的狀態(tài)。 【判別算法】【

24、判別算法】 構(gòu)造有用狀態(tài)集構(gòu)造有用狀態(tài)集 Qus (1) 設(shè)設(shè) q0 為開始態(tài)，則為開始態(tài)，則 令令 q0Qus ； (2) 若若 qiQus 且有且有 (qi,a)= qj 則令則令 qjQus ； (3) 重復(fù)執(zhí)行重復(fù)執(zhí)行(2)，直到，直到Qus不再增大為止。不再增大為止。 (4) 從狀態(tài)集從狀態(tài)集Q中，刪除不在中，刪除不在Qus中的所有狀態(tài)。中的所有狀態(tài)。 3.3.3 有限自動(dòng)機(jī)的最小化算法有限自動(dòng)機(jī)的最小化算法(續(xù)續(xù)1) . . 合并等價(jià)狀態(tài)算法合并等價(jià)狀態(tài)算法 【原理】兩個(gè)狀態(tài)【原理】兩個(gè)狀態(tài)i , j 等價(jià)，當(dāng)且僅當(dāng)滿足下面兩等價(jià)，當(dāng)且僅當(dāng)滿足下面兩 個(gè)條件：個(gè)條件： 必須必須同是

25、同是結(jié)束態(tài)結(jié)束態(tài)，或，或同不是同不是結(jié)束態(tài)結(jié)束態(tài)； 對(duì)對(duì)所有所有字母表上符號(hào)，狀態(tài)字母表上符號(hào)，狀態(tài) i , j 必變必變 換到等價(jià)狀態(tài)。換到等價(jià)狀態(tài)。 【例】把下述自動(dòng)機(jī)最小化：【例】把下述自動(dòng)機(jī)最小化： (1) 初分成兩個(gè)不等價(jià)子集：初分成兩個(gè)不等價(jià)子集： Q1=1,2,Q2=3 (2) 還能分成不等價(jià)子集嗎？還能分成不等價(jià)子集嗎？ (1,a)= 2 , (2,a)= 2 又又 (1,b)= 3 , (2,b)= 3 + +- - - - b b a a b b a a a a 12(等價(jià)等價(jià)) 合并后的最合并后的最 小自動(dòng)機(jī)小自動(dòng)機(jī) + + - - a a b b a a 3.3.3 有

26、限自動(dòng)機(jī)的最小化算法有限自動(dòng)機(jī)的最小化算法(續(xù)續(xù)2) . . 合并等價(jià)狀態(tài)算法合并等價(jià)狀態(tài)算法 (1) 初始，把狀態(tài)集初始，把狀態(tài)集Q劃分成兩個(gè)不等價(jià)子集劃分成兩個(gè)不等價(jià)子集: Q1(結(jié)束狀態(tài)集結(jié)束狀態(tài)集)， Q2(非結(jié)束狀態(tài)集非結(jié)束狀態(tài)集)； (2) 把每個(gè)把每個(gè)Qi再劃分成不同的子集，條件是：再劃分成不同的子集，條件是： 對(duì)同一對(duì)同一Qi中兩個(gè)狀態(tài)中兩個(gè)狀態(tài) i 和和 j ，若對(duì)字母表中，若對(duì)字母表中 的的某個(gè)某個(gè)符號(hào)，變換到符號(hào)，變換到已劃分已劃分的不同的狀態(tài)集中，的不同的狀態(tài)集中， 則則 i 和和 j 應(yīng)分離應(yīng)分離: (3) 重復(fù)步驟重復(fù)步驟(2)，直到再不能劃分為止；，直到再不能劃分

27、為止； (4) 合并最終劃分的每個(gè)子集中的各狀態(tài)合并最終劃分的每個(gè)子集中的各狀態(tài)(合而為一合而為一)。 如如 (i,a)Qm , (j,a)Qn 且且 mn - - 劃分不等價(jià)狀態(tài)集劃分不等價(jià)狀態(tài)集 有限自動(dòng)機(jī)化簡示例有限自動(dòng)機(jī)化簡示例 【例【例3.10】 化簡下述化簡下述 DFA: (1) 刪除無用狀態(tài)：刪除無用狀態(tài)： 動(dòng)態(tài)構(gòu)造動(dòng)態(tài)構(gòu)造DFA變換表變換表，即從開始狀態(tài)，即從開始狀態(tài) 1 出發(fā)，出發(fā)， 把變換后的狀態(tài)填入表項(xiàng)，并同時(shí)作為新行標(biāo)記；把變換后的狀態(tài)填入表項(xiàng)，并同時(shí)作為新行標(biāo)記； 如此下去，直到再不出現(xiàn)新狀態(tài)為止。未出現(xiàn)的狀如此下去，直到再不出現(xiàn)新狀態(tài)為止。未出現(xiàn)的狀 態(tài)，就是無用的

28、狀態(tài)。態(tài)，就是無用的狀態(tài)。 【注】【注】 DFA 中的狀態(tài)中的狀態(tài) 2，8 被刪除被刪除! 46 47 375 644 513 361 ba + - - - + - - - ba b a b a b a b a a ab a DFA的變換表：的變換表： 有限自動(dòng)機(jī)化簡示例有限自動(dòng)機(jī)化簡示例( (續(xù)續(xù)1) 1) 46 47 375 644 513 361 ba + - - - DFA: (2) 合并等價(jià)狀態(tài)合并等價(jià)狀態(tài): 令令 QNE= 1,3,4, 5,6,7 取取 1,3,4 ： 即即 QNE= 1,3,4, 5,6,7 取取 3,4： (3,a)=1 , (4,a)=4 劃分劃分 Q1=3

29、, Q2=4 即即 QNE= 1,3,4, 5,6,7 取取 5,6,7: 同理，可劃分成同理，可劃分成 Q1=5, Q2=6,7； 最后：最后： QNE= 1,3,4, 5,6,7 不等價(jià)集不等價(jià)集 (1,a)=6 , (3,4,a)=1,4 劃分成劃分成 Q1=1, Q2=3,4 有限自動(dòng)機(jī)化簡示例有限自動(dòng)機(jī)化簡示例(續(xù)續(xù)2) 46 47 375 644 513 3 6 1 ba + - - - DFA: 合并等價(jià)狀態(tài)合并等價(jià)狀態(tài): 6 , 7 46 365 644 513 3 6 1 ba + - - + - - b a b b a b aa a 6替換替換7 最小的最小的 DFA !

30、有限自動(dòng)機(jī)化簡練習(xí)有限自動(dòng)機(jī)化簡練習(xí) 刪除無刪除無 用狀態(tài)用狀態(tài) 合并等合并等 價(jià)狀態(tài)價(jià)狀態(tài) (3) 令令 getchar(ch) 為讀符號(hào)函數(shù)。為讀符號(hào)函數(shù)。 3.4 有限自動(dòng)機(jī)的實(shí)現(xiàn)有限自動(dòng)機(jī)的實(shí)現(xiàn) 用計(jì)算機(jī)完成有限自動(dòng)機(jī)的功能，其核心是用計(jì)算機(jī)完成有限自動(dòng)機(jī)的功能，其核心是 “變換變換”的實(shí)現(xiàn)技術(shù)。這里介紹的是把的實(shí)現(xiàn)技術(shù)。這里介紹的是把變換表變換表按某按某 種方式存儲(chǔ)起來，作為知識(shí)源來識(shí)別單詞，實(shí)現(xiàn)機(jī)種方式存儲(chǔ)起來，作為知識(shí)源來識(shí)別單詞，實(shí)現(xiàn)機(jī) 制是：制是： 控制程序控制程序 變換表變換表 + 【三點(diǎn)說明】【三點(diǎn)說明】 (1) 假定自動(dòng)機(jī)只作為假定自動(dòng)機(jī)只作為識(shí)別器識(shí)別器，即，即對(duì)對(duì)待

31、識(shí)別的待識(shí)別的符號(hào)串符號(hào)串： 僅回答僅回答 是是(接受接受) 或或 否否(拒絕拒絕)。 (2) 為便于處理，可令為便于處理，可令 # 作為作為待識(shí)別的待識(shí)別的符號(hào)串符號(hào)串的的后繼符后繼符。 為此，擴(kuò)展自動(dòng)機(jī)如下：為此，擴(kuò)展自動(dòng)機(jī)如下： + - a - b - # # ok 4 ok 5 6 3 1 # b a + - - 空則空則no 3.4.1 控制程序設(shè)計(jì)控制程序設(shè)計(jì) 開始開始 結(jié)束結(jié)束 state = 1 getchar(ch) 查變換表：查變換表： (state,ch)= ? =空空 =ok 回答回答:yes 回答回答:no y n y state = n 開始狀態(tài)開始狀態(tài)1賦給賦給

32、變量變量 state 從輸入串中讀取一從輸入串中讀取一 符號(hào)到變量符號(hào)到變量 ch 變量變量 state 重新重新 被賦值為變換后被賦值為變換后 的狀態(tài)！的狀態(tài)！ n 3.4.2 變換表存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)變換表存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 變換表的存儲(chǔ)結(jié)構(gòu)可選擇下述兩種方式之一：變換表的存儲(chǔ)結(jié)構(gòu)可選擇下述兩種方式之一： (1) 二維數(shù)組二維數(shù)組 ，其下標(biāo)是其下標(biāo)是(狀態(tài)，輸入符號(hào)狀態(tài)，輸入符號(hào))； 為了適應(yīng)不同編碼語言的需要，狀態(tài)和輸入為了適應(yīng)不同編碼語言的需要，狀態(tài)和輸入 符號(hào)可采取相應(yīng)的符號(hào)可采取相應(yīng)的編碼形式編碼形式；通常，使用連續(xù)通常，使用連續(xù) 的正整數(shù)：的正整數(shù)：0,1,2,3,。 (2) 壓縮變換表壓縮

33、變換表，方法是把每個(gè)狀態(tài)行作為，方法是把每個(gè)狀態(tài)行作為子表，狀態(tài)子表，狀態(tài) 為索引，為索引，并把并把錯(cuò)誤的輸入符號(hào)合并在一起，如：錯(cuò)誤的輸入符號(hào)合并在一起，如： no b a no f e no y x 索引表索引表 (其他其他)-錯(cuò)誤符號(hào)。錯(cuò)誤符號(hào)。 狀狀 態(tài)態(tài) 變換子表變換子表 有限自動(dòng)機(jī)實(shí)現(xiàn)示例有限自動(dòng)機(jī)實(shí)現(xiàn)示例 【例【例3.11】 有限自動(dòng)機(jī)有限自動(dòng)機(jī)DFA: + a b - # a b c d no b a no d no c b a no ok# 壓縮變換表壓縮變換表 輸入串輸入串 aacd# 識(shí)別過程：識(shí)別過程： 備注變換剩余chstate 3acd#a1 接受ok#4 4#d2

34、 2d#c3 3cd#a3 索引表索引表 3.5 正規(guī)語言描述方法間的相互轉(zhuǎn)換正規(guī)語言描述方法間的相互轉(zhuǎn)換 正規(guī)語言正規(guī)語言有三種等價(jià)的表示方法：有三種等價(jià)的表示方法： (1) 正規(guī)文法正規(guī)文法 (2) 正規(guī)式正規(guī)式 (3) 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 我們以我們以有限自動(dòng)機(jī)有限自動(dòng)機(jī)為核心，介紹彼此間的轉(zhuǎn)換關(guān)系：為核心，介紹彼此間的轉(zhuǎn)換關(guān)系： . 正規(guī)文法正規(guī)文法 DFA 設(shè)設(shè) G(Z)=(VN,VT,Z,P), DFA=(Q,S,F, ) 則有：則有： VT (A,a)=BA - aB (A,a)=B(結(jié)束態(tài))A - a S(開始態(tài))Z(開始符號(hào)) Q VN DFA正規(guī)文法 A - A(結(jié)束態(tài)) 有時(shí)需要增加一個(gè)結(jié)束狀態(tài)有時(shí)需要增