編譯原理nfa

① 編譯原理，如何判斷一個FA是DFA還是NFA

第一個是NFA 第二個是DFA
主要區別
1）DFA沒有輸入空串之上的轉換動作；
2）對於DFA，一個特定的符號輸入，有且只能得到一個狀態，而NFA就有可能得到一個狀態集；

② 編譯原理設計狀態轉換圖

根據題意，對應的正規式為b*a+b， 構造等價的NFA，如下圖所示

③ 計算機編譯原理什麼是NFA

ε只能出現在NFA中，當然不是為了方便直觀，而是連通NFA和DFA的橋梁。編譯原理講授的不是如何繪制NFA或者DFA，二是告訴讀者怎樣能夠自動實現NFA或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表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。

⑤ 編譯原理NFA轉DFA ，請問DFA的初始狀態如何確定

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態。

DFA的終態就是所有包含了NFA終態的DFA的狀態。

先以0開始，經過任意個ε得到的結點就是第一個狀態，這道題沒有ε就是{0}。

根據演算法轉化來的DFA肯定是唯一的，但是轉化得到的DFA並不一定是狀態最少的，每一個DFA都可以轉化到狀態最少的DFA。狀態最少的DFA是唯一的（狀態名不同的同構情況除外）。因為每個DFA都可以對應相應的NFA（DFA本身就是），所以NFA轉化的DFA不一定都是狀態數最少的。

(5)編譯原理nfa擴展閱讀：

DFA以如下方式接受或拒絕一個字元串：從初始狀態出發，對於輸入字元串中的每個字元，自動機都將沿著一條確定的邊到另一狀態，這條邊必須是標有輸入符號的邊。對n個字元的字元串進行了n次狀態變換後，如果自動機到達了一個終態，自動機將接收該字元串。

若到達的不是終態，或者找不到與輸入字元相匹配的邊，那麼字元串將拒絕接受這個字元串。 由一個自動機識別的語言是該自動機接收的字元串集合。

⑥ 編譯原理中，由NFA轉化來的DFA是唯一的嗎

根據演算法轉化來的DFA肯定是唯一的，但是轉化得到的DFA並不一定是狀態最少的，每一個DFA都可以轉化到狀態最少的DFA。狀態最少的DFA是唯一的（狀態名不同的同構情況除外）。可參考龍書（一本編譯書籍）。因為每個DFA都可以對應相應的NFA（DFA本身就是），所以NFA轉化的DFA不一定都是狀態數最少的。

⑦ 如題，編譯原理中為什麼要將NFA轉化為DFA

對DFA來說，一個輸入必然對應唯一的路徑與結果，而這正是我們設計編譯器所需要的。

如果從一個狀態經過同樣的一個輸入可以通過兩條或更多路徑達到不同的狀態，我們的編譯器就會迷惑（不知道怎麼辦），只能通過窮舉測試每個狀態是否可行，而窮舉演算法的效率通常都很低下。
DFA的最簡化是有固定演算法的，NFA有沒有我不知道，通常最簡化之後的DFA要比NFA簡單得多