來自NFA的DFA的子集構造

Question

我正在閱讀Alfred V.Aho撰寫的「編譯器原理，技術和工具」一書。從NFA一個DFA的子集構造具有以下操作上NFA狀態

e-closure(s)| Set of NFA states reachable from NFA state s on e-transations alone 
e-closure(T)| Set of NFA states reachable from some NFA state s in set T on e-transation alone; =**U**s in T e-closure(s) 
move(T,a) | Set of NFA states to which there is a transition on input symbol **a** from some state s in T 

下面是一個NFA接受(a|b)*abb

而對於DFA d轉換表DTRAN被

我遇到的問題是我無法理解我們如何獲得DFA狀態的NFA狀態BCD和E 當標記DFA狀態A時。NFA中的狀態{0,1,2,4,7}只有2和7已轉換爲a,move(A,a) ={3,8}和e-closure({3,8}) ={1,2,3,4,6,7,8}。 My problem is how do we end up with{1,2,3,4,6,7,8}和下面的NFA狀態。

Answer 1

您還應該在轉換後包含電子轉換。因此，在查看move(A,a)={3,8}時，您應該添加狀態{6,7,1,2,4}，因爲這些狀態都可以從狀態2通過move(A,a)={3,8}與一個或多個電子轉換進行聯繫。

我沒有檢查，但我認爲其他國家可以構建類似。