Построение по НКА эквивалентного ДКА, алгоритм Томпсона — различия между версиями
(→Алгоритм) |
(→Алгоритм) |
||
Строка 4: | Строка 4: | ||
=== Алгоритм === | === Алгоритм === | ||
Генерируем все подмножества множества состояний НКА {{---}} это состояния ДКА. | Генерируем все подмножества множества состояний НКА {{---}} это состояния ДКА. | ||
− | Далее для всевозможных <tex>(q_1, q_2)</tex> {{---}} пар состояний ДКА и символов <tex>c</tex> | + | Далее для всевозможных <tex>(q_1, q_2)</tex> {{---}} пар состояний ДКА и символов <tex>c</tex> {{---}} добавляем переход из <tex>q_1</tex> в <tex>q_2</tex> по <tex>c</tex>, если для каждого состояния НКА из <tex>q_1</tex> есть переход по <tex>c</tex> в состояние из <tex>q_2</tex> и, наоборот, в каждое состояние НКА из <tex>q_2</tex> есть переход из состояния из <tex>q_1</tex> по <tex>c</tex> |
+ | |||
== Алгоритм Томпсона == | == Алгоритм Томпсона == | ||
Данный алгоритм используется для преобразования НКА в ДКА. | Данный алгоритм используется для преобразования НКА в ДКА. |
Версия 22:10, 23 сентября 2011
Содержание
Алгоритм систем подмножеств
Смысл алгоритма состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний.Алгоритм
Генерируем все подмножества множества состояний НКА — это состояния ДКА. Далее для всевозможных
— пар состояний ДКА и символов — добавляем переход из в по , если для каждого состояния НКА из есть переход по в состояние из и, наоборот, в каждое состояние НКА из есть переход из состояния из поАлгоритм Томпсона
Данный алгоритм используется для преобразования НКА в ДКА. Смысл этого алгоритма, как и предыдущего, состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний. Но не все из состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.Алгоритм
Вначале в очередь помещается множество, состоящее только из стартового состояния НКА
В результате задаст новое состояние автомата. Если еще нет в ДКА, тогда мы помещаем в очередь.
Так как - конечна, а , то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма — в худшем случае это .
Корректность
Утверждение: |
Построенный автомат принимает тот же язык |
Применим индукцию по длине слова .
|