Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Алгоритм Томпсона

Данный алгоритм используется для преобразования НКА в ДКА. Смысл алгоритма состоит в замене множества из [math]n[/math] состояний НКА, множеством из [math]2^n[/math] подмножеств его состояний. Но не все из [math]2^n[/math] состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.

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