NFA中DFA的子集构造

Question

我正在阅读由alfredV.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  

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

​

而DFA D的转换表Dtran是

我所遇到的问题是，当我在{0,1,2,4,7}中的州中，只有2和7向a、move(A,a) ={3,8}和e-closure({3,8}) ={1,2,3,4,6,7,8}过渡时，我无法理解如何在DFA状态B、C、D和E中得到NFA状态。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到具有1或更多e转换的状态2到达。

我没有检查，但我想其他的州也可以用相似的方式来构造。