来自NFA的DFA的子集构造
问题描述:
我正在阅读Alfred V.Aho撰写的“编译器原理,技术和工具”一书。从NFA一个DFA的子集构造具有以下操作上NFA状态来自NFA的DFA的子集构造
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
而对于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状态。
答
您还应该在转换后包含电子转换。因此,在查看move(A,a)={3,8}
时,您应该添加状态{6,7,1,2,4}
,因为这些状态都可以从状态2通过move(A,a)={3,8}
与一个或多个电子转换进行联系。
我没有检查,但我认为其他国家可以构建类似。
谢谢编辑@Martin Liversage – karma