編譯原理dfa的最簡化

① 編譯原理由正規式構造DFA

先畫出NFA，如圖：（我就是傳說當中的靈魂畫師）

這個DFA本身就已經是最簡的了，無法再簡化，最簡化過程我就直接省了

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

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

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

③ 編譯原理--NFA轉化為DFA問題 下面是個圖，但是最小化後A和C為什麼不能合並

看龍書吧，編譯上的經典。
怎樣實現倒是沒有，不過我這里有一個網上淘的簡單C語言編譯器源碼，如果你要我可以發給你。

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

⑤ 編譯原理這個DFA怎麼畫

這個是能畫的最簡單的，左邊是開始狀態。原則是：1）先連接運算，2）再選擇3）再閉包

⑥ 編譯原理：高手幫忙看下與正規式等價的狀態最少的DFA

http://..com/question/680468671167188732.html?fr=qlquick

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

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

⑧ dfa的最小化如何化簡的步驟

下面具體介紹DFA的化簡演算法：
（1） 首先將DFA M的狀態劃分出終止狀態集K1和非終止狀態集K2。
K＝K1∪K2
由上述定義知，K1和K2是不等價的。
（2） 對各狀態集每次按下面的方法進一步劃分，直到不再產生新的劃分。
設第i次劃分已將狀態集劃分為k組，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
對於狀態集Kj(i)（j=1,2,…,k）中的各個狀態逐個檢查，設有兩個狀態Kj』、 Kj』』∈Kj(i)，且對於輸入符號a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn屬於同一個狀態集合，則將Kj』和Kj』』放到同一集合中，否則將Kj』和Kj』』分為兩個集合。
（3） 重復第（2）步，直到每一個集合不能再劃分為止，此時每個狀態集合中的狀態均是等價的。
（4） 合並等價狀態，即在等價狀態集中取任意一個狀態作為代表，刪去其他一切等價狀態。
（5） 若有無關狀態，則將其刪去。
根據以上方法就將確定有限自動機進行了簡化，而且簡化後的自動機是原自動機的狀態最少的自動機。

⑨ 編譯原理中，在DFA的最小化問題。

是要分到兩個不同集合里的

但是我建議 在極小化時先引入「死狀態」
如果一個DFA的轉換函數不是全函數，則要引入一個「死狀態」sd，sd對所有輸入符號都轉換到sd本身。
這樣你做的時候就會看的很明白

⑩ 編譯原理中DFA的終態和非終態怎麼區分啊，誰說的通俗點啊

編譯原理中DFA的終態和非終態區別為：包含不同、空集不同、狀態不同。

一、包含不同

1、DFA的終態：DFA的終態包含了NFA終點結點的狀態集合。

2、DFA的非終態：DFA的非終態不包含NFA終點結點的狀態集合。

二、空集不同

1、DFA的終態：DFA的終態不可能為空集，因為NFA的終點一定會包含在某個DFA的狀態集合中。

2、DFA的非終態：DFA有可能得到的非終態是空集，意味著所有的DFA的狀態集合都包含了NFA的終點。

三、狀態不同

1、DFA的終態：DFA的終態每個狀態之間屬於同一個狀態。

2、DFA的非終態：DFA的非終態每個狀態之間不一定屬於同一個狀態。