Построение по НКА эквивалентного ДКА, алгоритм Томпсона — различия между версиями
Строка 1: | Строка 1: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
+ | == Алгоритм систем подмножеств == | ||
+ | Смысл алгоритма состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</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> | ||
== Алгоритм Томпсона == | == Алгоритм Томпсона == | ||
Данный алгоритм используется для преобразования НКА в ДКА. | Данный алгоритм используется для преобразования НКА в ДКА. | ||
− | Смысл алгоритма состоит в замене множества из <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>. |
Версия 20:36, 6 ноября 2010
Содержание
Алгоритм систем подмножеств
Смысл алгоритма состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний.Алгоритм
Генерируем все подмножества множества состояний НКА — это состояния ДКА. Далее для всевозможных
— пар состояний ДКА и символов , добавляем переход из в по , если для каждого состояния НКА из есть переход по в состояние из и, наоборот, в каждое состояние НКА из есть переход из состояния из поАлгоритм Томпсона
Данный алгоритм используется для преобразования НКА в ДКА. Смысл этого алгоритма, как и предыдущего, состоит в замене множества из
состояний НКА, множеством из подмножеств его состояний. Но не все из состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.Алгоритм
Вначале в очередь помещается множество состоящее только из стартового состояния НКА
В результате задаст новое состояние автомата. Если еще нет в ДКА, тогда мы помещаем в очередь.
Так как - конечна, а , то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма — в худшем случае это .
Корректность
Утверждение: |
Построенный автомат принимает тот же язык |
Применим индукцию по длине слова .
|