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

1、3.1 3.1 正規(guī)語(yǔ)言及其描述方法正規(guī)語(yǔ)言及其描述方法【內(nèi)容提要【內(nèi)容提要】 自動(dòng)機(jī)自動(dòng)機(jī) 是一種語(yǔ)言模型，是語(yǔ)言的一種識(shí)別是一種語(yǔ)言模型，是語(yǔ)言的一種識(shí)別工具，其中的工具，其中的 有限自動(dòng)機(jī)有限自動(dòng)機(jī)(finite automata(finite automata）FAFA 被用來(lái)處理被用來(lái)處理 正規(guī)語(yǔ)言正規(guī)語(yǔ)言，后者是編譯程序設(shè)計(jì)中后者是編譯程序設(shè)計(jì)中詞法詞法分析分析的對(duì)象。的對(duì)象。3.2 3.2 有限自動(dòng)機(jī)的定義與分類有限自動(dòng)機(jī)的定義與分類3.3 3.3 有限自動(dòng)機(jī)的等價(jià)變換有限自動(dòng)機(jī)的等價(jià)變換1,21,23.4 3.4 有限狀態(tài)自動(dòng)機(jī)的實(shí)現(xiàn)問(wèn)題有限狀態(tài)自動(dòng)機(jī)的實(shí)現(xiàn)問(wèn)題3.5 3.5

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

3、aA=aaaA=a=an n ,n0,n0 L(G)= aL(G)= an n | n0 | n0 正規(guī)文法正規(guī)文法正規(guī)語(yǔ)言正規(guī)語(yǔ)言【例【例3.23.2】 L1 = aL1 = am mb bn n| m0 ,n1 , | m0 ,n1 , 正規(guī)語(yǔ)言正規(guī)語(yǔ)言 ? ? 可由正規(guī)文法定義：可由正規(guī)文法定義： G1(S): S - aS|bA ; A - bAG1(S): S - aS|bA ; A - bA| | L1 L1 是正規(guī)語(yǔ)言。是正規(guī)語(yǔ)言。 【例【例3.33.3】 L2 =(ab)L2 =(ab)n n| n1 , | n1 , 正規(guī)語(yǔ)言正規(guī)語(yǔ)言 ? ? 可由正規(guī)文法定義：可由正規(guī)文法定

4、義： G2(S): S - aA ; A - bB ; B - aAG2(S): S - aA ; A - bB ; B - aA| | L2 L2 是正規(guī)語(yǔ)言。是正規(guī)語(yǔ)言。 【例【例3.43.4】 L3 =aL3 =an nb bn n| n0 , | n0 , 正規(guī)語(yǔ)言正規(guī)語(yǔ)言 ? ? 不能由正規(guī)文法定義不能由正規(guī)文法定義( (正規(guī)文法無(wú)法描述正規(guī)文法無(wú)法描述a a和和b b數(shù)量數(shù)量上相等！上相等！) )： L3 L3 不是正規(guī)語(yǔ)言！不是正規(guī)語(yǔ)言！ 3.1.1 3.1.1 正規(guī)語(yǔ)言正規(guī)語(yǔ)言的的正規(guī)式正規(guī)式表示法表示法 正規(guī)式正規(guī)式 是指由字母表中的符號(hào)，通過(guò)以下是指由字母表中的符號(hào)，通過(guò)以

5、下三種運(yùn)算三種運(yùn)算( (也可以使用圓括號(hào)也可以使用圓括號(hào)) )連接起來(lái)構(gòu)成的表達(dá)式連接起來(lái)構(gòu)成的表達(dá)式 e e ： 連接連接 ( ( . .) ) 或或( ( | | ) ) 閉包閉包( ( + +，* * ) ) 設(shè)設(shè) val(e)val(e), ,L(eL(e) ) 分別表示正規(guī)式分別表示正規(guī)式 e e 的的值值和和語(yǔ)言，語(yǔ)言，則：則： L(e)= x| x=val(e L(e)= x| x=val(e)即即 正規(guī)式正規(guī)式表示的表示的語(yǔ)言語(yǔ)言是該是該正規(guī)式所有值的集合正規(guī)式所有值的集合( (正規(guī)集正規(guī)集) )。例： 正規(guī)式正規(guī)式 正規(guī)式的正規(guī)式的 值值 ab.cdeab.cde abcde

6、abcde ab|cdeab|cde ab , cdeab , cde a a+ +a ,aa ,aaaa ,aa ,aaa , , ,a ,an n , ,a a* * , a , aa , aaa , , an , 正規(guī)式正規(guī)式表示表示正規(guī)語(yǔ)言正規(guī)語(yǔ)言示例：示例：展開(kāi)：展開(kāi)： L(e3) = ab L(e3) = abn nc, bc, bn n | n0 | n0 ， L(e2) = (ab) L(e2) = (ab)n n| n1 | n1 ， e2=(ab e2=(ab) )+ + e3= ab e3= ab* *c|bc|b* * L L（e1e1）= a= am mb bn n|

7、 m0 ,n1 | m0 ,n1 ， e1= a e1= a* *b b+ + = b,ab,bb,aaab,aab,abb,aabb = b,ab,bb,aaab,aab,abb,aabb, , = ab,abab,ababab,abababab = ab,abab,ababab,abababab, , = ac,abc,abbc,abbbc = ac,abc,abbc,abbbc, ,; ; ,b,bb,bbb,b,bb,bbb, , 【例】：【例】：3.1.2 3.1.2 正規(guī)語(yǔ)言正規(guī)語(yǔ)言的的有限自動(dòng)機(jī)有限自動(dòng)機(jī)表示法：表示法： L3= ab L3= abn nc c ,b,bn n|n

8、0 |n0 ， L2= (ab) L2= (ab)n n| n1 | n1 ， L1= a L1= am mb bn n| m0 ,n1 | m0 ,n1 ，+ + b- -ab+ + b- -aa+-abcbb-FA1:FA1:FA2:FA2:FA3:FA3: 初看起來(lái)，有限自動(dòng)機(jī)是帶標(biāo)記的有向圖！初看起來(lái)，有限自動(dòng)機(jī)是帶標(biāo)記的有向圖！1,2,3,4 1,2,3,4 狀態(tài)集狀態(tài)集; ; 其中：其中： +(+(開(kāi)始狀態(tài)開(kāi)始狀態(tài)) )； -(-(結(jié)束狀態(tài)結(jié)束狀態(tài)) )a,b,c a,b,c 字母表；字母表； (1,a)=2 (1,a)=2 變換變換 ( ( 或或 ););a L3= L3= ab

9、 abn nc c ,b,bn n|n0 |n0 +-abcbb-FA3:FA3: 一個(gè)一個(gè) FAFA，若存在一條從某開(kāi)始狀態(tài)，若存在一條從某開(kāi)始狀態(tài) i i 到某結(jié)束到某結(jié)束狀態(tài)狀態(tài) j j 的通路，且這條通路上所有邊的標(biāo)記連成的的通路，且這條通路上所有邊的標(biāo)記連成的符號(hào)串為符號(hào)串為 ，則，則 就是一個(gè)句子；就是一個(gè)句子；所有這樣的所有這樣的 的集的集合，就是該合，就是該 FA FA 表示的語(yǔ)言表示的語(yǔ)言。【圖符說(shuō)明】：【圖符說(shuō)明】：【運(yùn)行機(jī)制【運(yùn)行機(jī)制】：】：（ 表示表示1 1狀態(tài)遇符號(hào)狀態(tài)遇符號(hào)a a變到變到2 2狀態(tài)狀態(tài), ,) )；e =e = abab* *c|bc|b* * G(

10、S): S- aA|bBG(S): S- aA|bB| | ，A - bA|A - bA|c c ，B -B - bBbB| | 【例【例3.53.5】 L = abL = abn nc, bc, bn n| n0 ,= a,b,c| n0 ,= a,b,c； 【注】【注】 凡是能由上述三種方法表示的語(yǔ)言，一定凡是能由上述三種方法表示的語(yǔ)言，一定是是正規(guī)語(yǔ)言正規(guī)語(yǔ)言；反之，凡是不能由上述三種方法表示；反之，凡是不能由上述三種方法表示的語(yǔ)言，一定的語(yǔ)言，一定不是正規(guī)語(yǔ)言不是正規(guī)語(yǔ)言。1. 1. 正規(guī)文法描述：正規(guī)文法描述： 2. 2. 正規(guī)式描述正規(guī)式描述: :3. 3. 有限自動(dòng)機(jī)描述：有限自

11、動(dòng)機(jī)描述：+-abcbb-FA:FA:表示可接受表示可接受空串空串！ 3.2.1 3.2.1 有限自動(dòng)機(jī)的定義有限自動(dòng)機(jī)的定義狀態(tài)狀態(tài) i i 遇符號(hào)遇符號(hào) a,a,變換為狀態(tài)變換為狀態(tài) j j ：變換（二元函數(shù)）：變換（二元函數(shù)）：Q Q( (有限狀態(tài)集有限狀態(tài)集); ); i ij ja a或或【定義】【定義】 有限自動(dòng)機(jī)是一種數(shù)學(xué)模型，用于描述正有限自動(dòng)機(jī)是一種數(shù)學(xué)模型，用于描述正規(guī)語(yǔ)言規(guī)語(yǔ)言, ,可定義為可定義為五元組五元組： (i,a(i,a）=j=j其中：其中：i,jQ, i,jQ, aa+ ;F F( (結(jié)束狀態(tài)集結(jié)束狀態(tài)集, ,F F Q Q ）；）；S S( (開(kāi)始狀態(tài)開(kāi)始狀

12、態(tài)集集, ,S S Q Q）；( (字母表字母表) )；【含義【含義】FA=( Q,S,F,FA=( Q,S,F, ) )L(FA)L(FA)= x| i= x| i FA FA 存在一條從某初始狀態(tài)存在一條從某初始狀態(tài) i i 到某結(jié)束狀態(tài)到某結(jié)束狀態(tài) j j 的的連續(xù)變換連續(xù)變換，且，且每次變換每次變換( (=) )的邊標(biāo)記連成的符號(hào)串恰的邊標(biāo)記連成的符號(hào)串恰好為好為 x x ；稱稱x x為為FAFA接受，否則拒絕接受，否則拒絕。 令令 L(FA)L(FA)為自動(dòng)機(jī)為自動(dòng)機(jī)FAFA所描述的正規(guī)語(yǔ)言；則所描述的正規(guī)語(yǔ)言；則如如 右圖有限自動(dòng)機(jī)：右圖有限自動(dòng)機(jī)：= x x+-abcbb-設(shè)設(shè)

13、x=ax=a1 1 a a2 2a an n ， a ai i+ a a1 1=i i1 1i ia a2 2=i i2 2a an n=j j則有則有即：即：含義是含義是: :j , j , xx* * , ,iS,jFiS,jF 則則 L(FA)L(FA)的的識(shí)別識(shí)別過(guò)程如下所過(guò)程如下所示：示：+-abcbb-.第一條通路：第一條通路：FA1FA1=b b+ + +=a a =b b=c c+ +=a a =b b =b b=c c.第二條通路：第二條通路：FA2FA2+ += =a a =c c+ +=b b =b b+ + L(FA)=abL(FA)=abn nc, bc, bn n|

14、 n0 | n0 L(FA1)= abL(FA1)= abn nc c| n0 | n0 L(FA2)= bL(FA2)= bn n| n0 | n0 因而因而接受空串的接受空串的 FAFA的典型特征！的典型特征！【例【例3.63.6】有限自動(dòng)機(jī)有限自動(dòng)機(jī) ：FA=( Q,S,F,FA=( Q,S,F, ) ) 其中其中: : Q Q=1,2,3,4,=1,2,3,4,=a,b,c, =a,b,c, S S=1,2, =1,2, F F=3=3，44 FAFA 的兩種表現(xiàn)形式：的兩種表現(xiàn)形式： 狀態(tài)圖狀態(tài)圖: : ：(1,a)=2;(1,b)=4(1,a)=2;(1,b)=4；(2,b)=2(

15、2,b)=2； (2,c)=3(2,c)=3；(2,(2, )=3)=3；(4,b)=4(4,b)=4； 變換表變換表: : 變換表結(jié)構(gòu)變換表結(jié)構(gòu)：行號(hào)行號(hào)( (狀態(tài)狀態(tài)),),列號(hào)列號(hào)( (符號(hào)符號(hào)),),表項(xiàng)表項(xiàng)( (變換后變換后狀態(tài)狀態(tài)) ) +-abcb bb b- + +4332421 12 23 34 4a ab bc c + +- - -+ +開(kāi)始狀態(tài)開(kāi)始狀態(tài)結(jié)束狀態(tài)結(jié)束狀態(tài)a ab b【例【例3.73.7】 A= abA= abn nc,(ab)c,(ab)n n|n0 |n0 三三：變換函數(shù)不單值，：變換函數(shù)不單值，如如一一：開(kāi)始狀態(tài)不唯一：開(kāi)始狀態(tài)不唯一, ,不好用不好用!

16、 !( ( (1,a)=(2|4) ),(1,a)=(2|4) ),也不好用！也不好用！方法一方法一：聯(lián)合式聯(lián)合式方法二方法二：組合式組合式1 1比較：比較：二二：帶有：帶有 邊，還是不好用邊，還是不好用! !有好用的嗎有好用的嗎?!?!FAFA的構(gòu)造：的構(gòu)造：+ab bc-+ -+ -ab b+ -+ -ab b+ab bc-或或+ab bc-【例【例3.73.7】構(gòu)造正規(guī)語(yǔ)言】構(gòu)造正規(guī)語(yǔ)言+ab bc-a ab ba a- A=ab A=abn nc,(ab)c,(ab)n n|n0 |n0 +ab bb b-b bcb b-aa-ccDFA:DFA: 確定的有確定的有限自動(dòng)機(jī)如右圖限自動(dòng)

17、機(jī)如右圖所示：所示：方法三方法三：確定式確定式+ab bb b-b bcb b-aa-ccDFA:DFA: 確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī)(DFA)(DFA)特征特征：開(kāi)始狀態(tài)唯一開(kāi)始狀態(tài)唯一; ; 變換函數(shù)單值；變換函數(shù)單值；不帶不帶 邊。邊。 非確定的有限自動(dòng)機(jī)非確定的有限自動(dòng)機(jī)(NFA)(NFA) 帶有帶有 邊的邊的非確定的有限非確定的有限自動(dòng)機(jī)自動(dòng)機(jī)( ( NFA)NFA) 不帶有不帶有 邊的邊的非確定的有限非確定的有限自動(dòng)機(jī)自動(dòng)機(jī)( NFA)( NFA)- - 不能全部具備上述特征者！不能全部具備上述特征者！ 3.2.4 3.2.4 有限自動(dòng)機(jī)的分類有限自動(dòng)機(jī)的分類+ab b- b

18、 b FA1FA1+ +ab b-b bb b-【例例3.83.8 】試分別指出下述有限自動(dòng)機(jī)的分類情況：】試分別指出下述有限自動(dòng)機(jī)的分類情況：FA2FA2+ab bc- FA3FA3ab bc c-+ +c cc c+ +ab bc c-+ +c cb bFA5FA5結(jié)論：結(jié)論：DFADFA: FA2: FA2NFANFA: FA4,FA5: FA4,FA5FA1,FA3 (FA1,FA3 ( NFA)NFA)FA4FA4( NFA)( NFA) 【習(xí)題【習(xí)題3.13.1】解釋下列詞語(yǔ)：】解釋下列詞語(yǔ)： 正規(guī)文法，正規(guī)語(yǔ)言，有限自動(dòng)機(jī)；正規(guī)文法，正規(guī)語(yǔ)言，有限自動(dòng)機(jī)； 確定的有限自動(dòng)機(jī)，非確定的有限自動(dòng)機(jī)。確定的有限自動(dòng)機(jī)，非確定的有限自動(dòng)機(jī)?！玖?xí)題【習(xí)題3.23.2】給定正規(guī)語(yǔ)言，構(gòu)造有限自動(dòng)機(jī)：】給定正規(guī)語(yǔ)言，構(gòu)造有限自動(dòng)機(jī)： 無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù) （正規(guī)式為（正規(guī)式為 e=dde=dd* *） 標(biāo)識(shí)符集標(biāo)識(shí)符集( (正規(guī)式為正規(guī)式為 e= e= ( (|d)|d)* * ) ) A= a A= an n,ba,ban n |n0 |n0