編譯原理NFAM

『壹』 編譯原理課程設計:從NFA構造與之等價的正規式r的程序實現

NFA，DFA要畫圖，不會畫圖啊！

『貳』 編譯原理的課程設計，構造正規式r*（閉包運算）的NFA的程序實現。求源代碼，求文檔。 謝謝

個人感覺畫出NFA最直觀易懂了。前一個正規式僅有一個狀態（開始和接受狀態同），後一個雖然是三個狀態，但是其中一個是繞著a閉包的狀態，一個是繞著b閉包的狀態，而這兩個狀態又是繞著第三狀態（既是開始狀態又是接受狀態）進行閉包，所以實際上可合並為一種狀態，即是說這兩個正規式對應於同一個NFA，所以相等是顯然成立的。

『叄』 ！！編譯原理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表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。

『肆』 對給定的正規式b(a|b)*aa,構造其NFA M，並將其確定化。

表示方法：五元組（S，Z，f，S0，z）

S：狀態集

Z：字母表

f：映射關系

s0：初態

z：終態

（2）確定有限自動機DFA：f為單值映射

（3）非確定有限自動機NFA：f為多值映射

（4）狀態轉換圖和狀態轉換矩陣

(4)編譯原理NFAM擴展閱讀

假定DFAMd＝（｛s0，s1，s2｝，｛a，b｝，f，s0，｛s2｝）：

f：

f（s0，a）＝s1f（s0，b）＝s2

f（s1，a）＝s1f（s1，b）＝s2

f（s2，a）＝s2f（s2，b）＝s1

試著給出Md的狀態轉換圖和狀態轉換矩陣。

狀態轉換矩陣如下

ab

s0s1s2

s1s1s2

s2s2s1

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

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

『陸』 一個關於編譯原理的很難的問題

NFA據說要畫圖的畫表的。。。這里可以么？

『柒』 編譯原理判斷題 設M是一個NFA,並且L(M)={x,y,z},則M的狀態數至少為4個 請問這句話為什麼是錯誤的呢

M的狀態數至少為4個，這句話不正確。

比如下圖，同樣符合題目條件，但狀態只有2個。

『捌』 計算機編譯原理什麼是NFA

ε只能出現在NFA中，當然不是為了方便直觀，而是連通NFA和DFA的橋梁。編譯原理講授的不是如何繪制NFA或者DFA，二是告訴讀者怎樣能夠自動實現NFA或DFA的構造。在實際應用中ε可以幫助計算機轉換NFA為DFA，而在屬性文法和語法制導階段，它也是溝通綜合屬性與繼承屬性、執行語義動作不可或缺的一部分。另外ε的使用可以大大簡化文法產生式的構造難度。我記得最初使用ε是為了使得文法體系（字母表）更加完善，但是在實際應用中卻變得應用廣泛(此觀點不一定正確)。最後想說的是，在編譯中，ε也帶來了不小的麻煩，否則也就不會有諸如「去空產生式」這樣的演算法了:)

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

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

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

『拾』 編譯原理中為什麼要將NFA轉化為DFA

編譯原理中DFA是確定的有限自動機，而NFA是非確定有限自動機，將NFA化為DFA是將狀態數減少，更為簡單確定
希望能給你幫助。