編譯原理畫狀態表

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

② 編譯原理將正規式轉換為等價的正規文法思路

在編譯原理中，將正規式轉化為等價的正規文法是一種常見的方法。我通常採用一種直觀且簡單的圖示化方式來進行這種轉化。

首先，我們從開始符號S開始，定義S可以轉換為三個可能的狀態：a、b和aA或bA。這表示S可以產生a、b中的任何一個，或者繼續產生A。

接著，我們定義A，A可以轉換為aA、aB或空（ε）。這意味著A可以產生一個a，接著繼續產生A，或者產生一個a並接著產生B，當然也可以直接變為ε。

然後，我們定義B，B可以轉換為aB或bC。這意味著B可以產生一個a，接著繼續產生B，或者產生一個b並接著產生C。

最後，我們定義C，C可以轉換為aA或aB。這意味著C可以產生一個a，接著繼續產生A，或者產生一個a並接著產生B。

通過這種方式，我們可以直觀地看到正規式之間的轉換關系，進而轉化為正規文法。

這種圖示化的方法不僅直觀，而且易於理解和記憶。在實際應用中，這種方法可以快速有效地將復雜的正規式轉化為等價的正規文法。

通過這種方式，我們可以將正規式中的各個部分與其對應的文法規則建立聯系，進而更容易地理解和處理。

值得注意的是，這種方法雖然簡單直觀，但在處理更為復雜的正規式時，可能需要進行更細致的分析和調整。

總的來說，通過圖示化的方法，我們可以更好地理解和應用正規式到正規文法的轉換過程。

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

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

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

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

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

(3)編譯原理畫狀態表擴展閱讀：

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

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

④ 編譯原理，正則表達式的低級基礎問題

1、正則表達式：0(0|1)*1
2、由於不方便畫圖，最簡DFA用狀態表表示如下：
（1）開始狀態S------輸入0------->狀態A
（2）狀態A-------輸入0-------->狀態A
（3）狀態A-------輸入1-------->狀態B（可接受狀態）
（4）狀態B-------輸入0-------->狀態A
（5）狀態B-------輸入1-------->狀態B（可接受狀態）

⑤ 求大神指導編譯原理的狀態轉換圖怎麼畫

這里你要弄清子集法中，每一行，指的是變遷。比如第一行，代表狀態0，畫一根線到狀態1，因此第1個0是指這個變遷的起點狀態0，第3個1是指變遷的終點狀態1。

同理，第2行是指從狀態1出發，有2個變遷，即第一個是狀態1指向狀態1（自己），第2個變遷是從狀態1到狀態1和2。

這樣第3行就表示如果從狀態{1，2}開始，輸入是0和1時的變遷分別是什麼，依此類推。
你紅的圈出來的就是NFA所有可能的狀態和狀態組合。