形式語(yǔ)言與自動(dòng)機(jī) 第三章 有窮狀態(tài)自動(dòng)機(jī)1

形式語(yǔ)言與自動(dòng)機(jī)FormalLanguagesandAutomataTheory第三章有窮自動(dòng)機(jī)第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語(yǔ)言的識(shí)別器七、FA的變形-帶輸出的FA第一次課第二次課語(yǔ)言的識(shí)別

方法1：根據(jù)G的定義，尋找一個(gè)派生，或歸約

一、有窮狀態(tài)自動(dòng)機(jī)定義與表示自動(dòng)機(jī)系統(tǒng)的結(jié)構(gòu)及功能特征分析：

1、字母表：系統(tǒng)處理的所有字符串由字母表上的字符組成；2、控制器：系統(tǒng)每次從輸入字符串讀入一個(gè)字符，并根據(jù)當(dāng)前狀態(tài)和讀入的字符，轉(zhuǎn)入新的狀態(tài)；新的狀態(tài)和當(dāng)前狀態(tài)可以相同也可不同；為此，系統(tǒng)具有有窮個(gè)狀態(tài),并需要維護(hù)一個(gè)讀指針。3、幾個(gè)特殊狀態(tài)：一個(gè)開(kāi)始狀態(tài)；系統(tǒng)從此開(kāi)始處理句子；一些稱之為終止?fàn)顟B(tài)或接受狀態(tài)，系統(tǒng)從開(kāi)始狀態(tài)至此狀態(tài)為止，讀入字符構(gòu)成的字符串是語(yǔ)言的一個(gè)句子；系統(tǒng)到達(dá)這些狀態(tài)讀入的全部字符串構(gòu)成系統(tǒng)所能識(shí)別的語(yǔ)言。有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)裝置的物理模型：

有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)裝置的組成：

1、一個(gè)具有一系列方格的輸入字符串的帶子：方格中存放字符，字符從輸入帶左端開(kāi)始存放，輸入帶右端無(wú)窮；

2、一個(gè)有窮狀態(tài)控制器FSC：控制一個(gè)讀頭；每讀入一個(gè)字符，讀頭右移一格，指向下一個(gè)待讀入字符。有窮狀態(tài)控制器FSC的基本工作過(guò)程：

控制器執(zhí)行動(dòng)作由三個(gè)節(jié)拍組成：⑴

讀頭讀入當(dāng)前指向的字符；⑵根據(jù)讀入的字符和其自身當(dāng)前狀態(tài)，改變有窮狀態(tài)控制器的狀態(tài)；⑶

讀頭右移一格指向下一個(gè)字符。有窮狀態(tài)自動(dòng)機(jī)定義與表示

8有窮狀態(tài)自動(dòng)機(jī)定義與表示

δ(q0,0)=q1δ(q0,1)=q3

δ(q0,2)=q3

δ(q1,0)=q2δ(q1,1)=q3δ(q1,2)=q3

δ(q2,0)=q1δ(q2,1)=q3δ(q2,2)=q3

δ(q3,0)=q3δ(q3,1)=q3δ(q3,2)=q3

狀態(tài)表表示法：狀態(tài)圖表示法：q0q3q1q2{1,2}{1,2}{1,2}00{0,1,2}0012狀態(tài)說(shuō)明q0q1q3q3開(kāi)始狀態(tài)q1q2q3q3q2q1q3q3終止?fàn)顟B(tài)q3q3q3q3有窮狀態(tài)自動(dòng)機(jī)定義與表示函數(shù)表示法：

有窮狀態(tài)自動(dòng)機(jī)定義與表示注：狀態(tài)轉(zhuǎn)移圖中可能存在一些并行弧，其從同一節(jié)點(diǎn)出發(fā)，到達(dá)同一節(jié)點(diǎn)。11一個(gè)例子:

分析：目標(biāo)是構(gòu)造一個(gè)DFA，識(shí)別串x是否有連續(xù)的3個(gè)0作為結(jié)尾.狀態(tài)0.目前已經(jīng)讀入了0個(gè)0，即xxxx1或1狀態(tài)1.目前已經(jīng)讀入了1個(gè)0，即

xxxx10或0狀態(tài)2.目前已經(jīng)讀入了2個(gè)0，即

xxxx100或00狀態(tài)3.目前已經(jīng)讀入了3個(gè)0，即

xxxx1000或000

0001S1有窮狀態(tài)自動(dòng)機(jī)定義與表示關(guān)于FA的幾個(gè)基本概念：1、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’2、FA的瞬時(shí)（即時(shí)）描述3、FA狀態(tài)對(duì)讀入字符串的存儲(chǔ)功能4、何謂FA識(shí)別一個(gè)句子或語(yǔ)言5、FA

的等價(jià)性

有窮狀態(tài)自動(dòng)機(jī)定義與表示（1）

定義3.1的補(bǔ)充定義：有窮狀態(tài)自動(dòng)機(jī)定義與表示讀入空串讀入非空串對(duì)于任意的q

∈Q,w∈∑

,a

∈∑，有：

δ’(q,wa)=δ(δ’(q,w),a) =δ(δ’(q,a1a2a3…an），

a) =δ(…δ(δ(q,a1),a2),…,an),a)

說(shuō)明1：DFA從狀態(tài)q出發(fā)處理字符串wa

的狀態(tài)轉(zhuǎn)移過(guò)程：有窮狀態(tài)自動(dòng)機(jī)定義與表示說(shuō)明2：由于Q×∑是Q×∑*的真子集；對(duì)于任意輸入字符a，有δ(q,a)=δ(q,εa) ε是單位元素 =δ(δ(q,ε),a)由補(bǔ)充定義第2條=δ(q,a)

由補(bǔ)充定義第1條有窮狀態(tài)自動(dòng)機(jī)定義與表示可見(jiàn)，狀態(tài)轉(zhuǎn)移函數(shù)δ’可以涵蓋描述δ，因此，不必區(qū)分的使用δ和δ

，通常一般性地用δ代替δ

。定義3.3：設(shè)FAM=(Q,,,q0,F)，x,y∈∑*，δ(q0,x)=q

,

xqy稱為M的一個(gè)瞬時(shí)描述（ID），表示： xy是M正在處理的一個(gè)字符串，其子串x引導(dǎo)M從q0

啟動(dòng)，到達(dá)狀態(tài)q,

M的讀頭當(dāng)前指向子串y的首字符。有窮狀態(tài)自動(dòng)機(jī)定義與表示（2）如果xqay是M一個(gè)瞬時(shí)描述,且（q,a）=p

，則有：

xqay

xapy

表示M在狀態(tài)q時(shí)已處理完字符串x；當(dāng)前讀入的字符為a且轉(zhuǎn)入狀態(tài)p,然后將讀頭向右移動(dòng)一格，指向字符串y的首字符。FAM的瞬時(shí)移動(dòng)描述：有窮狀態(tài)自動(dòng)機(jī)定義與表示FAM的瞬時(shí)移動(dòng)序列描述：

：M從已識(shí)別的字符串出發(fā)，經(jīng)過(guò)n次移動(dòng)，識(shí)別的字符串變?yōu)?；亦即，存在n個(gè)ID構(gòu)成序列：

,

1,2,…,n-1,，使得

1

….

n-1

。有窮狀態(tài)自動(dòng)機(jī)定義與表示例：

q0abc→

aq1bc

→…

→

abcq3ε注：所有移動(dòng)都在M中進(jìn)行時(shí)，可省去推導(dǎo)符中的M，分別記為：幾個(gè)特殊的瞬時(shí)移動(dòng)序列描述：

：M的ID從

出發(fā)，經(jīng)過(guò)若干步（包含零步）移動(dòng)，變成

。

：M的ID從

出發(fā)，經(jīng)過(guò)至少一步移動(dòng)，變成。

：n=0,=。

（M沒(méi)有移動(dòng)）有窮狀態(tài)自動(dòng)機(jī)定義與表示FAM瞬時(shí)移動(dòng)序列描述實(shí)例：例：FAM識(shí)別輸入串1010010001，產(chǎn)生一

個(gè)瞬時(shí)移動(dòng)描述序列：有窮狀態(tài)自動(dòng)機(jī)定義與表示

有窮狀態(tài)自動(dòng)機(jī)定義與表示（3）定義3-4：設(shè)有限自動(dòng)機(jī)FAM=<Q,∑,δ,q0,F>,對(duì)于

q∈Q，能引導(dǎo)FA從開(kāi)始狀態(tài)到達(dá)q的字符串集合set(q)={x|x∈∑*且δ(q0,x)=q

}定義為狀態(tài)

q對(duì)字符串的存儲(chǔ)能力。例：接受語(yǔ)言L={x000|x∈{0,1}*}∪{x001|x∈{0,1}*

}的FAM各狀態(tài)的字符串存儲(chǔ)能力如下： set(q0)={x|x∈∑*,x=ε或者x以1結(jié)尾但不以001結(jié)尾}; set(q1)={x|x∈∑*,x=0或者x以10結(jié)尾} set(q2)={x|x∈∑*,x=00或者x以100結(jié)尾} set(q3)={x|x∈∑*,x僅以000結(jié)尾} set(q4)={x|x∈∑*,x僅以001結(jié)尾}L={x000|x∈{0,1}*}∪{x001|x∈{0,1}*}

set(q0)={x|x∈∑*,x=ε或者x以1結(jié)尾但不以001結(jié)尾}; set(q1)={x|x∈∑*,x=0或者x以10結(jié)尾} set(q2)={x|x∈∑*,x=00或者x以100結(jié)尾} set(q3)={x|x∈∑*,x僅以000結(jié)尾} set(q4)={x|x∈∑*,x僅以001結(jié)尾}有窮狀態(tài)自動(dòng)機(jī)定義與表示說(shuō)明：1、上述5個(gè)集合兩兩互不相交；5個(gè)集合的并正好構(gòu)成M識(shí)別輸入字母表{0，1}的克林閉包；亦即，這5個(gè)集合是關(guān)于{0,1}*的一個(gè)劃分；2、此劃分可由M上的一個(gè)等價(jià)關(guān)系RM確定，亦即，

x,y∈∑*，xRMy

q∈Q,x,y∈set(q)有窮狀態(tài)自動(dòng)機(jī)定義與表示（4）

定義3-6：

設(shè)M1，M2是FA。如果L（M1）=L（M2），則稱M1與M2等價(jià)。有窮狀態(tài)自動(dòng)機(jī)定義與表示（5）第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語(yǔ)言的識(shí)別器七、FA的變形-帶輸出的FA定義3-7：

確定的有限自動(dòng)機(jī)，記作

DFA，為一個(gè)五元組M=<Q,∑,δ,q0,F>，其中，Q，∑，q0，F(xiàn)的意義與FA定義相同；狀態(tài)轉(zhuǎn)移函數(shù)δ:Q×∑→Q

為單值映射函數(shù)，即，對(duì)q∈Q和a∈∑,δ(q,a)=p有唯一映射值；M在狀態(tài)q下讀入字符a，將狀態(tài)q變成唯一狀態(tài)p，讀頭向右移動(dòng)一個(gè)方格，指向輸入字符串的下一個(gè)字符。二、確定的有窮自動(dòng)機(jī)DFA例1：構(gòu)造一DFM，使它接受語(yǔ)言L={x000y|x,y∈{0,1}*}。語(yǔ)言句子結(jié)構(gòu)特征分析：對(duì)于任給輸入字符串x∈{0,1}*，DFAM需逐一檢查x的每個(gè)字符，判斷其中是否存在連續(xù)的000作為子串，有則接受x,然后，繼續(xù)讀完字符串剩余的后綴y。確定的有窮自動(dòng)機(jī)DFAFA的主框架分析：q0：M的開(kāi)始狀態(tài)；

q1：M在q0

后讀入一個(gè)0，其可能是子串000的第一個(gè)0，記住；q2：M在q1后又讀入一個(gè)0，其可能是子串000的第二個(gè)0，記??；q3：M在q2后又讀入一個(gè)0，發(fā)現(xiàn)了子串000，記住，此狀態(tài)為終態(tài)。設(shè)計(jì)–補(bǔ)足FA所缺失的其它狀態(tài)：δ(q0,0)=q1–

可能讀到x第一個(gè)0；δ(q0,1)=q0–回始態(tài)重新檢查；δ(q1,0)=q2–可能讀到x第二個(gè)0；δ(q1,1)=q0-回始態(tài)重新檢查；δ(q2,0)=q3–發(fā)現(xiàn)x的子串000；δ(q2,1)=q0-回始態(tài)重新檢查；

δ(q3,0)=q3

，δ(q3,1)=q3----已到達(dá)終態(tài)，繼續(xù)接受字符串的后綴。

確定的有窮自動(dòng)機(jī)DFA定義控制器的有限狀態(tài)：狀態(tài)表狀態(tài)圖確定的有窮自動(dòng)機(jī)DFADFA識(shí)別字符下面哪個(gè)是自動(dòng)機(jī)可識(shí)別的字符？A.epsilonB.011C.100011D.1011ABCD011100所識(shí)別語(yǔ)言中同一長(zhǎng)度的字符數(shù)這個(gè)自動(dòng)機(jī)可接受的長(zhǎng)度最小的字符是2，共有兩個(gè)，01和10。記作N(2)=2.請(qǐng)問(wèn)：A.N(13)=16B.N(13)=84C.N(12)=14D.N(12)=624ABCD011100解：DFM可定義為：M=（{q0,q1,q2,q3},{0,1},{δ(q0,0)=q1,δ(q1,0)=q2,

δ(q2,0)=q3,δ(q3,0)=q3,δ(q0,1)=q0,δ(q1,1)=q0,

δ(q2,1)=q0,δ(q3,1)=q3

},q0，

q3

）。例1：構(gòu)造一DFM，使它接受語(yǔ)言L={x000y|x,y∈{0,1}*}。確定的有窮自動(dòng)機(jī)DFA例2：構(gòu)造一DFM，使其接受語(yǔ)言L={0n1m2k|n,m,k≧1

}。語(yǔ)言句子結(jié)構(gòu)特征分析：0在最前，1在中間，2在最后，三者不可交叉出現(xiàn)；不可顛倒順序；字符0、1、2的個(gè)數(shù)均不得少于1。確定的有窮自動(dòng)機(jī)DFAFA的主框架分析：q0：M的開(kāi)始狀態(tài)；

q1：M在q0

后讀到至少一個(gè)0，等待讀入更多個(gè)0；q2：M在q1后讀入至少一個(gè)1，等待讀入更多個(gè)1；q3：M在q2后讀入至少一個(gè)2，等待讀入更多個(gè)1

，此狀態(tài)為終態(tài)。確定的有窮自動(dòng)機(jī)DFA求識(shí)別L={0n1m2k|n,m,k≧1

}的DFAM補(bǔ)足FA缺失部分：

-引入陷阱狀態(tài)qt(自鎖態(tài))：系統(tǒng)一旦進(jìn)入則無(wú)法離開(kāi)的狀態(tài)。設(shè)計(jì)要點(diǎn)：1、構(gòu)造一個(gè)識(shí)別給定語(yǔ)言的DFA時(shí)，可先根據(jù)語(yǔ)言的主要特征，畫(huà)出該FA的主體框架圖，然后考慮相關(guān)細(xì)節(jié)問(wèn)題。2、一旦DFA發(fā)現(xiàn)無(wú)法識(shí)別的語(yǔ)言句子，則進(jìn)入陷阱狀態(tài)

qt；引入陷阱狀態(tài)可方便FA的構(gòu)造。

確定的有窮自動(dòng)機(jī)DFA確定的有窮自動(dòng)機(jī)DFA

確定的有窮自動(dòng)機(jī)DFA

注意：M的每個(gè)狀態(tài)給出了語(yǔ)言的等價(jià)類，所有狀態(tài)構(gòu)成了語(yǔ)言上的一個(gè)劃分～

分析：什么是這里的“有窮狀態(tài)”？（或者等價(jià)類）確定的有窮自動(dòng)機(jī)DFA

注意：M的每個(gè)狀態(tài)給出了語(yǔ)言的等價(jià)類，所有狀態(tài)構(gòu)成了語(yǔ)言上的一個(gè)劃分～

分析：什么是這里的“有窮狀態(tài)”？（或者等價(jià)類）

這些等價(jià)類之間如何轉(zhuǎn)換？（xxa意味著xa=2*x+a）確定的有窮自動(dòng)機(jī)DFA

確定的有窮自動(dòng)機(jī)DFA

分析：什么是這里的“有窮狀態(tài)”？小結(jié)：1、有窮自動(dòng)機(jī)FA的一般概念：

自動(dòng)機(jī)定義–五元組：M=<Q,∑,δ,q0,F>

；自動(dòng)機(jī)表示方法：函數(shù)法，狀態(tài)表，狀態(tài)圖；FA的瞬時(shí)移動(dòng)序列描述：xqay

xapy

及n次移動(dòng)合成；FA每個(gè)狀態(tài)對(duì)讀入字符串均具有某種存儲(chǔ)功能：set(q)；

能為FA接受的語(yǔ)言；FA的等價(jià)等。2、確定型有窮自動(dòng)機(jī)DFA的定義及其構(gòu)造：

定義：DFA的狀態(tài)轉(zhuǎn)移函數(shù)

δ唯一；

構(gòu)造：首先，根據(jù)語(yǔ)言結(jié)構(gòu)特征設(shè)計(jì)DFA主框架，然后，運(yùn)用其它未明示的信息補(bǔ)足主框架設(shè)計(jì)；設(shè)計(jì)中可增設(shè)“陷阱狀態(tài)”。第三章有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)FA定義與表示二、確定的有窮自動(dòng)機(jī)DFA三、非確定的有窮自動(dòng)機(jī)NFA四、DFA和NFA的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)ε-NFA六、FA是正則語(yǔ)言的識(shí)別器七、FA的變形-帶輸出的FA例3：求接受語(yǔ)言L（M）={x|x∈

{0,1}*，且 x含有子串00或11}的FA。狀態(tài)表狀態(tài)圖三、非確定有窮自動(dòng)機(jī)NFA

3、此時(shí)的NFA程序應(yīng)視為擁有“智能”，亦即，在一給定狀態(tài)下，它可根據(jù)當(dāng)前從輸入字符串讀入的字符自動(dòng)到δ(q,a)的轉(zhuǎn)移狀態(tài)集合中選擇進(jìn)入一個(gè)正確的狀態(tài)。非確定有窮自動(dòng)機(jī)NFA非確定有窮自動(dòng)機(jī)NFA

幾個(gè)相關(guān)的基本概念：1、引入基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)δ’；2、

NFA接受句子及語(yǔ)言的條件3、兩個(gè)NFA的等價(jià)非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA

非確定有窮自動(dòng)機(jī)NFA定義3-8的補(bǔ)充：狀態(tài)轉(zhuǎn)移函數(shù)δ擴(kuò)展為δ

對(duì)于任意的q

∈Q,w∈∑

,a

∈∑，有：

δ’(q,wa)=δ(δ’(q,w),a) =δ(δ’(q,a1a2a3…an），

a) =δ(…δ(δ(q,a1),a2),…,an),a)

非確定有窮自動(dòng)機(jī)NFA說(shuō)明1：NFA從狀態(tài)q出發(fā)處理字符串wa

狀態(tài)轉(zhuǎn)移過(guò)程：說(shuō)明2：由于Q×∑是Q×∑*

的真子集；對(duì)于任意的q∈Q，a∈∑

，有δ(q，a)=δ’(q，εa) ε是單位元素

={p｜ヨr∈δ(q，ε)，使得p∈δ(r,a)}由定義第2條 ={p｜ヨr∈{q}，使得p∈δ(r,a)}

由定義第1條 ={p｜p∈

δ(q，a)}

q是r的唯一值 =δ(q，a)