第3章__自動機基礎(chǔ)

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

2、描述方法 【定義】【定義】 正規(guī)語言正規(guī)語言是指由是指由正規(guī)文法正規(guī)文法定義的語言；定義的語言；程序設(shè)計語言中的程序設(shè)計語言中的單詞單詞，大都屬于此種語言。，大都屬于此種語言。正規(guī)語言正規(guī)語言有三種等價的表示方法：有三種等價的表示方法： (1) 正規(guī)文法正規(guī)文法 (2) 正規(guī)式正規(guī)式 (3) 有限自動機有限自動機正規(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ī)文法正規(guī)語言正規(guī)語言 正規(guī)語言判

3、定示例正規(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ī)文法無法描述a和和b數(shù)數(shù)量上相等！

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

5、的集合。正規(guī)式正規(guī)式 L3= abnc, bn | n0 ， L2= (ab)n| n1 ，e2=(ab)+e3= ab*c|b* L1= ambn| m0 ,n1 ，e1= a*b+. 有限自動機表示法：有限自動機表示法： L3= abnc ,bn|n0 L2= (ab)n|n1 L1= ambn| m0 ,n1 + + b- -ab+ + b- -aa+-abcbb-FA1:FA2:FA3: 初看起來，有限自動機是帶標(biāo)記的有向圖！初看起來，有限自動機是帶標(biāo)記的有向圖！3.1.1 正規(guī)語言的另外兩種表示方法 1,2,3,4 狀態(tài)集狀態(tài)集; 其中：其中： +(開始狀態(tài)開始狀態(tài))； -(結(jié)束狀態(tài)

6、結(jié)束狀態(tài)) a,b,c 字母表字母表； (1,a)=2 變換變換 ( 或或 );(表示表示1狀態(tài)遇符號狀態(tài)遇符號a變到變到2狀態(tài)狀態(tài),)；有限自動機有限自動機表示法說明：表示法說明： aL3= abnc ,bn|n0 +-abcbb- 一個一個FA，若存在一條從某開始狀態(tài)，若存在一條從某開始狀態(tài) i 到某結(jié)束狀態(tài)到某結(jié)束狀態(tài) j 的通路，且這條通路上所有邊的標(biāo)記連成的符號串的通路，且這條通路上所有邊的標(biāo)記連成的符號串為為 ，則，則 就是一個句子；就是一個句子；所有這樣的所有這樣的 的集合，就是的集合，就是該該 FA 表示的語言表示的語言。【圖符說明】：【圖符說明】：【運行機制】：【運行機制】：

7、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. 有限自動機描述：有限自動機描述：+-abcbb- 3.2.1 有限自動機的定義狀態(tài)狀態(tài) i 遇符號遇符號 a 時時變換為狀態(tài)變換為狀態(tài) j 3.2 有限自動機的定義和分類有限自動

8、機的定義和分類 變換變換(二元函數(shù)二元函數(shù)) ;Q(有限狀態(tài)集有限狀態(tài)集) ; i ij ja a或或【定義】【定義】 有限自動機是一種數(shù)學(xué)模型，用于描述有限自動機是一種數(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) ; (字母表字母表) ;即：即：L(FA)= x| i j , x* ,iS,jF FA 存在一條從某初始狀態(tài)存在一條從某初始狀態(tài) i 到某結(jié)束狀態(tài)到某結(jié)束狀態(tài) j 的的連連 續(xù)變

9、換續(xù)變換，且，且每次變換每次變換(=)的邊標(biāo)記連成的符號串恰好的邊標(biāo)記連成的符號串恰好為為 x ；稱稱x為為FA接受，否則拒絕接受，否則拒絕。 令令L(FA)為自動機為自動機FA所描述的正規(guī)語言；則所描述的正規(guī)語言；則 則則 L(FA)的生成的生成(或識別或識別)過程如下過程如下所示：所示： 如右圖有限自動機：如右圖有限自動機： 3.2.2 有限自動機所描述的語言有限自動機所描述的語言= x x+-abcbb-設(shè)設(shè) x=a1 a2an ， ai+ a a1 1=i1ia a2 2=i2a an n=j則有則有即：即：含義是含義是: : L(FA)的生成的生成(或識別或識別)過程示例：過程示例：

10、+-abcbb-.第一條通路：第一條通路：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(FA2)= bn| n0 因而因而接受空串的接受空串的 FA的典型特征！的典型特征！【例【例3.6】有限自動機】有限自動機 ：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

11、.2.3 有限自動機的兩種表現(xiàn)形式有限自動機的兩種表現(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))，列列(符號符號)，表項表項(變換后狀態(tài)變換后狀態(tài)) +-abcb bb b- + + 4 3 3 2 4 21234a 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),也不好用！也不好用！

12、 3.2.4 有限自動機的分類有限自動機的分類方法一方法一：聯(lián)合式聯(lián)合式方法二方法二：組合式組合式1 1方法三方法三：組合式組合式2 2+ab bc-+ab b-比較之：比較之：+ab bc- ab b-的有限自動機構(gòu)造：的有限自動機構(gòu)造：三三: 帶有帶有 邊，還是不好用邊，還是不好用!有好用的嗎有好用的嗎?!?!？+ab bc-a ab b-【例【例3.73.7】構(gòu)造正規(guī)語言】構(gòu)造正規(guī)語言+ab bc-a ab ba a- 3.2.4 有限自動機的分類有限自動機的分類【有限自動機分類】【有限自動機分類】1. 確定的有限自動機確定的有限自動機(DFA)特征特征：開始狀態(tài)唯一開始狀態(tài)唯一; 變換

13、函數(shù)單值變換函數(shù)單值; 不帶不帶 邊。邊。2. 非確定的有限自動機非確定的有限自動機(NFA)(1) 帶有帶有 邊的邊的非確定的有限非確定的有限自動機自動機( NFA)(2) 不帶有不帶有 邊的邊的非確定的有限非確定的有限自動機自動機( NFA)- 不能全部滿足上述特征者！不能全部滿足上述特征者！ 確定的有限自確定的有限自動機如右圖所示：動機如右圖所示：+abb-bcb-aa-ccDFA: A= abnc,(ab)n|n0 3.3 有限自動機的等價轉(zhuǎn)換有限自動機的等價轉(zhuǎn)換 有限自動機的有限自動機的等價轉(zhuǎn)換等價轉(zhuǎn)換, ,主要包含兩個內(nèi)容：主要包含兩個內(nèi)容：(1) 有限自動機的確定化有限自動機的確

14、定化( NFA=DFA);(2) 有限自動機的最小化有限自動機的最小化( DFA=最小的最小的DFA); 非確定機非確定機(NFA) 較易構(gòu)造較易構(gòu)造，但不好用！但不好用！ 確定機確定機 (DFA) 較難構(gòu)造，但好用！較難構(gòu)造，但好用！ 任何一非確定機任何一非確定機NFA，皆可通過有效算，皆可通過有效算法把其轉(zhuǎn)化為等價的確定機法把其轉(zhuǎn)化為等價的確定機DFA（二者描（二者描述的語言相同）。述的語言相同）。 有限自動機的有限自動機的最小化最小化, ,又稱有限自動機的又稱有限自動機的化簡化簡；是；是指：指：對給定的確定機對給定的確定機DFA1,構(gòu)造另一個確定機構(gòu)造另一個確定機DFA2,使得使得 L(

15、DFA1)=L(DFA2),且且DFA2的狀態(tài)最少。的狀態(tài)最少。 ab* , b+ , L(FA2)=abn,bn|n0 【定義【定義1】設(shè)有兩個有限自動機】設(shè)有兩個有限自動機FA1和和FA2，若，若L(FA1)= L(FA2)則稱則稱FA1與與FA2等價，記作等價，記作FA1 FA2。 3.3.1 有限自動機的有限自動機的等價等價. 兩個自動機的等價：兩個自動機的等價：+ab b- b b FA2FA1 L(FA1)=L(FA2)+ +ab b-b bb b- FA1 FA2四條四條通路，分別接受：通路，分別接受： ab+ , ab* , b+ , L(FA1)=abn,bn|n0二條二條通

16、路，分別接受：通路，分別接受： . . 兩個狀態(tài)的等價：兩個狀態(tài)的等價： 【定義【定義2】設(shè)】設(shè) i 和和 j 為為FA的兩個狀態(tài)，若把其的兩個狀態(tài)，若把其看作初看作初態(tài)態(tài)，二者接受的符號串集合相同，則有，二者接受的符號串集合相同，則有 i j (等價等價)。 3.3.1 有限自動機的有限自動機的等價等價【例【例2】FA2+ab bc- 【例【例1】FA1:+ab bc-【注】如何判斷兩個狀態(tài)的等價性？稍后再討論?！咀ⅰ咳绾闻袛鄡蓚€狀態(tài)的等價性？稍后再討論。2 4 ？3 5 ？4 5 ？判斷等價性：判斷等價性：2 3 ？ 2,3節(jié)點構(gòu)成節(jié)點構(gòu)成 閉路閉路 2,3等價等價；可；可合而為一合而為一

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

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

19、ab bc c-+ + c c-+ +ab bc c-+ +c cc c-+ + NFANFA+ + + +- -+ +，+ +，3.3.2 有限自動機的確定化算法有限自動機的確定化算法(續(xù)續(xù)1).把把 化為化為DFADFA算法算法( ( =DFA ) ): : NFANFA NFANFA(2) 按按 的變換函數(shù)實施變換：的變換函數(shù)實施變換： NFANFA (qi1,qin ,ak)= (qi1, ak) (qin, ak)=qj1,qjn(3) 若若qj1,qjn 未作為未作為狀態(tài)行狀態(tài)行標(biāo)記，則作新行標(biāo)記；標(biāo)記，則作新行標(biāo)記；a1a2a3q01,q0n(4) 重復(fù)步驟重復(fù)步驟(2)(3)，

20、直到不再出現(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)記 - 【注】【注】必要時，新產(chǎn)生的必要時，新產(chǎn)生的DFA可用狀態(tài)圖表示?？捎脿顟B(tài)圖表示。 NFANFA字母表中符號字母表中符號 開始態(tài)集開始態(tài)集 NFANFA(1) 構(gòu)造構(gòu)造DFA的變換表的變換表(框架框架)： 確定化示例：確定化示例： NFA+abc-+ab-【例【例3.9】聯(lián)合】聯(lián)合式自動機式自動機NFA: 確定化過程確定化過程:DFA: c

21、b aD3F2E5C2,4G4E5D3F2F2E5G4D3D3C2,4B2,5B2,5+-ABCEFGD+-acbabcc-bba-【注】【注】A,B,C, 狀態(tài)集的代碼狀態(tài)集的代碼A1,4NFA確定化練習(xí)確定化練習(xí)1. 消除消除 邊練習(xí)邊練習(xí)2. 確定化練習(xí)確定化練習(xí) NFANFA1. 消除消除 邊練習(xí)的邊練習(xí)的答案答案2. 確定化練習(xí)的確定化練習(xí)的答案答案 NFANFANFA確定化練習(xí)確定化練習(xí)01122333 4,5,64,5,6 3 7733.3.3 有限自動機的最小化算法有限自動機的最小化算法 最小有限自動機，是指滿足下述條件的確定最小有限自動機，是指滿足下述條件的確定有限自動機：有

22、限自動機：(1) 沒有無用狀態(tài)沒有無用狀態(tài)(無用狀態(tài)已刪除無用狀態(tài)已刪除)；(2) 沒有等價狀態(tài)沒有等價狀態(tài)(等價狀態(tài)已合并等價狀態(tài)已合并)。.刪除無用狀態(tài)算法刪除無用狀態(tài)算法 【定義】【定義】無用狀態(tài)無用狀態(tài)是指自動機從開始態(tài)出發(fā)，對是指自動機從開始態(tài)出發(fā)，對任何符號串都不能到達的狀態(tài)。任何符號串都不能到達的狀態(tài)?！九袆e算法】【判別算法】 構(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不再增大為止。不再增大

23、為止。(4) 從狀態(tài)集從狀態(tài)集Q中，刪除不在中，刪除不在Qus中的所有狀態(tài)。中的所有狀態(tài)。3.3.3 有限自動機的最小化算法有限自動機的最小化算法(續(xù)續(xù)1). . 合并等價狀態(tài)算法合并等價狀態(tài)算法【原理】兩個狀態(tài)【原理】兩個狀態(tài)i , j 等價，當(dāng)且僅當(dāng)滿足下面兩等價，當(dāng)且僅當(dāng)滿足下面兩個條件：個條件： 必須必須同是同是結(jié)束態(tài)結(jié)束態(tài)，或，或同不是同不是結(jié)束態(tài)結(jié)束態(tài)； 對對所有所有字母表上符號，狀態(tài)字母表上符號，狀態(tài) i , j 必變必變換到等價狀態(tài)。換到等價狀態(tài)?！纠堪严率鲎詣訖C最小化：【例】把下述自動機最小化：(1) 初分成兩個不等價子集：初分成兩個不等價子集：Q1=1,2,Q2=3(2)

24、 還能分成不等價子集嗎？還能分成不等價子集嗎？ (1,a)= 2 , (2,a)= 2 又又 (1,b)= 3 , (2,b)= 3+ +- - -b ba ab ba aa a 12(等價等價)合并后的最合并后的最小自動機小自動機+ +- -a ab ba a3.3.3 有限自動機的最小化算法有限自動機的最小化算法(續(xù)續(xù)2). . 合并等價狀態(tài)算法合并等價狀態(tài)算法(1) 初始，把狀態(tài)集初始，把狀態(tài)集Q劃分成兩個不等價子集劃分成兩個不等價子集:Q1(結(jié)束狀態(tài)集結(jié)束狀態(tài)集)， Q2(非結(jié)束狀態(tài)集非結(jié)束狀態(tài)集)；(2) 把每個把每個Qi再劃分成不同的子集，條件是：再劃分成不同的子集，條件是： 對同

25、一對同一Qi中兩個狀態(tài)中兩個狀態(tài) i 和和 j ，若對字母表中，若對字母表中的的某個某個符號，變換到符號，變換到已劃分已劃分的不同的狀態(tài)集中，的不同的狀態(tài)集中，則則 i 和和 j 應(yīng)分離應(yīng)分離:(3) 重復(fù)步驟重復(fù)步驟(2)，直到再不能劃分為止；，直到再不能劃分為止；(4) 合并最終劃分的每個子集中的各狀態(tài)合并最終劃分的每個子集中的各狀態(tài)(合而為一合而為一)。如如 (i,a)Qm , (j,a)Qn 且且 mn- - 劃分不等價狀態(tài)集劃分不等價狀態(tài)集 有限自動機化簡示例有限自動機化簡示例【例【例3.10】 化簡下述化簡下述 DFA:(1) 刪除無用狀態(tài)：刪除無用狀態(tài)： 動態(tài)構(gòu)造動態(tài)構(gòu)造DFA變

26、換表變換表，即從開始狀態(tài)，即從開始狀態(tài) 1 出發(fā)，出發(fā)，把變換后的狀態(tài)填入表項，并同時作為新行標(biāo)記；把變換后的狀態(tài)填入表項，并同時作為新行標(biāo)記；如此下去，直到再不出現(xiàn)新狀態(tài)為止。未出現(xiàn)的狀如此下去，直到再不出現(xiàn)新狀態(tài)為止。未出現(xiàn)的狀態(tài)，就是無用的狀態(tài)。態(tài)，就是無用的狀態(tài)?！咀ⅰ俊咀ⅰ?DFA 中的狀態(tài)中的狀態(tài) 2，8 被刪除被刪除! 4647375644513361ba+-+-bababababaaabaDFA的變換表：的變換表： 有限自動機化簡示例有限自動機化簡示例( (續(xù)續(xù)1) 1) 4647375644513361ba+-DFA:(2) 合并等價狀態(tài)合并等價狀態(tài): 令令 QNE= 1,3

27、,4, 5,6,7 取取 1,3,4 ：即即 QNE= 1,3,4, 5,6,7 取取 3,4： (3,a)=1 , (4,a)=4 劃分劃分 Q1=3, Q2=4 即即 QNE= 1,3,4, 5,6,7 取取 5,6,7: 同理，可劃分成同理，可劃分成 Q1=5, Q2=6,7； 最后：最后： QNE= 1,3,4, 5,6,7 不等價集不等價集 (1,a)=6 , (3,4,a)=1,4 劃分成劃分成 Q1=1, Q2=3,4 有限自動機化簡示例有限自動機化簡示例(續(xù)續(xù)2)4647375644513361ba+-DFA:合并等價狀態(tài)合并等價狀態(tài): 6 , 746365644513361b

28、a+-+- -babbabaaa 6替換替換7最小的最小的DFA ! 有限自動機化簡練習(xí)有限自動機化簡練習(xí)刪除無刪除無用狀態(tài)用狀態(tài)合并等合并等價狀態(tài)價狀態(tài)(3) 令令 getchar(ch) 為讀符號函數(shù)。為讀符號函數(shù)。3.4 有限自動機的實現(xiàn)有限自動機的實現(xiàn) 用計算機完成有限自動機的功能，其核心是用計算機完成有限自動機的功能，其核心是“變換變換”的實現(xiàn)技術(shù)。這里介紹的是把的實現(xiàn)技術(shù)。這里介紹的是把變換表變換表按某按某種方式存儲起來，作為知識源來識別單詞，實現(xiàn)機種方式存儲起來，作為知識源來識別單詞，實現(xiàn)機制是：制是： 控制程序控制程序 變換表變換表 +【三點說明】【三點說明】(1) 假定自動機

29、只作為假定自動機只作為識別器識別器，即，即對對待識別的待識別的符號串符號串： 僅回答僅回答 是是(接受接受) 或或 否否(拒絕拒絕)。 (2) 為便于處理，可令為便于處理，可令 # 作為作為待識別的待識別的符號串符號串的的后繼符后繼符。為此，擴展自動機如下：為此，擴展自動機如下：+-a-b-#ok 4ok 5 6 3 1# b a+-空則空則no3.4.1 控制程序設(shè)計控制程序設(shè)計開始開始結(jié)束結(jié)束state = 1getchar(ch)查變換表：查變換表： (state,ch)= ? =空空 =ok回答回答:yes回答回答:noynystate = n開始狀態(tài)開始狀態(tài)1賦給賦給變量變量 sta

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

31、是把每個狀態(tài)行作為子表，狀態(tài)子表，狀態(tài)為索引，為索引，并把并把錯誤的輸入符號合并在一起，如：錯誤的輸入符號合并在一起，如：nobanofenoyx索引表索引表 (其他其他)-錯誤符號。錯誤符號。狀狀態(tài)態(tài)變換子表變換子表 有限自動機實現(xiàn)示例有限自動機實現(xiàn)示例【例【例3.11】 有限自動機有限自動機DFA: +ab-#abcdnobanodnocbanook#壓縮變換表壓縮變換表輸入串輸入串 aacd# 識別過程：識別過程：備注變換剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表索引表3.5 正規(guī)語言描述方法間的相互轉(zhuǎn)換正規(guī)語言描述方法間的相互轉(zhuǎn)換 正規(guī)語言正規(guī)語言有三種等價的表示方法：有三種等價的表示方法： (1) 正規(guī)文法正規(guī)文法 (2) 正規(guī)式正規(guī)式 (3) 有限自動機有限自動機 我們以我們以有限自動機有限自動機為核心，介紹彼此間的轉(zhuǎn)換關(guān)系：為核心，介紹彼此間的轉(zhuǎn)換關(guān)系： . 正規(guī)文法正規(guī)文法 DFA設(shè)設(shè) G(Z)=(VN,VT,Z,P), DFA=(Q,S,F, )則有：則有：VT(