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