Изменения
→Алгоритм
Смысл этого алгоритма, как и предыдущего, состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состояний. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.
===Алгоритм===
Вначале в очередь помещается множество , состоящее только из стартового состояния НКА <tex>{q_0}</tex>.
Затем из очереди изымается очередное множество <tex>P</tex> {{---}} новое состояние ДКА. Если в <tex>P</tex> есть допускающие состояния, то оно допускающее. Функция перехода строится по следующему правилу: <tex>\delta_D(P, c) = \bigcup_{q_i \in P}\delta_N(q_i, c)</tex>.<br>
В результате <tex>\delta_D(P, c)</tex> задаст новое состояние <tex>Q</tex> автомата. Если <tex>Q</tex> еще нет в ДКА, тогда мы помещаем <tex>Q</tex> в очередь.
Так как <tex>|Q_N|</tex> - конечна, а <tex>|Q_D| \le 2^{|Q_N|}</tex>, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма {{---}} в худшем случае это <tex>O(2^n)</tex>.
===Корректность===
{{Утверждение
