Изменения
Нет описания правки
== Алгоритм Томпсона ==
Данный алгоритм используется для преобразования НКА в ДКА.
Вначале в очередь помещается множество состоящее только из стартового состояния НКА <tex>{q_0}</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>, то алгоритм завершится за конечное число шагов. Отсюда же для реализации можно использовать AVLполучается верхняя оценка на время работы алгоритма {{---деревья}} в худшем случае это <tex>O(2^n)</tex>.
