Ⅰ 編譯原理:怎麼用子集法將NFA轉換成DFA 用圖4.16的NFA舉例子
這里你要弄清子集法中，每一行，指的是變遷。比如第一行，代表狀態0，畫一根線到狀態1，因此第1個0是指這個變遷的起點狀態0，第3個1是指變遷的終點狀態1。
同理，第2行是指從狀態1出發，有2個變遷，即第一個是狀態1指向狀態1（自己），第2個變遷是從狀態1到狀態1和2。
這樣第3行就表示如果從狀態{1，2}開始，輸入是0和1時的變遷分別是什麼，依此類推。
你紅的圈出來的就是NFA所有可能的狀態和狀態組合。
Ⅱ 什麼是子集構造法
子集構造是NFA(Non-Deterministic Finite Automaton, 非確定有窮自動機)轉DFA(Deterministic Finite Automaton)時所使用的用於消除 epsilon-transition(epsilon轉換. 那個字元打不出來, 你懂的) 的方法.
其方法如下.
設有NFA的M, 將其轉換為DFA的 `M.
M的初始狀態的epsilon-closure(epsilon-閉包)作為 `M的初始狀態. 而後, 在某個轉換上, 設該轉換為 a-transition, 那麼, 構造 Sa = {t| 對原狀態集合S中的一些狀態s, 存在通過a-transition到t的轉換}. 再構造Sa的閉包 `Sa. 如此一直構造, 直到沒有新的狀態構造出來為止, 此即子集構造.