Изменения
→Алгоритм
= Алгоритм =
Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата.
===Разбиения на блоки===
Пусть <tex>Q</tex> - множество состояний ДКА. Разделим <tex>Q</tex> на 2 блока <tex>F</tex> и <tex>Q - F</tex>, где <tex>F</tex> - множество терминальных состояний и <tex>Q - 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>. Продолжаем деление до тех пор пока множество сплитеров не пусто.
===Псевдокод===
<tex>W</tex> {{---}} очередь из множество сплитеров.
<tex>P</tex> {{---}} множество всех блоков ДКА.
<tex>W \leftarrow \{ F, Q - F \}</tex>
replace <tex>R</tex> in <tex>W</tex> with <tex>R_1</tex> and <tex>R_2</tex>
else
if <tex>\mid |R_1 \mid | \le \mid |R_2 \mid|</tex> then
add <tex>R_1</tex> to <tex>W</tex>
else
==Время работы алгоритма==
Благодаря системе добавления множеств состояний в множество сплитеров, каждое ребро будет рассмотрено не более чем <tex>\log{n}</tex> раз. А так как ребер у нас порядка <tex> |\Sigma| * n </tex> то получаем <tex> O(n\log{n})</tex>
