Изменения

Данный алгоритм используется для преобразования преобразовывает НКА в эквивалентный ДКА.Смысл этого алгоритма, как и предыдущего, состоит в замене множества Мы будем использовать предыдущий алгоритм построения с одним дополнением - нам не нужны состояния недостижимые из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состоянийстартового. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому  Поэтому в алгоритме используется обход в ширину.  

Вначале в <tex>Q</tex> - очередь помещается множествосостояний, состоящее только соответствующих множествам, состоящих из стартового состояния состояний НКА .<tex>{q_0}s</tex>- стартовое состояние НКА.Затем из очереди изымается очередное множество <tex>P\rightarrow</tex> {{---}} новое состояние ДКАположить в очередь. Если в <tex>P\leftarrow</tex> есть допускающие состояния, то оно допускающее- достать из очереди. Функция перехода строится по следующему правилу '''1: ''' <tex>\delta_D(P, c) = \bigcup_{q_i \in Ps}\delta_Nrightarrow Q</tex> '''2:''' while not (isEmpty(q_i, c)</tex>.Q<br/tex>)) {В результате '''3:''' <tex>q_d \delta_D(P, c)leftarrow Q</tex> задаст новое состояние '''4:''' for <tex>Qc \in \Sigma</tex> автомата. Если { '''5:''' <tex>Qp_d = \o</tex> еще нет в ДКА, тогда мы помещаем '''6:''' for <tex>Qq \in q_d</tex> в очередь.Так как '''7:''' <tex>|Q_N|p_d = p_d \cup \delta(q, c)</tex> - конечна, а '''8:''' if (<tex>|Q_D| \le 2^{|Q_N|}p_d</tex>, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма {{---}} не было в худшем случае это <tex>O(2^nQ</tex>) '''9:''' <tex>p_d \rightarrow Q</tex>. '''10:''' } '''11:''' }

===Корректность==={{Утверждение|statement=Построенный автомат принимает тот же язык|proof=Применим индукцию по длине слова <tex>\omega</tex>.* <tex>|\omega|=1</tex>: По построению стартовое состояние ДКА будет <tex>{s}</tex>, где <tex>s</tex> {{--Верхняя оценка на работу алгоритмы -}} стартовое состояние НКА, причем допускать они могут только одновременно.* Пусть для <tex>|O(n \omega|=cdot 2^n)</tex> - это верно, докажем, что верно и для <tex>|\omega|=n+1</tex>: Пусть так как количество подмножеств множества состояний НКА на шаге n мог находиться в состояниях <tex>{q_1...q_k}</tex>, тогда ДКА, по построениюне более, находится в состоянии <tex>Q={q_1...q_k}</tex>. После перехода по чем <tex>\omega[2^n+1] = c</tex> НКА будет находиться в состояниях <tex>{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex>, а ДКА в состоянии каждое подмножество мы обрабатываем за <tex>P=\delta_DO(Q, cn)</tex>, причем, в силу построения, оно будет допускающим, когда одно из <tex>{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex> {{---}} допускающее. Что нам и требовалосьровно один раз.}}