Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
Постановка задачи
Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык.
Алгоритм
Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата.
Разбиения на блоки
Пусть
- множество состояний ДКА. Разделим на 2 блока и , где - множество терминальных состояний и - множество нетерминальных состояний. Теперь будем делить блоки до тех пор, пока они не будут содержать только эквивалентные состояния. Для этого создадим множество сплитеров, где сплитер - это множество состояний. Для каждой буквы из алфавита создадим множество , состоящее из состояний имеющих ребро в текущий сплитер по букве . Если какой-нибудь блок имеет не нулевое пересечение с , а также не является его подмножеством, то его можно разделить на два новых блока. Первый блок состоит из состояний, которые имеют ребра в текущий сплитер по букве , а второй блок состоит из оставшихся состояний. Меньший из них добавим в множество сплитеров и обновим множество блоков . Продолжаем деление до тех пор пока множество сплитеров не пусто.Псевдокод
— множество сплитеров. — множество всех блоков ДКА.
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
Время работы алгоритма
Благодаря системе добавления множеств состояний в множество сплитеров, каждое ребро будет рассмотрено не более чем
раз. А так как ребер у нас порядка то получаем