Изменения

Данный алгоритм преобразовывает НКА в эквивалентный ДКА.Мы будем Будем использовать предыдущий вышеуказанный способ построения с одним дополнением {{--- нам }} не нужны будем учитывать состояния недостижимые из стартового. 

<tex>Q</tex> {{-- -}} очередь состояний, соответствующих множествам, состоящих из состояний НКА.<tex>s</tex> {{--- }} стартовое состояние НКА. '''1:''' <tex>Q.push(\{s\})</tex> '''2:''' <tex>while</tex> <tex>not</tex> <tex>(isEmpty(Q))\{</tex> '''3:''' <tex>Q.pop(q_d)</tex> '''4:''' <tex>for</tex> <tex>c \in \Sigma \{</tex> '''5:''' <tex>p_d = \ovarnothing</tex> '''6:''' <tex>for</tex> <tex>q \in q_d</tex> '''7:''' <tex>p_d = p_d \cup \delta(q, c)</tex> '''8:''' <tex>if</tex> <tex>(p_d</tex> <tex>haven't</tex> <tex>been</tex> <tex>in</tex> <tex>Q</tex>) '''9:''' <tex>Q.push(p_d)</tex> '''10:''' <tex>\}</tex> '''11:''' <tex>\}</tex>

Верхняя оценка на работу алгоритмы - <tex>O(n \cdot 2^n)</tex> - так ===Асимптотика===Так как количество подмножеств множества состояний НКА не более, чем <tex>2^n</tex>, а каждое подмножество мы обрабатываем ровно один раз за время <tex>O(n)</tex>, получаем верхнюю оценку времени работы алгоритма {{---}} <tex>O(n \cdot 2^n)</tex> и ровно один раз.