-
冪集構造
鎖定
- 中文名
- 冪集構造
- 特 點
- 靈活性
- 性 質
- 計算理論
- 領 域
- 計算機
冪集構造簡介
冪集構造在理論上的重要性源於它確立了NFA儘管有額外的靈活性,它不能識別不能被任何DFA識別的任何語言。在實踐中的重要性源於它把易於構造的NFA轉換成了更有效執行的DFA。但是如果NFA有n個狀態,結果的DFA可能有最多2個狀態,這種指數增長有時使這種構造對於大NFA而言是不實際的。
[1]
冪集構造動機
回想一下,NFA除了特定節點可能有“分支”引出同時前進的多個路徑之外,它和DFA是一樣的。NFA將接受輸入字符串,如果在計算完成的時候它的路徑之一結束於一個接受狀態。如果它的所有路徑都失敗,它就拒絕輸入字符串。例如,如果我們在狀態2而下一個輸入符號是1,機器分支,行進到狀態2和4二者。
注意不管NFA從一個狀態中引出有多少不同的路徑,它們每個在看到一個字符之後都必定到達n個狀態中的一個。因此,給定以前的選擇序列,我們可以簡潔的總結NFA當前格局(configuration)為它在那個時刻可能處於的狀態的集合。此外,我們如果我們知道NFA當前處在的狀態的集合,我們可以指出基於下一個輸入符號我們可以訪問哪個狀態集合。這就是算法的關鍵。
[1]
冪集構造定義DFA
我們來概括上述過程。定義一個DFA有四個重要問題必須回答:
- 什麼是狀態?
- 那些狀態是接收狀態?
- 什麼狀態是開始狀態?
- 在哪裏放置邊並做什麼標記?
我需要一個DFA的狀態來描述NFA的每個可能格局。但是一般的説,NFA在任何給定點都可以處在它的狀態的任何子集中。集合S的子集的集合叫做冪集,並寫為P(S),我們定義在DFA中的狀態集合是在NFA中狀態集合的冪集。這回答了第一個問題。
我們已經提及瞭如果在NFA中任何並行路徑在結束時處在接受狀態,則NFA接受輸入字符串。DFA可以通過在包含某NFA接受狀態之一的任何狀態中接受輸入來模擬。這回答了第二個問題。
對於第三個問題。假設給NFA的輸入字符串是空串。在它必須停止之前它可以訪問什麼狀態?她不能沿着標記了輸入符號的任何邊前進,但它可以沿不消耗任何輸入的ε邊前進。因為它可以到達從開始狀態之使用ε表到達的任何狀態。這個狀態集合形式上叫做開始狀態的ε-閉包。因為我們的DFA在給予空輸入串的時候時候除了立即停止不能做任何事情,我們必須保證DFA的開始狀態包括所有可能的這些NFA狀態。我們通過設置DFA的開始狀態為NFA開始狀態的ε-閉包來完成。
最後,我們使用類似的想法回答第四個問題。假設我們處在DFA的特定狀態中(就是説,NFA狀態的特定集合中)我們看到了特定輸入符號。我們想知道下DFA的一個狀態是什麼。這精確的是從當前的NFA狀態集合基於這個輸入符號可以訪問到NFA狀態的集合。要得出這個集合,我們查看在每個一個NFA當前狀態,並詢問“給定這個輸入符號,從這能到哪裏呢?”。答案就是可沿着標記着這個輸入符號的任何單一邊,和任何數目的ε邊前進。我們以這種方式查找並發現我們可以觸及的所有節點,並把它們加入下一個狀態的節點集合中。當我們對所有當前NFA狀態完成了這個工作,我們就有了對應於特定DFA狀態的NFA狀態的集合,我們增加從當前DFA狀態到這個狀態的標記着這個輸入符號的一個邊。
一旦我們已經對所有DFA狀態和所有符號完成了這個過程,我們的DFA就完成了。結果的機器跟蹤了NFA在輸入字符串的每個時刻訪問的狀態的集合。但是,這個機器是非常大的:因為每個NFA的狀態集合可能包含任何特定NFA狀態,總共有2這種集合,它們都是DFA可能有的節點。如果我們如例子中這樣只建立必須的節點,我們經常會建立一個非常小的DFA的。不管如何,仍有必須所有2個狀態的情況,這是不可避免的。
[2]
冪集構造形式定義
設M= (S, Σ,T,s,A)是非確定有限狀態自動機。
定義5-元組Md= (Sd,Σd,Td,sd,Ad),這裏的
- Sd=P(S)
- Σd= Σ
- sd=Cε(s)
- Td(q, a)=Cε(∪∀ r ∈ qT(r, a)) ∀q ∈Sd, ∀ a ∈ Σ
- Ad= {q|q∈Sd∧q∩A≠ ∅}
P(S)是S的冪集;
Cε(q)是q的ε-閉包,就是説從q經過一次或多次ε-轉移可到達的所有狀態的集合。
冪集構造計算理論
- 要用多少時間、要用多少存儲(即計算複雜性理論)
這三方面的問題可以用一個問題來總括:“電腦的基礎能力及限制到什麼程度?”
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:4次歷史版本
- 最近更新: lr274481343