Я читаю книгу «Принципы, методы и инструменты компиляторов» Альфреда В.Ахо. Конструкция подмножества DFA из NFA имеет следующие операции над состояниями 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
А таблица перехода Dtran для DFA D:
Проблема в том, что я не могу понять, как мы получаем состояния NFA для состояний DFA 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 заявляет следующее.