Построение подмножества DFA из NFA

Я читаю книгу «Принципы, методы и инструменты компиляторов» Альфреда В.Ахо. Конструкция подмножества 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 NFA N для ‹code›(a|b)*abb‹/code›

А таблица перехода Dtran для DFA D:
Transition Table
Проблема в том, что я не могу понять, как мы получаем состояния 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 заявляет следующее.


person karma    schedule 02.03.2016    source источник
comment
Спасибо за редактирование @Martin Liversage   -  person karma    schedule 02.03.2016


Ответы (1)


Вам также следует включать электронные переходы после перехода. Поэтому при просмотре move(A,a)={3,8} вы должны добавить состояния {6,7,1,2,4}, так как все они доступны из состояния 2 с move(A,a)={3,8} с 1 или более электронными переходами.

Я не проверял, но предполагаю, что другие состояния можно построить аналогичным образом.

person Geert-Jan Hut    schedule 20.04.2016