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