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

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

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

Алгоритм

Вначале в очередь помещается множество состоящее только из стартового состояния НКА [math]{q_0}[/math]. Затем из очереди изымается очередное множество [math]P[/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].

Корректность

Утверждение:

Построенный автомат принимает тот же язык

[math]\triangleright[/math]

Применим индукцию по длине слова [math]\omega[/math]. [math]|\omega|=1[/math]: По построению стартовое состояние ДКА будет [math]{s}[/math], где [math]s[/math] — стартовое состояние НКА, причем допускать они могут только одновременно. Пусть для [math]|\omega|=n[/math] - это верно, докажем, что верно и для [math]|\omega|=n+1[/math]: Пусть НКА на шаге n мог находиться в состояниях [math]{q_1...q_k}[/math], тогда ДКА, по построению, находится в состоянии [math]Q={q_1...q_k}[/math]. После перехода по [math]\omega[n+1] = c[/math] НКА будет находиться в состояниях [math]{\delta_N(q_1, c)...\delta_N(q_k, c)}[/math], а ДКА в состоянии [math]P=\delta_D(Q, c)[/math], причем, в силу построения, оно будет допускающим, когда одно из [math]{\delta_N(q_1, c)...\delta_N(q_k, c)}[/math] — допускающее. Что нам и требовалось.

[math]\triangleleft[/math]