編譯原理dfa

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

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

⑵ 編譯原理中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的非終態每個狀態之間不一定屬於同一個狀態。

⑶ 編譯原理中的dfa是什麼意思，是什麼術語的縮寫

DFA(確定性有限自動機)

其實就是有限自動機，deterministic finite automaton

其實我記得好像是詞義分析階段用到的一個技術。。。

⑷ 編譯原理，子集法將NFA確定為DFA，求問，表格中的部分都是怎麼來的

我也在看這個。
先以S開始，經過任意個ε得到的結點就是第一個I，這道題就是{X，1,2}，
然後將{X，1,2}中的每一個字元經過a（中間可以有ε）後得到的結點加起來，X的Ia={1,2}，
1的Ia={1,2}，2的Ia是空集，所以這一行的Ia={1,2}。
後面的Ib也是一樣，只不過是經過b後得到的結點的集合。
然後分別將前面的Ia和Ib作為I計算新的Ia和Ib。
再將這些集合依次標號，這道題是{X，1,2}為X，{1,2}為1，{1,2,3}為2，{1,2，Y}為3，根據上面那個表就可以把圖畫出來了。

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

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

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

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

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

⑺ 編譯原理這個DFA怎麼畫

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

⑻ 編譯原理根據正則式((0*|1)(1*0))畫出DFA

今天學到編譯原理的正規表達式，好像挺像用於驗證的正則表達式，它們是不是一樣的？？ 不一樣的雖然編譯原理我忘差不多了可是正則表達式是 JavaScript等

⑼ 編譯原理 構造正規式的dfa時怎麼確定是否為終態

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態
DFA的終態就是所有包含了NFA終態的DFA的狀態
就如下邊的例子，是一個初態為1，終態為6，7，9的NFA經過確定化得到的轉換矩陣，右側是將左側的轉換矩陣改名之後的DFA，也就是最後得到的DFA
對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了
終態則是左邊的2，4，5，6，7和3，8，9和9對應的就是右邊的2，4，5

⑽ 編譯原理DFA子集法怎麼分割

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

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

就如下邊的例子，是一個初態為1，終態為6，7，9的NFA經過確定化得到的轉換矩陣，右側是將左側的轉換矩陣改名之後的DFA，也就是最後得到的DFA

對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了

終態則是左邊的2，4，5，6，7和3，8，9和9對應的就是右邊的2，4，5