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