形式語言與自動機 有窮自動機

1形式語言與自動機

第三章有窮自動機南京航空航天大學計算機科學與技術學院胡軍hujun.nju@139.com01二月2023南京航空航天大學計算機學院胡軍2第三章

有窮自動機1.1非形式化描述1.2有窮自動機的基本定義1.3非確定的有窮自動機1.4具有ε轉移的有窮自動機1.5有窮自動機的應用1.6具有輸出的有窮自動機（*)01二月2023南京航空航天大學計算機學院胡軍31.1有窮狀態(tài)系統(tǒng)指針式鐘表共有12*60*60個狀態(tài)小時×分鐘×秒圍棋共有3361個狀態(tài)每一個格子：（空，黑，白）；格子數(shù)量：19行×19列某些電子產品中的開關電路，具有n個門的開關網(wǎng)絡有2n種狀態(tài)“網(wǎng)上購物”系統(tǒng)（示例：）01二月2023南京航空航天大學計算機學院胡軍42007年圖靈獎模型檢驗（modelchecking）:基于自動機理論的形式化方法(formalmethods)E.ClarkEmersonSifakis01二月2023南京航空航天大學計算機學院胡軍51.2有窮自動機的基本定義定義3.1一個有窮自動機(FiniteAutomata)簡稱FA，是一個五元組：M=(Q,∑,δ,q0,F)，其中（1）Q是有窮狀態(tài)集；（States）（2）∑是有窮的輸入字母表（Alphabet）（3）δ是轉移函數(shù)，它將Q×∑→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始狀態(tài)；（Initialstate）（5）FQ，是終結狀態(tài)集。（Acceptingstates）(終止狀態(tài)，接受狀態(tài))上述定義的另一個說法：確定型的有窮自動機(DeterministicFiniteAutomata：DFA)01二月2023南京航空航天大學計算機學院胡軍6DFA例子q0q1q21000,11字母表：S

={0,1}狀態(tài)集：Q={q0,q1,q2}初始狀態(tài)：

q0終結狀態(tài):F={q0,q1}狀態(tài)集輸入01q0q1q2q0q1q2q2q2q1轉換函數(shù)表d:

**→問題：1.接受什么特征的字符串？2.狀態(tài)q2起什么作用？01二月2023南京航空航天大學計算機學院胡軍7這兩個DFA所接受的字符串集合分別是什么？DFA例子q0q1baabS

={a,b}q0q1q2q3q4aaaaabbbbbS

={a,b}01二月2023南京航空航天大學計算機學院胡軍8設計一個DFA(字母表為{0,1}),接受如下字符串：設計一個DFA(字母表為{0,1}),接受如下特征的字符串：最多有三個1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,101二月2023南京航空航天大學計算機學院胡軍9設計一個DFA(字母表為{0,1}),接受所有結尾是01的字符串。提示：DFA得記住讀入字符串的最后兩位。DFA例子qe01q0q1q00q10q01q110101001110001二月2023南京航空航天大學計算機學院胡軍10設計一個DFA(字母表為{0,1}),接受所有結尾是101的字符串。DFA例子01二月2023南京航空航天大學計算機學院胡軍11例3.1給出一個有窮自動機Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：轉移函數(shù)δ具體定義如下：

δ(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例子01二月2023南京航空航天大學計算機學院胡軍12有窮自動機的擴充定義定義3.2對于有窮自動機M=(Q，∑，δ，q0，F(xiàn))，它的擴充轉移函數(shù)

,是從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。01二月2023南京航空航天大學計算機學院胡軍13有窮自動機的基本定義從δ到

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

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

這種寫法，一律用δ表示，即δ的第二個變元既可以是單個字符也可以是一個字符串。01二月2023南京航空航天大學計算機學院胡軍14有窮自動機模型開始時，“讀頭”指向帶上的第一個輸入符號，控制器中放的是FA的初始狀態(tài)。然后，依據(jù)轉移函數(shù)δ做動作：若控制器中的當前狀態(tài)是q，且“讀頭”指向帶上符號為a，則控制器中狀態(tài)將變成p=δ(q,a)，且“讀頭”向右移指向帶上下一個符號，如此可以繼續(xù)進行下去。(注意：讀頭不能回頭，只能一直向右移動)→*01二月2023南京航空航天大學計算機學院胡軍15有窮自動機的模型定義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都不能接受的。01二月2023南京航空航天大學計算機學院胡軍16從給定集合構造接受該集合的FA例3.3：設計一個接受能被5整除的二進制數(shù)的FAM用qs表示初始狀態(tài)，用q0、q1、q2、q3、q4分別表示二進制數(shù)被5整除時余0（即能被5整除，所以它是終結狀態(tài)。）、余1、余2、余3、余4的狀態(tài)。01二月2023南京航空航天大學計算機學院胡軍17一個FA(字母表為{0,1}),接受所有結尾是101的字符串。能否給FA增加猜測選擇的能力？假設我們具有猜測何時輸入串還剩下三個字符的能力。

1.3非確定的有窮自動機(NFA)qdie101還剩三個字符01001二月2023南京航空航天大學計算機學院胡軍18NFA每個狀態(tài)對同樣的一個輸入字符，可能有0,1,或者多條轉換發(fā)生（"猜測"）.1010,1q0q1q2q301二月2023南京航空航天大學計算機學院胡軍19NFA：可以進行猜測選擇1010,1q0q1q2q3狀態(tài)q0有兩個標記為1的轉換；讀入1,NFA可以選擇停留在q0，或者繼續(xù)往前到狀態(tài)q101二月2023南京航空航天大學計算機學院胡軍20NFA：可以進行猜測選擇1010,1q0q1q2q3狀態(tài)q1對于輸入

1沒有相應的轉換；

q1上讀入1時,NFA就運行不下去了(die);而讀入0時候,NFA可以繼續(xù)到狀態(tài)q2；狀態(tài)q2類似的行為。01二月2023南京航空航天大學計算機學院胡軍211010,1q0q1q2q3q3沒有任何轉換出來；

q3上如果讀入0,1,NFA也運行進入死狀態(tài)。NFA：可以進行猜測選擇01二月2023南京航空航天大學計算機學院胡軍22NFA：猜測的能力1010,1q0q1q2q3猜測是否已經(jīng)到了最后三位字符的位置了？如果是，則猜測最后三位字符應該是與101相匹配判斷是否到達輸入字符串的最末端NFA的運行過程中某個時刻是會同時處于多個狀態(tài)中，只要輸入串x結束時NFA所處的多個狀態(tài)中至少有一個是接受狀態(tài)，就判斷NFA接受x。01二月2023南京航空航天大學計算機學院胡軍23

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

其中Q、∑、q0和F與確定的有窮自動機的含意相同，只是轉移函數(shù)δ的定義不同，它是從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中轉移函數(shù)δ的取值是一個狀態(tài)集，即使只有一個狀態(tài)p，也要寫成集合形式{p}。01二月2023南京航空航天大學計算機學院胡軍24

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

是從Q×∑*→2Q的映射，具體定義如下： (1)(q,ε)={q}, (2)(q,wa)={p|p∈δ(r,a),r∈(q,w)}。對于例3.4中的NFA，(q0,01001)的求值過程如下圖：01二月2023南京航空航天大學計算機學院胡軍25NFA接受的語言定義3.7給出NFAM=(Q,∑,δ,q0,F)，若δ(q0,x)∩F非空（x∈∑*），則稱字符串x被M接受。被NFAM接受的全體字符串稱為M接受的語言，記作L(M)。也就是 L(M)={x∣x∈∑*,且δ(q0,x)∩F非空}。01二月2023南京航空航天大學計算機學院胡軍26NFA與DFA的等價NFA能識別（接受）DFA所識別（接受）的所有語言。（為什么？）反過來成立嗎？任一個NFA都能轉換成一個DFA，二者所識別的語言是相等的。YES01二月2023南京航空航天大學計算機學院胡軍27NFA→DFA:直觀的理解100,1q0q1q2NFA:DFA:1q0q0orq11q0orq2100001二月2023南京航空航天大學計算機學院胡軍28NFA→DFA:子集構造法

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

01二月2023南京航空航天大學計算機學院胡軍29NFA→DFA:狀態(tài)之間的轉換100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,101二月2023南京航空航天大學計算機學院胡軍30NFA→DFA:確定DFA接受狀態(tài)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}?01010,1010101010,1DFA中包含NFA接受狀態(tài)的子集狀態(tài)設為accepting01二月2023南京航空航天大學計算機學院胡軍31NFA→DFA:消除無用的狀態(tài)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0}010101{q0,q1,q2}010{q1,q2}{q1}{q2}?01,1010,1將DFA中不可達的狀態(tài)消除掉。01二月2023南京航空航天大學計算機學院胡軍32子集構造法的一般步驟NFADFA狀態(tài)q0,q1,…,qnφ,{q0},{q1},{q0,q1},…,{q0,…,qn}每個狀態(tài)都是NFA的一個子集。初始狀態(tài)q0{q0}轉換dd’({qi1,…,qik},a)=

d(qi1,a)∪…∪

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

QF’={S:S包含

F中至少一個狀態(tài)}

01二月2023南京航空航天大學計算機學院胡軍33NFA-DFA等價性的形式化證明定理3.1設L是被一個非確定的有窮自動機接受的語言，則存在一個確定的有窮自動機也接受這個語言L。 證明

設

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

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

F′2Q:F′的每個元素至少包含F(xiàn)中的一個狀態(tài)；

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

δ（{q1,q2,…,qi},a）={p1,p2,…,pj}(a∈∑)。01二月2023南京航空航天大學計算機學院胡軍34NFA-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}。

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

歸納步驟

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

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

（1）另一方面

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

（2）01二月2023南京航空航天大學計算機學院胡軍35NFA-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}中有一個狀態(tài)在F中，則[q1,q2,…,qk]∈F′。這就是說，M和M′接受的語言是相同的，即L(M′)=L(M)=L。定理證畢。這個定理不僅證明了NFA和DFA兩類自動機的等價性，而且還給出了從一個NFA構造與它等價的DFA的具體步驟，這種證明稱為構造性的證明方法。01二月2023南京航空航天大學計算機學院胡軍36NFA-DFA等價構造的例子例3.5設M=({q0,q1},{0,1},δ,q0,{q1})是一個NFA，其中：

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

δ（q1,0）=Φ, δ（q1,1）={q0,q1}。根據(jù)定理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)=Φ。01二月2023南京航空航天大學計算機學院胡軍37子集構造法的實際實現(xiàn)從狀態(tài)[q0]出發(fā)，通過狀態(tài)轉移函數(shù)δ′，逐步擴充狀態(tài)集；每一步僅對狀態(tài)集中新增加的狀態(tài)，才寫出狀態(tài)轉移函數(shù)；此過程一直繼續(xù)下去，直到不再增加新的狀態(tài)為止，最后就得到了DFA。例3.6將例3.4中的NFA化為等價的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,q3,q2]。01二月2023南京航空航天大學計算機學院胡軍38子集構造法的實際實現(xiàn)

第四步

處理新增加的兩個狀態(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)。因為原來的NFA有5個狀態(tài)，若按定理3.1的構造方法，就要設25=32個狀態(tài)，是從初始狀態(tài)[q0]不能到達的，不必把這些狀態(tài)和相關的轉移函數(shù)包含到所求的DFA中去。01二月2023南京航空航天大學計算機學院胡軍391.4具有ε轉移的有窮自動機該自動機的狀態(tài)集為{q0,q1,q2},輸入字母表為{0，1，2}。由初始狀態(tài)q0開始，當接到輸入符號0時，轉移到狀態(tài)q0本身，但不遇到任何符號（用ε表示）即可從q0轉移到q1，從q1到q2也有類似的情況。這種自動機在NFA的基礎上又增加了一種不確定性，它不僅在某些情況下有更簡潔表達能力，而且在證明一些理論問題時，更是不可缺少的工具。01二月2023南京航空航天大學計算機學院胡軍40另一個ε-NFA的例子設計一個NFA識別語言：字符串要么包含偶數(shù)個0，或奇數(shù)個1；r0r11100evennumberof0ss0s10011oddnumberof1sq0e-transitions不需要讀入任何符號即可發(fā)生狀態(tài)轉換01二月2023南京航空航天大學計算機學院胡軍41具有ε轉移的有窮自動機定義3.8具有ε轉移的有窮自動機（簡稱ε-NFA）是一個五元組 M=(Q,∑,δ,q0,F)

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

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

δ(q0,0)={q0}，

δ(q0,ε)={q1}，

δ(q1,1)={q1}，

δ(q1,ε)={q2}，

δ(q2,2)={q2}。凡是沒有寫出的δ，如δ(q0,1)，δ(q1,2)，δ(q2,1)等等，都是沒有定義的，這和一般的NFA相同。01二月2023南京航空航天大學計算機學院胡軍42具有ε轉移的有窮自動機定義3.9在一個具有ε轉移的有窮自動機中，對于狀態(tài)q，它的ε-CLOSURE(q)是由下述規(guī)則定義的狀態(tài)集：

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

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

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

進一步地，對于狀態(tài)集P的ε-CLOSURE，我們規(guī)定

ε-CLOSURE(P)=ε-CLOSURE(q)。所謂ε-CLOSURE(q)，從轉移圖上看，就是從狀態(tài)q出發(fā)，沿著標有ε的有向邊所能達到的一切狀態(tài)所構成的集合（包括狀態(tài)q本身）。所謂ε-CLOSURE(P)，就是對P中一切狀態(tài)q，分別求出ε-CLOSURE(q)，然后將這些狀態(tài)集求并而得的狀態(tài)集。例如，ε-CLOSURE(q0)={q0,q1,q2},ε-CLOSURE(q1)={q1,q2}。01二月2023南京航空航天大學計算機學院胡軍43具有ε轉移的有窮自動機定義3.10對于一個具有ε轉移的有窮自動機，它的擴充轉移函數(shù)

定義如下：

（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}。01二月2023南京航空航天大學計算機學院胡軍44具有ε轉移的有窮自動機定義3.11對于一個具有ε轉移的有窮自動機M=(Q,∑,δ,q0,F)，它接受的語言定義為：

L(M)={w|d(q0,w)∩F非空}。定理3.2如果L被一個具有ε轉移的有窮自動機接受，則L也被一個不具有ε轉移的NFA接受。01二月2023南京航空航天大學計算機學院胡軍45具有ε轉移的有窮自動機證明(定理3.2)

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

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

如果ε-CLOSURE({q0})∩F非空，則F′=F∪{q0}；否則，F(xiàn)′=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∈∑)。根據(jù)δ′的定義，（3-2）式顯然成立。01二月2023南京航空航天大學計算機學院胡軍46具有ε轉移的有窮自動機歸納步驟

設∣x∣=m(m≥1)時，（3-2）式成立，現(xiàn)在要證當∣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))。

01二月2023南京航空航天大學計算機學院胡軍47具有ε轉移的有窮自動機

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

（4）

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

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

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

到這里，我們用歸納法證明了對一切x(∣x∣≥1)，（3-2）式成立。01二月2023南京航空航天大學計算機學院胡軍48具有ε轉移的有窮自動機為了完成定理的證明，我們要證：

對一切x∈∑*,δ′(q,x)∩F’非空，當且僅當(q,x)∩F非空。對x=ε和x≠ε分兩種情況考慮。首先，當x=ε時，若M接受它，則ε-CLOSURE(q0)至少包含F(xiàn)中的一個狀態(tài)，由F′的定義，則q0在F′中，那么M′也接受ε。反之，若M′接受ε，因為M′是一個不具有ε轉移的NFA，則q0必須在F′中。進一步分析，若q0也在F中，則M自