【正文】 ∣ x∣ 作歸納法來證明下式： δ180。(q0,x) = (q0,x)。 （ 32） 注意當 x=ε時，（ 32）式不一定成立，因為 δ180。(q0,ε)={q0}，而 (q0,ε)=εCLOSURE({q0})。所以只能對 ∣ x∣ ≥1證明 (32)式成立。 歸納基礎 ∣ x∣ = 1，即 x=a(a∈ ∑)。根據(jù) δ180。的定義，（ 32）式顯然 成立。 d?d?2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 46 具有 ε轉移的有窮自動機 ? 歸納步驟 設 ∣ x∣ =m (m≥1)時，（ 32）式成立，現(xiàn)在要證當∣ x∣ =m+1時，（ 32）式成立。 設 x = wa (a∈ ∑,∣ w∣ =m)，則由 δ180。的定義： δ180。(q0,wa) = δ180。(δ180。(q0,w)， a)。 （ 1） 由歸納法假設， δ180。(q0,w)= (q0,w)。設 (q0,w)=P，則由 δ180。的擴充定義： δ180。(P,a) = δ180。(q,a) = (q,a)。 （ 2） 另一方面，由 的定義： (q0,wa)=εCLOSURE( (q,a))。 d? d?d?d?d? d?Pq?? Pq??Pq??2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 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)式，最后得出 δ180。(q0,wa)= (q0,wa)。 到這里，我們用歸納法證明了對一切 x(∣ x∣ ≥1)，（ 32）式成 立。 Pq??Pq??Pq??Pq??d?d?d?2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 48 具有 ε轉移的有窮自動機 ? 為了完成定理的證明，我們要證： 對一切 x∈ ∑*, δ180。(q,x)∩ F’非空，當且僅當 (q,x)∩ F非空。 ? 對 x=ε和 x≠ε分兩種情況考慮。首先，當 x=ε時，若 M接受它，則εCLOSURE(q0)至少包含 F中的一個狀態(tài)，由 F180。的定義，則 q0在F180。中，那么 M180。也接受 ε。反之，若 M180。接受 ε，因為 M180。是一個不具有 ε轉移的 NFA，則 q0必須在 F180。中。進一步分析，若 q0也在 F中，則 M自然接受 ε；若 q0不在 F中，由 F180。的定義，則 εCLOSURE(q0)至少包含 F中的一個狀態(tài)，這也表示 M接受 ε。 d?2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 49 具有 ε轉移的有窮自動機 ? 再考慮 x≠ε的情況。設 M接受 x，即 (q0,x)包含 F中的一個狀態(tài)，則由（ 32）式， δ180。(q0,x)也包含 F中的同一個狀態(tài)，而此狀態(tài)自然也在 F180。中，即 M180。也接受 x 。反之，設 M180。接受 x，若 δ180。(q0,x)包含 F180。中的非 q0狀態(tài)（ F中的一個狀態(tài)），則由（ 32）式， (q0,x)也包含 F中的這個狀態(tài)，即 M也接受 x 。但是，若 δ180。(q0,x)包含 q0，且 q0不在 F中，則根據(jù) F180。的定義，此時必有 εCLOSURE(q0)∩ F非空。再由（ 32）式， (q0,x)也包含 q0，并進而包含 εCLOSURE(q0)，因此， (q0,x)∩ F非空，即 M也接受 x。定理證完。 d?d?d?d?2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 50 有窮自動機的應用 ? 在文本中查找字符串 ? 用于文本搜索的非確定的有窮自動機 ? 識別關鍵字集合的 DFA 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 51 在文本中查找字符串 ? 在 Web和其它在線文本庫時代，一個常見的問題是， 給定一個單詞集合，查找包含一個（或全部）單詞的所有文檔 。搜索引擎是完成這個任務的一個專門的軟件，它對 Web上出現(xiàn)的每個單詞（大約有一億種不同的英文單詞），保存這個單詞所有出現(xiàn)之處的列表。要用非常大的主存的計算機保持這些列表的最常見部分，以便隨時可用，允許許多人在瞬間搜索這些文檔。 ? 雖然在搜索引擎中常用的倒排索引技術沒有使用有窮自動機，但有許多有關的應用不適合使用倒排索引 ,但很適合于應用基于自動機的技術。 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 52 用于文本搜索的非確定的有窮自動機 ? 例 假設要設計一個識別單詞 web和 ebay出現(xiàn)的 NFA,用上述辦法設計出的 NFA如圖 。其中狀態(tài) 1是初始狀態(tài)，用符號 ∑表示 ∑中所有的字符。狀態(tài) 2到狀態(tài) 4完成識別 web的任務，狀態(tài) 5到狀態(tài) 8完成識別 ebay的任務。 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 53 用于文本搜索的非確定的有窮自動機 ? 當然這個 NFA還不是程序，對于這個 NFA的實現(xiàn)，主要有兩種方法： ① 寫一個程序來模擬這個 NFA，計算出讀入每個輸入字符后所處的狀態(tài)的集合，檢查什么時候達到終結狀態(tài)（參見圖 ）。 ② 用子集構造法將這個 NFA化為等價的 DFA。然后用程序直接模擬這個 DFA。 ? 某些文本處理程序?qū)嶋H上混合采用這兩種方法，但我們傾向于第（ 2）種方法。因為在這種特殊情況下從 NFA轉換為 DFA是容易的，而且保證不增加狀態(tài)數(shù)。 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 54 從 NFA轉化成的 DFA ? NFA： 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 55 從 NFA轉化成的 DFA ? DFA： 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍 56 ? 課后作業(yè)： ? （ 1）（ 2）（ 3），用 JFLAP完成。 ? ? （ 1）（ 2）， 用 JFLAP完成。 2022年 2月 15日星期二 南京航空航天大學計算機學院 胡軍