形式語言與自動機有窮自動機第一頁，共五十三頁，編輯于2023年，星期六第三章

有窮自動機1.1非形式化描述1.2有窮自動機的基本定義1.3非確定的有窮自動機1.4具有ε轉移的有窮自動機1.5有窮自動機的應用1.6具有輸出的有窮自動機（*)第二頁，共五十三頁，編輯于2023年，星期六2023/5/2921.1有窮狀態系統指針式鐘表共有12*60*60個狀態小時×分鐘×秒圍棋共有3361個狀態每一個格子：（空，黑，白）；格子數量：19行×19列某些電子產品中的開關電路，具有n個門的開關網絡有2n種狀態“網上購物”系統（示例：）第三頁，共五十三頁，編輯于2023年，星期六2023/5/2932007年圖靈獎模型檢驗（modelchecking）:基于自動機理論的形式化方法(formalmethods)E.ClarkEmersonSifakis第四頁，共五十三頁，編輯于2023年，星期六2023/5/2941.2有窮自動機的基本定義定義3.1一個有窮自動機(FiniteAutomata)簡稱FA，是一個五元組：M=(Q,∑,δ,q0,F)，其中（1）Q是有窮狀態集；（States）（2）∑是有窮的輸入字母表（Alphabet）（3）δ是轉移函數，它將Q×∑→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始狀態；（Initialstate）（5）FQ，是終結狀態集。（Acceptingstates）(終止狀態，接受狀態)上述定義的另一個說法：確定型的有窮自動機(DeterministicFiniteAutomata：DFA)第五頁，共五十三頁，編輯于2023年，星期六2023/5/295DFA例子q0q1q21000,11字母表：S

={0,1}狀態集：Q={q0,q1,q2}初始狀態：

q0終結狀態:F={q0,q1}狀態集輸入01q0q1q2q0q1q2q2q2q1轉換函數表d:

**→問題：1.接受什么特征的字符串？2.狀態q2起什么作用？第六頁，共五十三頁，編輯于2023年，星期六2023/5/296這兩個DFA所接受的字符串集合分別是什么？DFA例子q0q1baabS

={a,b}q0q1q2q3q4aaaaabbbbbS

={a,b}第七頁，共五十三頁，編輯于2023年，星期六2023/5/297設計一個DFA(字母表為{0,1}),接受如下字符串：設計一個DFA(字母表為{0,1}),接受如下特征的字符串：最多有三個1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,1第八頁，共五十三頁，編輯于2023年，星期六2023/5/298設計一個DFA(字母表為{0,1}),接受所有結尾是01的字符串。提示：DFA得記住讀入字符串的最后兩位。DFA例子qe01q0q1q00q10q01q1101010011100第九頁，共五十三頁，編輯于2023年，星期六2023/5/299設計一個DFA(字母表為{0,1}),接受所有結尾是101的字符串。DFA例子第十頁，共五十三頁，編輯于2023年，星期六2023/5/2910例3.1給出一個有窮自動機Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：轉移函數δ具體定義如下：

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

δ(q1,1)=q0

δ(q1,0)=q3

δ(q2,1)=q3

δ(q2,0)=q0

δ(q3,1)=q2

δ(q3,0)=q1→*DFA例子第十一頁，共五十三頁，編輯于2023年，星期六2023/5/2911有窮自動機的擴充定義定義3.2對于有窮自動機M=(Q，∑，δ，q0，F)，它的擴充轉移函數

,是從Q×∑*到Q的映射，其具體定義如下：

（1）(q,ε)=q；

（2）(q,wa)=δ((q,w),a)。

其中q∈Q，w∈∑*，a∈∑。例如，對于例3.1中的有窮自動機，就有： (q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)=δ(δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q2,1),0)=δ(q3,0)=q1。第十二頁，共五十三頁，編輯于2023年，星期六2023/5/2912有窮自動機的基本定義從δ到

的擴充是很自然的，δ就是

的特例（當|x|=1時）。今后在提到FA的轉移函數時，不再強調

這種寫法，一律用δ表示，即δ的第二個變元既可以是單個字符也可以是一個字符串。第十三頁，共五十三頁，編輯于2023年，星期六2023/5/2913有窮自動機模型開始時，“讀頭”指向帶上的第一個輸入符號，控制器中放的是FA的初始狀態。然后，依據轉移函數δ做動作：若控制器中的當前狀態是q，且“讀頭”指向帶上符號為a，則控制器中狀態將變成p=δ(q,a)，且“讀頭”向右移指向帶上下一個符號，如此可以繼續進行下去。(注意：讀頭不能回頭，只能一直向右移動)→*第十四頁，共五十三頁，編輯于2023年，星期六2023/5/2914有窮自動機的模型定義3.3給出FA：M=(Q,∑,δ,q0,F)，若δ(q0,x)=p∈F(x∈∑*)，則稱字符串x被M接受。進一步地，被M接受的全部字符串構成的集合，稱為被有窮自動機M接受的語言，并記為L(M)。用集合描述法就是 L(M)={x∣δ(q0,x)∈F}。FA所能接受的只是∑*的一部分子集，有很多∑*的子集是任何FA都不能接受的。第十五頁，共五十三頁，編輯于2023年，星期六2023/5/2915從給定集合構造接受該集合的FA例3.3：設計一個接受能被5整除的二進制數的FAM用qs表示初始狀態，用q0、q1、q2、q3、q4分別表示二進制數被5整除時余0（即能被5整除，所以它是終結狀態。）、余1、余2、余3、余4的狀態。第十六頁，共五十三頁，編輯于2023年，星期六2023/5/2916一個FA(字母表為{0,1}),接受所有結尾是101的字符串。能否給FA增加猜測選擇的能力？假設我們具有猜測何時輸入串還剩下三個字符的能力。

1.3非確定的有窮自動機(NFA)qdie101還剩三個字符010第十七頁，共五十三頁，編輯于2023年，星期六2023/5/2917NFA每個狀態對同樣的一個輸入字符，可能有0,1,或者多條轉換發生（"猜測"）.1010,1q0q1q2q3第十八頁，共五十三頁，編輯于2023年，星期六2023/5/2918NFA：可以進行猜測選擇1010,1q0q1q2q3狀態q0有兩個標記為1的轉換；讀入1,NFA可以選擇停留在q0，或者繼續往前到狀態q1第十九頁，共五十三頁，編輯于2023年，星期六2023/5/2919NFA：可以進行猜測選擇1010,1q0q1q2q3狀態q1對于輸入

1沒有相應的轉換；

q1上讀入1時,NFA就運行不下去了(die);而讀入0時候,NFA可以繼續到狀態q2；狀態q2類似的行為。第二十頁，共五十三頁，編輯于2023年，星期六2023/5/29201010,1q0q1q2q3q3沒有任何轉換出來；

q3上如果讀入0,1,NFA也運行進入死狀態。NFA：可以進行猜測選擇第二十一頁，共五十三頁，編輯于2023年，星期六2023/5/2921NFA：猜測的能力1010,1q0q1q2q3猜測是否已經到了最后三位字符的位置了？如果是，則猜測最后三位字符應該是與101相匹配判斷是否到達輸入字符串的最末端NFA的運行過程中某個時刻是會同時處于多個狀態中，只要輸入串x結束時NFA所處的多個狀態中至少有一個是接受狀態，就判斷NFA接受x。第二十二頁，共五十三頁，編輯于2023年，星期六2023/5/2922

NFA的形式化定義定義3.4一個非確定的有窮自動機(NondeterministicFiniteAutomata)簡記為NFA，是一個五元組 M=(Q,∑,δ,q0,F)

其中Q、∑、q0和F與確定的有窮自動機的含意相同，只是轉移函數δ的定義不同，它是從Q×∑→2Q（Q的冪集）上的映射。在FA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中轉移函數δ的取值是一個狀態集，即使只有一個狀態p，也要寫成集合形式{p}。第二十三頁，共五十三頁，編輯于2023年，星期六2023/5/2923

NFA的形式化定義定義3.5對于NFAM=(Q,∑,δ,q0,F)，它的擴充轉移函數

是從Q×∑*→2Q的映射，具體定義如下： (1)(q,ε)={q}, (2)(q,wa)={p|p∈δ(r,a),r∈(q,w)}。對于例3.4中的NFA，(q0,01001)的求值過程如下圖：第二十四頁，共五十三頁，編輯于2023年，星期六2023/5/2924NFA接受的語言定義3.7給出NFAM=(Q,∑,δ,q0,F)，若δ(q0,x)∩F非空（x∈∑*），則稱字符串x被M接受。被NFAM接受的全體字符串稱為M接受的語言，記作L(M)。也就是 L(M)={x∣x∈∑*,且δ(q0,x)∩F非空}。第二十五頁，共五十三頁，編輯于2023年，星期六2023/5/2925NFA與DFA的等價NFA能識別（接受）DFA所識別（接受）的所有語言。（為什么？）反過來成立嗎？任一個NFA都能轉換成一個DFA，二者所識別的語言是相等的。YES第二十六頁，共五十三頁，編輯于2023年，星期六2023/5/2926NFA→DFA:直觀的理解100,1q0q1q2NFA:DFA:1q0q0orq11q0orq21000第二十七頁，共五十三頁，編輯于2023年，星期六2023/5/2927NFA→DFA:子集構造法

(subsetconstruction)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?NFA中的任一個狀態子集都是所構造的DFA的一個狀態

第二十八頁，共五十三頁，編輯于2023年，星期六2023/5/2928NFA→DFA:狀態之間的轉換100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,1第二十九頁，共五十三頁，編輯于2023年，星期六2023/5/2929NFA→DFA:確定DFA接受狀態100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,1DFA中包含NFA接受狀態的子集狀態設為accepting第三十頁，共五十三頁，編輯于2023年，星期六2023/5/2930NFA→DFA:消除無用的狀態100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0}010101{q0,q1,q2}010{q1,q2}{q1}{q2}?01,1010,1將DFA中不可達的狀態消除掉。第三十一頁，共五十三頁，編輯于2023年，星期六2023/5/2931子集構造法的一般步驟NFADFA狀態q0,q1,…,qnφ,{q0},{q1},{q0,q1},…,{q0,…,qn}每個狀態都是NFA的一個子集。初始狀態q0{q0}轉換dd’({qi1,…,qik},a)=

d(qi1,a)∪…∪

d(qik,a)接受狀態Fí

QF’={S:S包含

F中至少一個狀態}

第三十二頁，共五十三頁，編輯于2023年，星期六2023/5/2932NFA-DFA等價性的形式化證明定理3.1設L是被一個非確定的有窮自動機接受的語言，則存在一個確定的有窮自動機也接受這個語言L。 證明

設

M=(Q,∑,δ,q0,F)是一個接受L的NFA，現在構造一個DFAM′=(Q′,∑,δ′,q0′,F′)，其中：

Q′=2Q,即Q的每一個子集作為Q′的一個狀態，若子集為{q1,q2,…,qk}，則Q′中狀態記為[q1,q2,…,qk]； q0′={q0}；

F′2Q:F′的每個元素至少包含F中的一個狀態；

δ′的定義為：δ′([q1,q2,…,qi],a)=[p1,p2,…,pj]當且僅當

δ（{q1,q2,…,qi},a）={p1,p2,…,pj}(a∈∑)。第三十三頁，共五十三頁，編輯于2023年，星期六2023/5/2933NFA-DFA等價性的形式化證明證明L(M′)=L(M)=L。先證一個更一般的命題：

δ′(q0’,x)=[q1,q2,…,qk] iffδ(q0,x)={q1,q2,…,qk}（x∈∑*）。 (3-1)

對x的長度∣x∣用歸納來證明。

歸納基礎

∣x∣=0，即x=ε。因為

δ′(q0′,ε)=q0′=[q0],

δ(q0,ε)={q0}。

根據δ′的定義。所以（3-1）式成立。

歸納步驟

設對于|x|≤m的輸入串（3-1）式成立，現在考慮長度為m+1的輸入串xa(x∈∑*，a∈∑)。因為一方面

δ′(q0′,xa)=δ′(δ′(q0′,x),a)，

（1）另一方面

δ(q0,xa)=δ(δ(q0,x),a)。

（2）第三十四頁，共五十三頁，編輯于2023年，星期六2023/5/2934NFA-DFA等價性的形式化證明由歸納法假設，因為x長度為m，以下（3）式成立，即δ′(q0′,x)=[p1,p2,…,pj]當且僅當δ(q0,x)={p1,p2,…,pj}。（3）

再由δ′的定義：

δ′([p1,p2,…,pj],a)=[r1,r2,…,rs]當且僅當

δ({p1,p2,…,pj},a)={r1,r2,…,rs}（4）

將（3），（4）代入（1），（2）兩式，即得出

δ′(q0′,xa)=[r1,r2,…,rs]當且僅當δ(q0,xa)={r1,r2,…,rs}。

從而（3-1）式得到證明。

有了（3-1）式之后，若[q1,q2,…,qk]∈F′,則q1,q2,…,qk

至少有一個在F中；反之，若{q1,q2,…,qk}中有一個狀態在F中，則[q1,q2,…,qk]∈F′。這就是說，M和M′接受的語言是相同的，即L(M′)=L(M)=L。定理證畢。這個定理不僅證明了NFA和DFA兩類自動機的等價性，而且還給出了從一個NFA構造與它等價的DFA的具體步驟，這種證明稱為構造性的證明方法。第三十五頁，共五十三頁，編輯于2023年，星期六2023/5/2935NFA-DFA等價構造的例子例3.5設M=({q0,q1},{0,1},δ,q0,{q1})是一個NFA，其中：

δ（q0,0）={q0,q1}, δ（q0,1）={q1},

δ（q1,0）=Φ, δ（q1,1）={q0,q1}。根據定理3.1，我們能構造出等價的DFA: M′=(Q,{0,1},δ′,[q0],F)

其中： Q={[q0],[q1],[q0,q1],Ф},F={[q1],[q0,q1]},

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

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

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

δ′(Φ,0)=Φ, δ′(Φ,1)=Φ。第三十六頁，共五十三頁，編輯于2023年，星期六2023/5/2936子集構造法的實際實現從狀態[q0]出發，通過狀態轉移函數δ′，逐步擴充狀態集；每一步僅對狀態集中新增加的狀態，才寫出狀態轉移函數；此過程一直繼續下去，直到不再增加新的狀態為止，最后就得到了DFA。例3.6將例3.4中的NFA化為等價的DFA，可按下述步驟構造：

第一步

從[q0]開始：

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

第二步

處理兩個新狀態[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]。

第三步

處理新增加的兩個狀態[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,q3,q2]。第三十七頁，共五十三頁，編輯于2023年，星期六2023/5/2937子集構造法的實際實現

第四步

處理新增加的兩個狀態[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]。

第五步

處理新增加的兩個狀態[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]。到這一步為止，不再增加新的狀態，所求的DFA只包含9個狀態。因為原來的NFA有5個狀態，若按定理3.1的構造方法，就要設25=32個狀態，是從初始狀態[q0]不能到達的，不必把這些狀態和相關的轉移函數包含到所求的DFA中去。第三十八頁，共五十三頁，編輯于2023年，星期六2023/5/29381.4具有ε轉移的有窮自動機該自動機的狀態集為{q0,q1,q2},輸入字母表為{0，1，2}。由初始狀態q0開始，當接到輸入符號0時，轉移到狀態q0本身，但不遇到任何符號（用ε表示）即可從q0轉移到q1，從q1到q2也有類似的情況。這種自動機在NFA的基礎上又增加了一種不確定性，它不僅在某些情況下有更簡潔表達能力，而且在證明一些理論問題時，更是不可缺少的工具。第三十九頁，共五十三頁，編輯于2023年，星期六2023/5/2939另一個ε-NFA的例子設計一個NFA識別語言：字符串要么包含偶數個0，或奇數個1；r0r11100evennumberof0ss0s10011oddnumberof1sq0e-transitions不需要讀入任何符號即可發生狀態轉換第四十頁，共五十三頁，編輯于2023年，星期六2023/5/2940具有ε轉移的有窮自動機定義3.8具有ε轉移的有窮自動機（簡稱ε-NFA）是一個五元組 M=(Q,∑,δ,q0,F)

其中Q,∑,q0,F的含義與一般的DFA或NFA相同，而δ是從

Q×(∑∪{ε})→2Q的映射。對于前面給出的自動機，它的δ函數是：

δ(q0,0)={q0}，

δ(q0,ε)={q1}，

δ(q1,1)={q1}，

δ(q1,ε)={q2}，

δ(q2,2)={q2}。凡是沒有寫出的δ，如δ(q0,1)，δ(q1,2)，δ(q2,1)等等，都是沒有定義的，這和一般的NFA相同。第四十一頁，共五十三頁，編輯于2023年，星期六2023/5/2941具有ε轉移的有窮自動機定義3.9在一個具有ε轉移的有窮自動機中，對于狀態q，它的ε-CLOSURE(q)是由下述規則定義的狀態集：

（1）q在ε-CLOSURE(q)中；

（2）若p在ε-CLOSURE(q)中，則δ(p,ε)也都在ε-CLOSURE(q)中；

（3）重復（2），直到ε-CLOSURE(q)中狀態不再增加為止。

進一步地，對于狀態集P的ε-CLOSURE，我們規定

ε-CLOSURE(P)=ε-CLOSURE(q)。所謂ε-CLOSURE(q)，從轉移圖上看，就是從狀態q出發，沿著標有ε的有向邊所能達到的一切狀態所構成的集合（包括狀態q本身）。所謂ε-CLOSURE(P)，就是對P中一切狀態q，分別求出ε-CLOSURE(q)，然后將這些狀態集求并而得的狀態集。例如，ε-CLOSURE(q0)={q0,q1,q2},ε-CLOSURE(q1)={q1,q2}。第四十二頁，共五十三頁，編輯于2023年，星期六2023/5/2942具有ε轉移的有窮自動機定義3.10對于一個具有ε轉移的有窮自動機，它的擴充轉移函數

定義如下：

（1）(q,ε)=ε-CLOSURE(q),

（2）(q,wa)=ε-CLOSURE(P),P=δ(r,a)。其中q∈Q,a∈∑,w∈∑*。例3.6考慮圖3.11中的自動機 (q0,0)=ε-CLOSURE(δ((q0,ε),0)) =ε-CLOSURE(δ({q0,q1,q2},0)) =ε-CLOSURE({q0})={q0,q1,q2}。 (q0,01)=ε-CLOSURE(δ((q0,0),1)) =ε-CLOSURE(δ({q0,q1,q2},1)) =ε-CLOSURE({q1})={q1,q2}。第四十三頁，共五十三頁，編輯于2023年，星期六2023/5/2943具有ε轉移的有窮自動機定義3.11對于一個具有ε轉移的有窮自動機M=(Q,∑,δ,q0,F)，它接受的語言定義為：

L(M)={w|d(q0,w)∩F非空}。定理3.2如果L被一個具有ε轉移的有窮自動機接受，則L也被一個不具有ε轉移的NFA接受。第四十四頁，共五十三頁，編輯于2023年，星期六2023/5/2944具有ε轉移的有窮自動機證明(定理3.2)

設M=(Q,∑,δ,q0,F)是具有ε轉移的有窮自動機，且L(M)=L?，F在構造M′=(Q,∑,δ′,q0,F′)是一個不具有ε轉移的NFA，其中：

δ′(q,a)=δ(q,a),q∈Q,a∈∑。

如果ε-CLOSURE({q0})∩F非空，則F′=F∪{q0}；否則，F′=F。

下面我們將對∣x∣作歸納法來證明下式：

δ′(q0,x)=(q0,x)。

（3-2）

注意當x=ε時，（3-2）式不一定成立，因為δ′(q0,ε)={q0}，而

(q0,ε)=ε-CLOSURE({q0})。所以只能對∣x∣≥1證明(3-2)式成立。

歸納基礎

∣x∣=1，即x=a(a∈∑)。根據δ′的定義，（3-2）式顯然成立。第四十五頁，共五十三頁，編輯于2023年，星期六2023/5/2945具有ε轉移的有窮自動機歸納步驟

設∣x∣=m(m≥1)時，（3-2）式成立，現在要證當∣x∣=m+1時，（3-2）式成立。

設x=wa(a∈∑,∣w∣=m)，則由δ′的定義：

δ′(q0,wa)=δ′(δ′(q0,w)，a)。

（1）

由歸納法假設，δ′(q0,w)=(q0,w)。設(q0,w)=P，則由δ′的擴充定義：

δ′(P,a)=δ′(q,a)=(q,a)。

（2）

另一方面，由

的定義： (q0,wa)=ε-CLOSURE((q,a))。

第四十六頁，共五十三頁，編輯于2023年，星期六2023/5/2946具有ε轉移的有窮自動機

我們對（2）式的右部再進一步推導，得出 (q,a)=ε-CLOSURE(δ(ε-CLOSURE（q）,a)) =ε-CLOSURE(δ(ε-CLOSURE（q）,a)) =ε-CLOSURE(δ(q,a))。

（4）

其中最后一步簡化是因為對P=(q0,w)中的任何狀態q,ε-CLOSURE(q)已經在P中，所以在對P中狀態求和的情況下，可以將ε-CLOSURE(q)用q來代替。

綜合(1),(2),(3),(4)式，最后得出

δ′(q0,wa)=(q0,wa)。

到這里，我們用歸納法證明了對一切x(∣x∣≥1)，（3-2）式成立。第四十七頁，共五十三頁，編輯于2023年，星期六2023/5/2947具有ε轉移的有窮自動機為了完成定理的證明，我們要證：

對一切x∈∑*,δ′(q,x)∩F’非空，當且僅當(q,x)∩F非空。對x=ε和x≠ε分兩種情況考慮