Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) — различия между версиями
(Новая страница: «Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))») |
|||
Строка 1: | Строка 1: | ||
− | + | = Постановка задачи = | |
+ | Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык. | ||
+ | |||
+ | = Алгоритм = | ||
+ | Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата. | ||
+ | |||
+ | === Разбиение на блоки === |
Версия 05:45, 15 октября 2011
Постановка задачи
Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык.
Алгоритм
Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата.