Построение по НКА эквивалентного ДКА, алгоритм Томпсона — различия между версиями
(→Алгоритм) |
|||
Строка 9: | Строка 9: | ||
Смысл этого алгоритма, как и предыдущего, состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состояний. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину. | Смысл этого алгоритма, как и предыдущего, состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состояний. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину. | ||
===Алгоритм=== | ===Алгоритм=== | ||
− | Вначале в очередь помещается множество состоящее только из стартового состояния НКА <tex>{q_0}</tex>. | + | Вначале в очередь помещается множество, состоящее только из стартового состояния НКА <tex>{q_0}</tex>. |
Затем из очереди изымается очередное множество <tex>P</tex> {{---}} новое состояние ДКА. Если в <tex>P</tex> есть допускающие состояния, то оно допускающее. Функция перехода строится по следующему правилу: <tex>\delta_D(P, c) = \bigcup_{q_i \in P}\delta_N(q_i, c)</tex>.<br> | Затем из очереди изымается очередное множество <tex>P</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>\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>, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма {{---}} в худшем случае это <tex>O(2^n)</tex>. | Так как <tex>|Q_N|</tex> - конечна, а <tex>|Q_D| \le 2^{|Q_N|}</tex>, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма {{---}} в худшем случае это <tex>O(2^n)</tex>. | ||
+ | |||
===Корректность=== | ===Корректность=== | ||
{{Утверждение | {{Утверждение |
Версия 22:09, 23 сентября 2011
Содержание
Алгоритм систем подмножеств
Смысл алгоритма состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний.Алгоритм
Генерируем все подмножества множества состояний НКА — это состояния ДКА. Далее для всевозможных
— пар состояний ДКА и символов , добавляем переход из в по , если для каждого состояния НКА из есть переход по в состояние из и, наоборот, в каждое состояние НКА из есть переход из состояния из поАлгоритм Томпсона
Данный алгоритм используется для преобразования НКА в ДКА. Смысл этого алгоритма, как и предыдущего, состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний. Но не все из состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.Алгоритм
Вначале в очередь помещается множество, состоящее только из стартового состояния НКА
В результате задаст новое состояние автомата. Если еще нет в ДКА, тогда мы помещаем в очередь.
Так как - конечна, а , то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма — в худшем случае это .
Корректность
Утверждение: |
Построенный автомат принимает тот же язык |
Применим индукцию по длине слова .
|