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

第3章自動(dòng)機(jī)基礎(chǔ)自動(dòng)機(jī)是一種語(yǔ)言模型，是語(yǔ)言的一種識(shí)別工具，其中的

有限自動(dòng)機(jī)(FiniteAutomata)FA被用來(lái)處理正規(guī)語(yǔ)言，后者是編譯程序設(shè)計(jì)中詞法分析的對(duì)象。3.1正規(guī)語(yǔ)言及其描述方法3.2有限自動(dòng)機(jī)的定義與分類3.3有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換3.4有限自動(dòng)機(jī)的實(shí)現(xiàn)3.5正規(guī)語(yǔ)言描述方法間的相互轉(zhuǎn)換3.1正規(guī)語(yǔ)言及其描述方法

【定義】正規(guī)語(yǔ)言是指由正規(guī)文法定義的語(yǔ)言；程序設(shè)計(jì)語(yǔ)言中的單詞，大都屬于此種語(yǔ)言。正規(guī)語(yǔ)言有三種等價(jià)的表示方法：

(1)正規(guī)文法(2)正規(guī)式(3)有限自動(dòng)機(jī)正規(guī)文法僅有三種形式的產(chǎn)生式：

(1)A->aB(2)A->a(3)A->【例3.1】G(Z)：A->aA|∵A=>;A=>aA=>aaA=>aaaA=>…=>an,n≥0∴L(G)={an|n≥0}正規(guī)文法正規(guī)語(yǔ)言※正規(guī)語(yǔ)言判定示例:【例3.2】L1={ambn|m≥0,n≥1},正規(guī)語(yǔ)言?

∵可由正規(guī)文法定義：

G1(S):S->aS|bA;A->bA|∴L1是正規(guī)語(yǔ)言。

【例3.3】L2={(ab)n|n≥1},正規(guī)語(yǔ)言?

∵可由正規(guī)文法定義：

G2(S):S->aA;A->bB;B->aA|∴L2是正規(guī)語(yǔ)言。

【例3.4】L3={anbn|n≥0},正規(guī)語(yǔ)言?

∵不能由正規(guī)文法定義(正規(guī)文法無(wú)法描述a和b數(shù) 量上相等！)：

∴

L3不是正規(guī)語(yǔ)言！

3.1.1正規(guī)語(yǔ)言的另外兩種表示方法Ⅰ.正規(guī)式表示法：

※正規(guī)式是指由字母表中的符號(hào)，通過(guò)以下三種運(yùn)算(也可以使用圓括號(hào))連接起來(lái)構(gòu)成的表達(dá)式e：閉包(*，+)連接

(.)或(|)

※設(shè)val(e),L(e)分別表示正規(guī)式

e的值和語(yǔ)言，則：

L(e)={x|x=val(e)}即正規(guī)式表示的語(yǔ)言是該正規(guī)式所有值的集合。正規(guī)式

L3={abnc,bn

|n≥0}，

L2={(ab)n|n≥1}，e2=(ab)+e3=ab*c|b*

L1={ambn|m≥0,n≥1}，e1=a*b+Ⅱ.有限自動(dòng)機(jī)表示法：

L3={abnc

,bn|n≥0}L2={(ab)n|n≥1}

L1={ambn|m≥0,n≥1}+①②b-ab+①②③b-aa①②③④+-abcbb--FA1:FA2:FA3:※初看起來(lái)，有限自動(dòng)機(jī)是帶標(biāo)記的有向圖！3.1.1正規(guī)語(yǔ)言的另外兩種表示方法

{1,2,3,4}—狀態(tài)集;

其中：+(開始狀態(tài))；

-(結(jié)束狀態(tài)){a,b,c}—字母表；

δ(1,a)=2—

變換

(或);…(表示1狀態(tài)遇符號(hào)a變到2狀態(tài),…)；※有限自動(dòng)機(jī)表示法說(shuō)明：

①②aL3={abnc

,bn|n≥0}①②③④+-abcbb--

一個(gè)FA，若存在一條從某開始狀態(tài)

i到某結(jié)束狀態(tài)j

的通路，且這條通路上所有邊的標(biāo)記連成的符號(hào)串為，則就是一個(gè)句子；所有這樣的的集合，就是該FA表示的語(yǔ)言?！緢D符說(shuō)明】：【運(yùn)行機(jī)制】：FA:e=

ab*c|b*

G(S):S->aA|bB|

，A->bA|c

，B->

bB|※正規(guī)語(yǔ)言的三種表示法綜合示例：【例3.5】L={abnc,bn|n≥0},∑={a,b,c}；

【注】凡是能由上述三種方法中的一種表示的語(yǔ)言，一定是正規(guī)語(yǔ)言；反之，凡是不能由上述三種方法表示的語(yǔ)言，一定不是正規(guī)語(yǔ)言。1.正規(guī)文法描述：

2.正規(guī)式描述:3.有限自動(dòng)機(jī)描述：①②③④+-abcbb--

3.2.1有限自動(dòng)機(jī)的定義狀態(tài)i

遇符號(hào)a時(shí)變換為狀態(tài)

j

3.2有限自動(dòng)機(jī)的定義和分類

變換(二元函數(shù));Q(有限狀態(tài)集);ija或【定義】有限自動(dòng)機(jī)是一種數(shù)學(xué)模型，用于描述正規(guī)語(yǔ)言,可定義為五元組：

FA=(Q,∑,S,F,)

(i,a)=j其中：i,j∈Q,a∈∑+{};F(結(jié)束狀態(tài)集,FQ);S(開始狀態(tài)集,SQ);∑(字母表);即：L(FA)={x|i

j,x∈∑*,i∈S,j∈F}

FA存在一條從某初始狀態(tài)i

到某結(jié)束狀態(tài)j

的連續(xù)變換，且每次變換(=>)的邊標(biāo)記連成的符號(hào)串恰好為x；稱x為FA接受，否則拒絕。令L(FA)為自動(dòng)機(jī)FA所描述的正規(guī)語(yǔ)言；則則L(FA)的生成(或識(shí)別)過(guò)程如下所示：如右圖有限自動(dòng)機(jī)：

3.2.2有限自動(dòng)機(jī)所描述的語(yǔ)言=>

x①②③④+-abcbb--設(shè)

x=a1a2…an，ai∈∑+{}a1=>i1ia2=>i2an=>j…則有即：含義是:

※L(FA)的生成(或識(shí)別)過(guò)程示例：①②③④+-abcbb--Ⅰ.第一條通路：FA1=>b④①+①+=>a②=>b②=>c③①+=>a②=>b②=>b②=>c③…Ⅱ.第二條通路：FA2①+=>①=>a②=>c③①+=>b④=>b④①+…∴L(FA)={abnc,bn|n≥0}∴L(FA1)={abnc|n≥0}∴L(FA2)={bn|n≥0}因而接受空串的

FA的典型特征！【例3.6】有限自動(dòng)機(jī)：FA=(Q,∑,S,F,)

其中:Q={1,2,3,4},∑={a,b,c},S={1,2},F={3,4}

FA

的兩種表現(xiàn)形式：⑴狀態(tài)轉(zhuǎn)換圖:

3.2.3有限自動(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)：行(狀態(tài))，列(符號(hào))，表項(xiàng)(變換后狀態(tài))①②③④+-abcbb-+4332421234abc+--+開始狀態(tài)結(jié)束狀態(tài)

【例3.7】A={abnc,(ab)n|n≥0}二:變換函數(shù)不單值(如一:開始狀態(tài)不唯一,不好用!(1,a)=(2|4)),也不好用！

3.2.4有限自動(dòng)機(jī)的分類方法一：聯(lián)合式方法二：組合式1方法三：組合式2①②③+abc-④⑤+ab-比較之：①②③+abc-④⑤ab-的有限自動(dòng)機(jī)構(gòu)造：三:帶有邊，還是不好用!有好用的嗎?!？①②③+abc-④ab-【例3.7】構(gòu)造正規(guī)語(yǔ)言①②③+abc-④a⑤ba--

3.2.4有限自動(dòng)機(jī)的分類【有限自動(dòng)機(jī)分類】1.確定的有限自動(dòng)機(jī)(DFA)特征：①開始狀態(tài)唯一;②變換函數(shù)單值;③不帶邊。2.非確定的有限自動(dòng)機(jī)(NFA)(1)帶有邊的非確定的有限自動(dòng)機(jī)(NFA)(2)不帶有邊的非確定的有限自動(dòng)機(jī)(NFA)--不能全部滿足上述特征者！

※確定的有限自動(dòng)機(jī)如右圖所示：①②③+abb-b④c⑤⑥⑦b-aa--ccDFA:

A={abnc,(ab)n|n≥0}3.3有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換※有限自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換,主要包含兩個(gè)內(nèi)容：(1)有限自動(dòng)機(jī)的確定化(NFA=>DFA);(2)有限自動(dòng)機(jī)的最小化(DFA=>最小的DFA);非確定機(jī)(NFA)較易構(gòu)造，但不好用！確定機(jī)(DFA)較難構(gòu)造，但好用！

任何一非確定機(jī)NFA，皆可通過(guò)有效算法把其轉(zhuǎn)化為等價(jià)的確定機(jī)DFA（二者描述的語(yǔ)言相同）。有限自動(dòng)機(jī)的最小化,又稱有限自動(dòng)機(jī)的化簡(jiǎn)；是指：對(duì)給定的確定機(jī)DFA1,構(gòu)造另一個(gè)確定機(jī)DFA2,使得L(DFA1)=L(DFA2),且DFA2的狀態(tài)最少。

ab*,b+,L(FA2)={abn,bn|n≥0}

【定義1】設(shè)有兩個(gè)有限自動(dòng)機(jī)FA1和FA2，若L(FA1)=L(FA2)則稱FA1與FA2等價(jià)，記作FA1FA2。

3.3.1有限自動(dòng)機(jī)的等價(jià)Ⅰ.兩個(gè)自動(dòng)機(jī)的等價(jià)：①②③+ab-bFA2FA1∵L(FA1)=L(FA2)①②③+ab-bb---∴FA1FA2※四條通路，分別接受：

ab+,ab*,b+,L(FA1)={abn,bn|n≥0}※二條通路，分別接受：Ⅱ.兩個(gè)狀態(tài)的等價(jià)：

【定義2】設(shè)i和j為FA的兩個(gè)狀態(tài)，若把其看作初態(tài)，二者接受的符號(hào)串集合相同，則有ij(等價(jià))。

3.3.1有限自動(dòng)機(jī)的等價(jià)【例2】FA2①②③+abc-【例1】FA1:①②+abc-【注】如何判斷兩個(gè)狀態(tài)的等價(jià)性？稍后再討論。24？35？45？判斷等價(jià)性：23？√∵2,3節(jié)點(diǎn)構(gòu)成閉路

∴2,3等價(jià)；可合而為一×××a②③-④⑤ba-a(3)對(duì)邊，按通路逆向逐一進(jìn)行：3.3.2有限自動(dòng)機(jī)的確定化算法Ⅰ.消除

邊算法(

NFA=>

或DFA):NFA(1)若存在閉路，則把閉路上各節(jié)點(diǎn)合而為一：②abc-③④②abc-(2)

標(biāo)記隱含的開始態(tài)和結(jié)束態(tài)：開始態(tài)的通路上的節(jié)點(diǎn)：+結(jié)束態(tài)逆向通路上節(jié)點(diǎn)：-①刪除一個(gè)邊；同時(shí)②引進(jìn)新邊：凡由原邊終點(diǎn)發(fā)出的邊，也要由其始點(diǎn)發(fā)出。(4)重復(fù)步驟(3)，直到再無(wú)邊為止。①②+cb-b③++-②ab③⑤bcc∴{am,ambcn,amcn|m≥0,n≥1}L()=NFA(2)

標(biāo)記隱含的開始態(tài)和結(jié)束態(tài)：L(NFA)=?※消除邊算法示例：【例3.8】考查NFA：

①②③+ab④c-(1)

閉路上的節(jié)點(diǎn)等價(jià)（）,可合而為一；①②(3)

逆序逐一刪除邊，同時(shí)引進(jìn)新邊：②③ab④c-+-+①③ab④c-+c-+①③ab④c-+cc-+NFA+++②-③+，④+，3.3.2有限自動(dòng)機(jī)的確定化算法(續(xù)1)Ⅱ.把化為DFA算法(=>DFA):NFANFA(2)

按的變換函數(shù)實(shí)施變換：NFA({qi1,…qin

}

,ak)=(qi1,ak)∪…∪(qin,ak)={qj1,…qjn}(3)若{qj1,…qjn}

未作為狀態(tài)行標(biāo)記，則作新行標(biāo)記；a1a2a3…{q01,…q0n}(4)重復(fù)步驟(2)(3)，直到不再出現(xiàn)新狀態(tài)集為止；(5)標(biāo)記DFA的開始態(tài)和結(jié)束態(tài)：第一行{q01,…q0n}，(右側(cè))標(biāo)記+

；凡是狀態(tài)行中含有的結(jié)束狀態(tài)者，(右側(cè))標(biāo)記-

【注】必要時(shí)，新產(chǎn)生的DFA可用狀態(tài)圖表示。NFA字母表中符號(hào)開始態(tài)集NFA(1)構(gòu)造DFA的變換表(框架)：{…}※確定化示例：NFA①②③+abc-④⑤+ab-【例3.9】聯(lián)合式自動(dòng)機(jī)NFA:※確定化過(guò)程:DFA:cbaD{3}F{2}E{5}C{2,4}G{4}E{5}D{3}F{2}F{2}E{5}G{4}D{3}D{3}C{2,4}B{2,5}B{2,5}+----ABCEFGD+-acbabcc-bba--【注】A,B,C,…狀態(tài)集的代碼A{1,4}※NFA確定化練習(xí)1.消除邊練習(xí)2.確定化練習(xí)NFA1.消除邊練習(xí)的答案2.確定化練習(xí)的答案NFA※NFA確定化練習(xí)01{1}{2}{2}{3}{3}{3}{4,5,6}{4,5,6}{3}{7}{7}{3}3.3.3有限自動(dòng)機(jī)的最小化算法

最小有限自動(dòng)機(jī)，是指滿足下述條件的確定有限自動(dòng)機(jī)：(1)沒(méi)有無(wú)用狀態(tài)(無(wú)用狀態(tài)已刪除)；(2)沒(méi)有等價(jià)狀態(tài)(等價(jià)狀態(tài)已合并)。Ⅰ.刪除無(wú)用狀態(tài)算法

【定義】無(wú)用狀態(tài)是指自動(dòng)機(jī)從開始態(tài)出發(fā)，對(duì)任何符號(hào)串都不能到達(dá)的狀態(tài)?！九袆e算法】構(gòu)造有用狀態(tài)集Qus(1)設(shè)q0

為開始態(tài)，則令q0∈Qus；(2)若qi∈Qus

且有(qi,a)=qj

則令qj∈Qus

；(3)重復(fù)執(zhí)行(2)，直到Qus不再增大為止。(4)從狀態(tài)集Q中，刪除不在Qus中的所有狀態(tài)。3.3.3有限自動(dòng)機(jī)的最小化算法(續(xù)1)Ⅱ.合并等價(jià)狀態(tài)算法【原理】?jī)蓚€(gè)狀態(tài)i,j等價(jià)，當(dāng)且僅當(dāng)滿足下面兩個(gè)條件：①必須同是結(jié)束態(tài)，或同不是結(jié)束態(tài)；②對(duì)所有字母表上符號(hào)，狀態(tài)i,j必變換到等價(jià)狀態(tài)。【例】把下述自動(dòng)機(jī)最小化：(1)初分成兩個(gè)不等價(jià)子集：Q1={1,2},Q2={3}(2)還能分成不等價(jià)子集嗎？∵(1,a)=2,(2,a)=2又(1,b)=3,(2,b)=3①③②+--babaa∴1≡2(等價(jià))合并后的最小自動(dòng)機(jī)①③+-aba3.3.3有限自動(dòng)機(jī)的最小化算法(續(xù)2)Ⅱ.合并等價(jià)狀態(tài)算法(1)初始，把狀態(tài)集Q劃分成兩個(gè)不等價(jià)子集:Q1(結(jié)束狀態(tài)集)，Q2(非結(jié)束狀態(tài)集)；(2)把每個(gè)Qi再劃分成不同的子集，條件是：

對(duì)同一Qi中兩個(gè)狀態(tài)i和j，若對(duì)字母表中的某個(gè)符號(hào)，變換到已劃分的不同的狀態(tài)集中，則i和j應(yīng)分離:(3)重復(fù)步驟(2)，直到再不能劃分為止；(4)合并最終劃分的每個(gè)子集中的各狀態(tài)(合而為一)。如(i,a)∈Qm,(j,a)∈Qn

且m≠n---劃分不等價(jià)狀態(tài)集※有限自動(dòng)機(jī)化簡(jiǎn)示例【例3.10】化簡(jiǎn)下述DFA:(1)刪除無(wú)用狀態(tài)：

動(dòng)態(tài)構(gòu)造DFA變換表，即從開始狀態(tài)1出發(fā)，把變換后的狀態(tài)填入表項(xiàng)，并同時(shí)作為新行標(biāo)記；如此下去，直到再不出現(xiàn)新狀態(tài)為止。未出現(xiàn)的狀態(tài)，就是無(wú)用的狀態(tài)。【注】DFA中的狀態(tài)2，8被刪除!4647375644513361ba+---②③①+⑦-⑥-⑤-bababab④a⑧baaabaDFA的變換表：※有限自動(dòng)機(jī)化簡(jiǎn)示例(續(xù)1)4647375644513361ba+---DFA:(2)合并等價(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},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à)集∵

(1,a)=6,({3,4},a)={1,4}∴劃分成Q1={1},Q2={3,4}※有限自動(dòng)機(jī)化簡(jiǎn)示例(續(xù)2)4647375644513361ba+---DFA:合并等價(jià)狀態(tài):{6,7}46365644513361ba+--③①+⑥-⑤-babb④abaaa

6替換7最小的DFA!※有限自動(dòng)機(jī)化簡(jiǎn)練習(xí)刪除無(wú)用狀態(tài)合并等價(jià)狀態(tài)(3)令getchar(ch)為讀符號(hào)函數(shù)。3.4有限自動(dòng)機(jī)的實(shí)現(xiàn)

用計(jì)算機(jī)完成有限自動(dòng)機(jī)的功能，其核心是“變換”的實(shí)現(xiàn)技術(shù)。這里介紹的是把變換表按某種方式存儲(chǔ)起來(lái)，作為知識(shí)源來(lái)識(shí)別單詞，實(shí)現(xiàn)機(jī)制是：

控制程序變換表+【三點(diǎn)說(shuō)明】(1)假定自動(dòng)機(jī)只作為識(shí)別器，即對(duì)待識(shí)別的符號(hào)串：僅回答是(接受)或否(拒絕)。(2)為便于處理，可令#

作為待識(shí)別的符號(hào)串的后繼符。為此，擴(kuò)展自動(dòng)機(jī)如下：③①+⑥⑤-a④-b-##……ok

4ok

5…………

6

3

1#ba+--空則no3.4.1控制程序設(shè)計(jì)開始結(jié)束state=1getchar(ch)查變換表：(state,ch)=?

=空

=ok回答:yes回答:noynystate=n開始狀態(tài)1賦給變量state從輸入串中讀取一符號(hào)到變量ch

變量state重新被賦值為變換后的狀態(tài)！n…②①3.4.2變換表存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)變換表的存儲(chǔ)結(jié)構(gòu)可選擇下述兩種方式之一：(1)二維數(shù)組，其下標(biāo)是(狀態(tài)，輸入符號(hào))；※為了適應(yīng)不同編碼語(yǔ)言的需要，狀態(tài)和輸入符號(hào)可采取相應(yīng)的編碼形式；通常，使用連續(xù)的正整數(shù)：0,1,2,3,…。(2)壓縮變換表，方法是把每個(gè)狀態(tài)行作為子表，狀態(tài)為索引，并把錯(cuò)誤的輸入符號(hào)合并在一起，如：no…⑧b⑤ano…②f④e…no…⑨y①x索引表(其他)--錯(cuò)誤符號(hào)。狀態(tài)變換子表④③②①※有限自動(dòng)機(jī)實(shí)現(xiàn)示例【例3.11】有限自動(dòng)機(jī)DFA:③①+②④ab-#abcdno②b③ano④dno②c④b③anook#壓縮變換表輸入串a(chǎn)acd#識(shí)別過(guò)程：備注變換剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表3.5正規(guī)語(yǔ)言描述方法間的相互轉(zhuǎn)換

正規(guī)語(yǔ)言有三種等價(jià)的表示方法：

(1)正規(guī)文法(2)正規(guī)式(3)有限自動(dòng)機(jī)

我們以有限自動(dòng)機(jī)為核心，介紹彼此間的轉(zhuǎn)換關(guān)系：

Ⅰ.正規(guī)文法<=>DFA設(shè)G(Z)=(VN,VT,Z,P),DFA=(Q,∑,S,F,)則有：∑VT(A,a)=BA->aB(A,a)=B(結(jié)束態(tài))A->aS(開始態(tài))Z(開始符號(hào))QVNDFA正規(guī)文法A->A(結(jié)束態(tài))有時(shí)需要增加一個(gè)結(jié)束狀態(tài)Z->aZ|bA|,A->bA|dB,B->※正規(guī)文法與DFA間轉(zhuǎn)換示例：【例3.12】自動(dòng)機(jī)=>正規(guī)文法:①②③abcd+-DFA:令Z-①,A-②,B-③則有正規(guī)文法Z->aA|cB,A-