Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) — различия между версиями
(→Разбиение на блоки) |
|||
Строка 24: | Строка 24: | ||
else | else | ||
add <tex>R_2</tex> to <tex>W</tex> | add <tex>R_2</tex> to <tex>W</tex> | ||
+ | |||
+ | ==Время работы алгоритма== |
Версия 04:37, 6 ноября 2011
Постановка задачи
Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык.
Алгоритм
Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата.
Псевдокод
— очередь из сплитеров. — множество всех блоков ДКА.
While is not empty do select and remove from for all do for all in such that and do partition into and and replace in with and if then replace in with and else if then add to else add to