来自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}与一个或多个电子转换进行联系。

我没有检查，但我认为其他国家可以构建类似。