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

Алгоритм систем подмножеств

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

Алгоритм

Генерируем все подмножества множества состояний НКА — это состояния ДКА. Далее для всевозможных [math](q_1, q_2)[/math] — пар состояний ДКА и символов [math]c[/math] — добавляем переход из [math]q_1[/math] в [math]q_2[/math] по [math]c[/math], если для каждого состояния НКА из [math]q_1[/math] есть переход по [math]c[/math] в состояние из [math]q_2[/math] и, наоборот, в каждое состояние НКА из [math]q_2[/math] есть переход из состояния из [math]q_1[/math] по [math]c[/math]

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

Данный алгоритм используется для преобразования НКА в ДКА. Смысл этого алгоритма, как и предыдущего, состоит в замене множества из [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]