Алгоритм Томпсона
Данный алгоритм используется для преобразования НКА в ДКА.
Смысл алгоритма состоит в замене множества из [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] = с[/math] НКА будет находиться в состояниях [math]{\delta_N(q_1, c)...\delta_N(q_k, c)}[/math], а ДКА в состоянии [math]P=\delta_D(Q, c)[/math], причем, в силу построения, оно будет допускающим, когда одно из <>tex{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex> — допускающее. Что нам и требовалось. |
| [math]\triangleleft[/math] |
