有限狀態(tài)自動機課件

2023/7/261有限狀態(tài)系統(tǒng)實例指針式鐘表共有12*60*60個狀態(tài)，每過一秒，鐘表就從一種狀態(tài)到另一種狀態(tài)。圍棋共有3361個狀態(tài)，每走一步棋就從一個狀態(tài)到另一個狀態(tài)。電視開電視關打開關閉2023/7/262有限狀態(tài)系統(tǒng)——淘寶網上購物顧客、店家和支付寶網三方之間的交互限于以下幾種事件：1、顧客告訴店家購買某種物品，決定預付款購物。并將錢款轉入支付寶。2、顧客決定取消預付款。顧客通知支付寶，把購物這筆錢保留在自己的銀行帳號上。3、店家送貨給顧客。4、顧客收到貨后

（1）確認付款。

通知支付寶將錢款劃撥到店家?guī)ぬ?，轉到（5）（2）退貨。把購物這筆錢保留在自己的銀行帳號上，結束。（3）換貨。寄回店家，店家重送貨給顧客。5、支付寶將這筆錢轉帳。把顧客購物這筆錢劃撥給店家的帳號。以上的事件以及事件間在一定條件下轉化的情況，可以表示成有限狀態(tài)系統(tǒng)，每個狀態(tài)表示某一方所處的局面。選物品預付款已購物送貨已收貨換貨更換物品選物品預付款已購物確認付款認可物品退貨不認可物品換貨取消選物品已購物確認付款認可物品轉帳交易結束不認可物品取消取消2023/7/2643.1語言的識別

推導和歸約中的回溯問題將對系統(tǒng)的效率產生極大的影響

SaA|aBAaA|cBaB|d系統(tǒng)識別語言{anc|n≥1}∪{and|n≥1}的字符串過程中狀態(tài)的變化圖示如上

2023/7/265識別系統(tǒng)(模型)⑴系統(tǒng)有有限個狀態(tài)，不同狀態(tài)代表不同的規(guī)定任務。⑵輸入字符串中出現(xiàn)的字符構成一個字母表。系統(tǒng)處理的所有字符串都是這個字母表上的字符串。

⑶系統(tǒng)在任何一個狀態(tài)下，從輸入字符串中讀入字符后，可轉到新的狀態(tài)（或狀態(tài)不變）。下一次再讀時，會讀入下一個字符。2023/7/266⑷系統(tǒng)中有一個開始狀態(tài)，系統(tǒng)在這個狀態(tài)下開始進行某個給定句子的處理。

⑸系統(tǒng)中有一些狀態(tài)表示它到目前為止所讀入的字符構成的字符串是語言的一個句子，把所有將系統(tǒng)從開始狀態(tài)引導到這種狀態(tài)的字符串放在一起構成一個語言，該語言就是系統(tǒng)所能識別的語言。

2023/7/267相應的物理模型一個右端無窮的輸入帶。一個有限狀態(tài)控制器(finitestatecontrol,FSC)

。一個讀頭。

系統(tǒng)的每一個動作由三個節(jié)拍構成：讀入讀頭正注視的字符；根據(jù)當前狀態(tài)和讀入的字符改變有限控制器的狀態(tài)；將讀頭向右移動一格。2023/7/2683.2有限狀態(tài)自動機有限狀態(tài)自動機(finiteautomaton,FA)是一個五元組：M=(Q，∑，q0，δ，F(xiàn))Q——狀態(tài)的非空有限集合。

q∈Q，q為M的一個狀態(tài)?！啤斎胱帜副怼］斎胱址际恰粕系淖址?。

q0——q0∈Q，是M的開始狀態(tài)（初始狀態(tài)或者啟動狀態(tài)）。2023/7/269δ——狀態(tài)轉移函數(shù)(轉換函數(shù)或移動函數(shù))，δ：Q×∑Q，對(q，a)∈Q×∑，δ(q，a)=p表示：M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭指向輸入字符串的下一個字符。F——FQ，是M的終止狀態(tài)集合。

q∈F，q稱M的終止狀態(tài)（接受狀態(tài)）。

狀態(tài)轉移圖狀態(tài)轉換圖2023/7/2610例有限狀態(tài)自動機

M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中：δ1(q0,0)=q1δ1(q1,0)=q2，δ1(q2,0)=q1q00q1S0q20識別{(00)n|n>=1}有限自動機的表示（1）轉移圖表示法（2）矩陣表示法符號狀態(tài)0q0（初始）q1q1q2q2（終止）q12023/7/2613確定的有限狀態(tài)自動機對于任意的q∈Q，

a∈∑，δ(q，a)均有確定的值，這種FA稱為確定的有限狀態(tài)自動機(deterministicfiniteautomaton，DFA)

M接受(識別)的語言

對于x∈∑*如果δ’(q0，x)∈F，則稱x被M接受。L(M)={x|x∈∑*且δ(q0，x)∈F}稱為由M接受(識別)的語言

δ：Q×∑Q，對(q，a)∈Q×∑，δ’：Q×∑*Q，對(q，w)∈Q×∑，對任意的q∈Q，w∈∑*，a∈∑，定義

(1)δ’(q,)=q(2)δ’(q,wa)=δ(

δ’(q,w),a)δ’(q,a)=δ’(q,

a)=δ(

δ’(q,),a)=δ(q,a)對于δ(q0,0)=q1,δ(q1,1)=q2,δ(q2,0)=q3,δ’(q0,010)=δ(δ’(q0,01),0)=δ(δ(δ’(q0,0),1),0)=δ(δ(δ(δ’(q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q1,1),0)=δ(q2

,0)=q3不用區(qū)分這兩個符號2023/7/2617例構造一個DFA，它接受的語言為{x000y|x，y∈{0，1}*}q0——M的啟動狀態(tài)；q1——M讀到了一個0，這個0可能是子串“000”的第1個0；q2——M在q1后緊接著又讀到了一個0，這個0可能是子串“000”的第2個0；q3——M在q2后緊接著又讀到了一個0，發(fā)現(xiàn)輸入字符串含有子串“000”；因此，這個狀態(tài)應該是終止狀態(tài)。2023/7/2618δ(q0,1)=q0——M在q0讀到了一個1，它需要繼續(xù)在q0“等待”可能是子串“000”的第1個0的輸入字符0；δ(q1,1)=q0——M在剛剛讀到了一個0后，讀到了一個1，表明在讀入這個1之前所讀入的0并不是子串“000”的第1個0，因此，M需要重新回到狀態(tài)q0，以尋找子串“000”的第1個0；

2023/7/2619δ(q2,1)=q0——M在剛剛發(fā)現(xiàn)了00后，讀到了一個1，表明在讀入這個1之前所讀入的00并不是子串“000”的前兩個0，因此，M需要重新回到狀態(tài)q0，以尋找子串“000”的第1個0；δ(q3,0)=q3——M找到了子串“000”，只用讀入該串的剩余部分。δ(q3,1)=q3——M找到了子串“000”，只用讀入該串的剩余部分。

2023/7/2620M=({q0，q1，q2，q3}，{0，1}，{(q0,0)=q1，δ(q1,0)=q2，δ(q2,0)=q3，δ(q0,1)=q0，δ(q1,1)=q0，δ(q2,1)=q0，δ(q3,0)=q3，δ(q3,1)=q3}，q0，{q3})

2023/7/2621例構造一個DFA，它接受的語言為{x000|x∈{0，1}*}。狀態(tài)q0讀到的0可能是輸入字符串的最后三個0的第1個0；在狀態(tài)q1緊接著讀到的0可能是輸入字符串的最后三個0的第2個0；在狀態(tài)q2緊接著讀到的0可能是輸入字符串的最后三個0的第3個0；2023/7/2622在狀態(tài)q3緊接著讀到的0也可能是輸入字符串的最后三個0的第3個0；如果在狀態(tài)q1，q2，q3讀到的是1，則要重新檢查輸入串是否以三個0結尾。

2023/7/2623接受語言{x000|x∈{0，1}*}∪{x001|x∈{0，1}*}的FA

2023/7/2624例

構造一個DFA，它接受的語言為{0n1m2k|n,m,k≥1}。

q0——M的啟動狀態(tài)；q1——M讀到至少一個0，并等待讀更多的0；q2——M讀到至少一個0后，讀到了至少一個1，并等待讀更多的1；q3——M讀到至少一個0后跟至少一個1后，并且接著讀到了至少一個2。

2023/7/2625先設計“主體框架”再補充細節(jié)當FA進入qt就無法離開此狀態(tài)。qt相當于一個陷阱狀態(tài)(trap)。一般將陷阱狀態(tài)用作發(fā)現(xiàn)輸入串不可能是該FA所識別的語言的句子時進入的狀態(tài)。在此狀態(tài)下，F(xiàn)A讀完輸入串中剩余的字符。

2023/7/2626例構造一個DFA，它接受的語言為{x|x∈{0，1}*，且當把x看成二進制數(shù)時，x模3與0同余}。

分析：換句話說，x要能被3整除。當二進制數(shù)x的位數(shù)向右不斷增加時，它的值（換算成十進制）的增加很有規(guī)律：x0的值等于2x，x1的值等于2x+1。例如x=100，它的十進制值是4，右邊添上0后為1000，它的十進制值是8；右邊添上1后為1001，它的十進制值是9。如x模3余1，則2x模3余2，而2x+1模3余3，即能被3整除了。又如有某個x模3余2，則2x模3余4，而余數(shù)4大于3，被3除余1，所以2x模3余1；而2x+1模3余5，相當于模3余2。經這樣分析以后，F(xiàn)AM除初始狀態(tài)外，只需要設3個狀態(tài)：模3余0狀態(tài)（即終結狀態(tài)），模3余1狀態(tài)，模3余2狀態(tài)。2023/7/2627接受語言{x|x∈{0，1}*，且當把x看成二進制數(shù)時，x模3與0同余}的DFA如下：

qs0S10q00能被3整除q1101模3余100能被3整除01模3余1q210模3余20111能被3整除100模3余11101模3余2接受的語言是由一切含有偶數(shù)個0和偶數(shù)個1的字符串組成的集合。確定有限自動機的程序設計q=m_q[q][d]2023/7/26303.3不確定有限自動機一個非確定的有限自動機(NondeterministicFiniteAutomata)簡記為NFA，是一個五元組 M=(Q,∑,δ,q0,F)

其中Q、∑、q0和F與確定的有限自動機的含意相同，只是轉移函數(shù)δ的定義不同，它是從Q×∑到2Q（Q的一切子集的集合）上的映射。在DFA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中轉移函數(shù)δ的取值是一個狀態(tài)集，即使只有一個狀態(tài)p，也要寫成集合形式{p}。2023/7/2631希望是接受{x|x∈{0，1}*，且x含有子串00或11}的FA如下：2023/7/2632希望是接受{x|x∈{0，1}*，且x的倒數(shù)第10個字符為1}的FA如下：2023/7/2633這兩個圖所給的“FA”與前面我們所定義的FA，即DFA，的區(qū)別在于：⑴

并不是對于所有的(q，a)∈∑×Q,δ(q，a)都有一個狀態(tài)與它對應；⑵

并不是對于所有的(q，a)∈∑×Q,δ(q，a)只對應一個狀態(tài)。

“FA”在任意時刻可以處于有限多個狀態(tài)。

2023/7/2634對于一個輸入字符，NFA與DFA的差異是前者可以進入若干個狀態(tài)，而后者只能進入一個惟一的狀態(tài)。雖然從DFA看待問題的角度來說，NFA在某一時刻同時進入若干個狀態(tài)，但是，這若干個狀態(tài)合在一起的“總效果”相當于它處于這些狀態(tài)對應的一個“綜合狀態(tài)”。因此，我們考慮讓DFA用一個狀態(tài)去對應NFA的一組狀態(tài)。

2023/7/2635NFA與DFA等價

NFAM1=(Q，∑，δ1，q0，F(xiàn)1)與DFAM2=(Q2，∑，δ2，q0′，F(xiàn)2)的對應關系：NFA從開始狀態(tài)q0啟動，我們就讓相應的DFA從狀態(tài)[q0]啟動。所以q0′=[q0]。

對于NFA的一個狀態(tài)組{q1，q2，…，qn}，如果NFA在此狀態(tài)組時讀入字符a后可以進入狀態(tài)組{p1，p2，…，pm},則讓相應的DFA在狀態(tài)[q1，q2，…，qn]讀入字符a時，進入狀態(tài)[p1，p2，…，pm]。

2023/7/2636構造給定NFA等價的DFA策略先只把開始狀態(tài)[q0]填入表的狀態(tài)列中，如果表中所列的狀態(tài)列有未處理的，則任選一個未處理的狀態(tài)[q1，q2，…，qn]，對∑中的每個字符a，計算δ([q1，q2，…，qn]，a)，并填入相應的表項中，如果δ([q1，q2，…，qn]，a)在表的狀態(tài)列未出現(xiàn)過，則將它填入表的狀態(tài)列。如此重復下去，直到表的狀態(tài)列中不存在未處理的狀態(tài)。

從NFA構造等價的DFA更為實用的方法是采取以下步驟：從狀態(tài)[q0]出發(fā)，通過狀態(tài)轉移函數(shù)δ′，逐步擴充狀態(tài)集；每一步僅對狀態(tài)集中新增加的狀態(tài)，才寫出狀態(tài)轉移函數(shù)；此過程一直繼續(xù)下去，直到不再增加新的狀態(tài)為止，最后就得到了DFA。第一步

從[q0]開始：

δ′([q0],0)=[q0,q1],δ′([q0],1)=[q0,q2]。

第二步

處理兩個新狀態(tài)[q0,q1]和[q0,q2]：

δ′([q0,q1],0)=[q0,q1,q3]，

δ′([q0,q1],1)=[q0,q2]；

δ′([q0,q2],0)=[q0,q1]，

δ′([q0,q2],1)=[q0,q2,q3]。

第三步

處理新增加的兩個狀態(tài)[q0,q1,q3]和[q0,q2,q3]：

δ′([q0,q1,q3],0)=[q0,q1,q3],δ′([q0,q1,q3],1)=[q0,q2,q3]；

δ′([q0,q2,q3],0)=[q0,q1,q3],δ′([q0,q2,q3],1)=[q0,q2,q3]。到這一步為止，不再增加新的狀態(tài)，所求的DFA只包含5個狀態(tài)。2023/7/2639NFA的等價DFA

第一步

從[q0]開始：

δ′([q0],0)=[q0,q3],δ′([q0],1)=[q0,q1]。

第二步

處理兩個新狀態(tài)[q0,q3]和[q0,q1]：

δ′([q0,q3],0)=[q0,q3,q4]，

δ′([q0,q3],1)=[q0,q1]；

δ′([q0,q1],0)=[q0,q3]，

δ′([q0,q1],1)=[q0,q1,q2]。

第三步

處理新增加的兩個狀態(tài)[q0,q3,q4]和[q0,q1,q2]：

δ′([q0,q3,q4],0)=[q0,q3,q4],δ′([q0,q3,q4],1)=[q0,q1,q4]；

δ′([q0,q1,q2],0)=[q0,q3,q2],δ′([q0,q1,q2],1)=[q0,q1,q2]。

第四步

處理新增加的兩個狀態(tài)[q0,q1,q4]和[q0,q3,q2]：δ′([q0,q1,q4],0)=[q0,q3,q4],δ′([q0,q1,q4],1)=[q0,q1,q2,q4]；

δ′([q0,q3,q2],0)=[q0,q3,q4,q2],δ′([q0,q3,q2],1)=[q0,q1,q2]。

第五步

處理新增加的兩個狀態(tài)[q0,q1,q2,q4]和[q0,q3,q4,q2]：

δ′([q0,q1,q2,q4],0)=[q0,q3,q4,q2],δ′([q0,q1,q2,q4],1)=[q0,q1,q2,q4]；

δ′([q0,q3,q4,q2],0)=[q0,q3,q4,q2],δ′([q0,q3,q4,q2],1)=[q0,q1,q2,q4]。到這一步為止，不再增加新的狀態(tài)，所求的DFA只包含9個狀態(tài)。Q00Q03S1Q0141Q0100011Q034Q012Q032Q0234Q01240110011001有限自動機的應用在文本中查找字符串用于文本搜索識別關鍵字集合在Web和其它在線文本庫時代，一個常見的問題是，給定一個單詞集合，查找包含一個（或全部）單詞的所有文檔。搜索引擎是完成這個任務的一個專門的軟件，它對Web上出現(xiàn)的每個單詞（大約有一億種不同的英文單詞），保存這個單詞所有出現(xiàn)之處的列表。要用非常大的主存的計算機保持這些列表的最常見部分，以便隨時可用，允許許多人在瞬間搜索這些文檔。雖然在搜索引擎中常用的倒排索引技術沒有使用有窮自動機，但有許多有關的應用不適合使用倒排索引,但很適合于應用基于自動機的技術。適合應用自動機技術來搜索的特征是：所搜索的數(shù)據(jù)庫快速變化。例如：

（a）每一天，新聞分析員希望搜索當天在線的新聞文章來尋找有關話題。比如，金融分析員可能搜索他感興趣的股票代碼或公司名稱。

（b）“采購機器人”軟件希望搜索顧客要求的商品的當前價格?！皺C器人”從Web上獲得當前的目錄頁面，然后搜索這些頁面尋找提示具體商品價格的單詞。所搜索的文檔不能建立目錄。出于商業(yè)機密的考慮，有些公司（比如出版商）不愿意讓人輕易發(fā)現(xiàn)本公司銷售的所有書的所有頁面。實際上，在響應查詢的“一瞬間”才生成這些頁面。NFADFA2023/7/26483.4帶空移動的有限狀態(tài)自動機

接受語言{0n1m2k|n，m，k≥0}的NFA

2023/7/2649接受語言{0n1m2k|n，m，k≥0}的NFA是否可以構造成下圖所示的“ε-NFA

”？

其構造顯然比上圖所示的NFA更容易。當然還希望它們是等價的。它的δ函數(shù)是：

δ(q0,0)={q0}，δ(q1,1)={q1}，δ(q2,2)={q2}δ(q0,ε)={q1}，δ(q1,ε)={q2}，2023/7/2650帶空移動的不確定的有限狀態(tài)自動機(non-deterministicfiniteautomatonwithε-moves,ε-NFA)M=(Q，∑，δ，q0，F(xiàn))，Q、∑、q0、F的意義同DFA。

δ：Q×(∑∪{ε})2Q

2023/7/2651非空移動(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1、p2、…或者pm

，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。2023/7/2652空移動q∈Qδ(q，ε)={p1，p2，…，pm}表示M在狀態(tài)q不讀入任何字符，可以選擇地將狀態(tài)變成p1、p2、…或者pm

。也可以叫做M在狀態(tài)q做一個空移動(又可以稱為ε移動)，并且選擇地將狀態(tài)變成p1、p2、…或者pm。2023/7/2653例定理ε-NFA與NFA等價?？臻]包的定義在一個有ε轉移的有限窮自動機中，用ε-CLOSURE(q)表示狀態(tài)q的空閉包，它是下述定義的狀態(tài)集：(1)q在ε-CLOSURE(q)中；(2)若p在ε-CLOSURE(q)中，則δ(p,ε)也都在ε-CLOSURE(q)中；(3)重復(2)，直到ε-CLOSURE(q)中狀態(tài)不再增加為止。從轉移圖上看，ε-CLOSURE(q)就是從狀態(tài)q出發(fā)，沿著標有ε的有向邊所能達到的一切狀態(tài)所構成的集合（包括狀態(tài)q本身）。對于狀態(tài)集P的ε-CLOSURE， ε-CLOSURE(P)=ε-CLOSURE(q)。ε-CLOSURE(q0)={q0,q1,q2}ε-CLOSURE(q1)={q1,q2}。擴充轉移函數(shù)對于一個具有ε轉移的有限窮自動機，它的擴充轉移函數(shù)δ’定義如下：

δ’(q,ε)=ε-CLOSURE(q), δ’(q,wa)=ε-CLOSURE(P),P=δ(r,a)。其中q∈Q,a∈∑,w∈∑*。注意，擴充轉移函數(shù)δ’已經不是δ的簡單擴充，與δ完全不相同。帶空移動的自動機轉為不確定自動機00q00q1q2δ’(q0,0)=ε-CLOSURE(δ(δ’(q0,ε),0)) =ε-CLOSURE(δ({q0,q1,q2},0)) =ε-CLOSURE({q0}) ={q0,q1,q2}與δ(q0,0)=q0不同δ’(q0,1)=ε-CLOSURE(δ(δ’(q0,ε),1)) =ε-CLOSURE(δ({q0,q1,q2},1)) =ε-CLOSURE({q1}) ={q1,q2}0,10,1q00q1q2δ’(q0,2)=ε-CLOSURE(δ(δ’(q0,ε),2)) =ε-CLOSURE(δ({q0,q1,q2},2)) =ε-CLOSURE({q2})={q2}0,10,1,2q00q1q2δ’(q1,0)=ε-CLOSURE(δ(δ’(q1,ε),0))=ε-CLOSURE(δ({q1,q2},0))無定義 δ’(q1,1)=ε-CLOSURE(δ(δ’(q1,ε),1))=ε-CLOSURE(δ({q1,q2},1))=ε-CLOSURE({q1})={q1,q2}δ’(q1,2)=ε-CLOSURE(δ(δ’(q1,ε),2))=ε-CLOSURE(δ({q1,q2},2)) =ε-CLOSURE({q2})={q2}δ’(q2,0)=ε-CLOSURE(δ(δ’(q2,ε),0)) =ε-CLOSURE(δ({q2},0))無定義 δ’(q2,1)=ε-CLOSURE(δ(δ’(q2,ε),1))=ε-CLOSURE(δ({q2},1))無定義 δ’(