Изменения

Основная идея минимизации состоит в разделении состояний ДКА по классам на классы эквивалентности. Получившиеся классы и будут состояниями минимального автомата.

Пусть <tex>Q</tex> {{---}} множество состояний ДКА. Разделим <tex>Q</tex> на 2 блока класса <tex>F</tex> и <tex>Q \setminus F</tex>, где <tex>F</tex> {{---}} множество терминальных состояний и <tex>Q \setminus F</tex> {{---}} множество нетерминальных состояний. Теперь будем делить блоки классы до тех пор, пока они не будут содержать только эквивалентные состояния. Для этого создадим множество сплиттеров, где сплиттер {{---}} это множество состояний. Для каждой буквы <tex>a</tex> из алфавита <tex>\Sigma</tex> создадим множество <tex>l_a</tex>, состоящее из состояний имеющих ребро в текущий сплиттер по букве <tex>a</tex>. Если какой-нибудь блок класс имеет не нулевое пересечение с <tex>l_a</tex>, а также не является его подмножеством, то его можно разделить на два новых блокакласса. Первый блок класс состоит из состояний, которые имеют ребра в текущий сплиттер по букве <tex>a</tex>, а второй блок класс состоит из оставшихся состояний. Меньший из них добавим в множество сплиттеров <tex>W</tex> и обновим множество блоков <tex>P</tex>. Продолжаем деление до тех пор пока множество сплиттеров не пусто.