Ⅰ 如題，編譯原理中為什麼要將NFA轉化為DFA
對DFA來說，一個輸入必然對應唯一的路徑與結果，而這正是我們設計編譯器所需要的。
如果從一個狀態經過同樣的一個輸入可以通過兩條或更多路徑達到不同的狀態，我們的編譯器就會迷惑（不知道怎麼辦），只能通過窮舉測試每個狀態是否可行，而窮舉演算法的效率通常都很低下。
DFA的最簡化是有固定演算法的，NFA有沒有我不知道，通常最簡化之後的DFA要比NFA簡單得多
Ⅱ 有窮自動機DFA&NFA (學習筆記)
有窮自動機（DFA和NFA）是一個識別器，它對每個輸入字元進行識別和判斷，以確定其能到達的最終狀態或狀態集。有窮自動機分為兩類：不確定的有窮自動機NFA（Non-Deeterministic Finite State Automata）和確定的有窮自動機DFA（Deterministic Finite State Automata）。以紅綠燈系統為例，紅燈（R）、綠燈（G）和黃燈（Y）分別代表不同狀態，以零售機為例，它可以接受五角和一塊的硬幣，但需要累計到至少3元才能進行選擇。
在介紹DFA和NFA之前，先介紹一些基本概念。字母表（Alphabet）是符號的有限集合，如{a, b, ... , x, m}，字元串（String）是建立在字母表上的有限符號序列，如對於字母表Σ={a, b, c}，「ababc」是一個字元串，而語言（Language）是建立在字母表上的多個字元串的集合，如{ababc, ab, bc, ..}，句子（Sentence）是語言集合中的元素（字元串）的另一個稱呼。
DFA是確定的有窮自動機，其狀態間轉換的公式為：狀態 x 輸入字元 --> 狀態。DFA的定義包含5個部分：Σ（字母表），S（狀態集合），s0（初始狀態），F（最終狀態），N（轉換函數）。在DFA中，「確定」意味著對於一個輸入字元，只有唯一的可能狀態。例如，從狀態S0讀取符號0之後的狀態為S1，即N (S0, 0) = S1，進一步讀取符號1之後的狀態為S2，即N (N (S0, 0), 1) = S2。重要定理指出，對於S中所有的狀態s，所有Σ*中的字元串α，β，有N*(s, αβ) = N*(N*(s, α), β)。最終狀態公式用於描述從任意一個狀態，經過一個字元串到達的最終狀態的所有可能情況。自動機等同是指如果兩個自動機接受相同的語言，那麼它們被認為是相等的。狀態等同意味著對於所有的輸入字元串w，有且只有N*(Sk,w) ∈ F 並且N*(Sk,w) ∈ F，其中F是最終狀態的集合，注意非終止狀態永遠不可能與終止狀態等同。狀態消除是簡化自動機的一種方法，包括等同狀態消除和無法到達的狀態消除。
NFA（不確定的有窮自動機）對一個輸入符號，可能有兩種或兩種以上的狀態。與DFA的主要區別在於DFA沒有輸入空串之上的轉換動作，而NFA對於一個特定的符號輸入，可能得到一個狀態集。NFA的定義與DFA相同。對於輸入字元串w，如果存在狀態s屬於F（最終狀態集），滿足R*(s0, w, s)，則w被自動機接受。存在定理指出，如果語言L被一個NFA接受，那麼一定存在一些DFA也接受這一語言L。
總體而言，DFA和NFA是用於識別語言的自動機模型。雖然NFA在狀態轉換上具有不確定性，但可以通過轉換演算法將NFA轉換為等效的DFA。DFA在確定性方面提供了更清晰的操作流程，而NFA則提供了更多靈活的路徑選擇。理解這兩種自動機對於編譯學習者來說是至關重要的。
Ⅲ NFA轉DFA的子集構造(subset construction)演算法
之前 學習編譯原理的時候老師有講過 子集構造法 ，當時我以為自己聽懂了，信心滿滿。可是這兩天我做了一些題目，發現自己實際上還是太嫩了，學習浮於表面。之後又重新看了龍書和虎書，對子集構造法有了更深層次的了解。特此發出一篇文章分享我的經驗。
概念是我們學習編譯原理的重中之重，雖然他很晦澀難懂，但我有必要將其放在最開始。
虎書的概念更偏向於理論化，我當時看的時候一頭霧水，但是不要擔心， 之後會一點一點解釋的 。
首先 ，我們形式化定義 閉包如下：
現在 ，假設我們位於由 NFA 狀態 組成的集合 中。從 中的狀態出發，輸入符號 ，將到達 NFA 新的狀態集；我們稱這個狀態集為 ：
利用 能更形式化地寫出 NFA 模擬演算法。如果初態是 ，輸入字元串是 ，則演算法為：
有了 和 演算法，就能構造出 DFA ， DFA 的狀態 就是 。抽象而言，如果 則存在一條從 到 的標記為 的邊。令 是字母表：
個人認為龍書的概念更加通俗易懂，但是由於沒有數學公式的歸納，導致理論基礎不扎實，有點慌。所以推薦兩本書一起看。
首先，是概念：
接著，是演算法：
很簡單 ，如果開始於 的機器接收字元串 ，始於 的和始於與 接收的串相同 ， 並到達相同狀態 ，且兩個狀態集 同為終態或者非終態 ，那麼 是等價的。我們可以把指向 的連線全部指向 ，並刪除 ，反之亦然。
NFA 轉 DFA 知識總結就到這里，有什麼問題請留言，有錯誤請批評指正，非常感謝您的閱讀。
Ⅳ ！！編譯原理DFA和NFA
DFA或NFA是對計算機程序的行為的抽象模型。你編寫的程序其實就對應了一個自動機。簡單舉例來說，如果a,b可以取值0或1; 程序： if(a==1) b=1; 這個程序對應了一個自動機。
對應的自動機就有狀態 (0,0), (0,1), (1,1), (1, 0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時，運行程序的下一個狀態就是(1,1)。
畫圖出來就是 這4個狀態作為頂點，並且有下面幾條邊
(0,0) --> (0,0)（自環）, (1,0)-->(1,1), (1,1)-->(1,1)（自環）, (0,1)-->(0,1)自環
存在的意義就是一種理論模型，也可以認為是一種編程思想。 詞法分析系也離不開 if else， 這一系列的if else和條件也就組成自動機。。。
最經典體現自動機思想的演算法就是KMP演算法，你肯定學過，字元串子串匹配的演算法。 回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。