Изменения
→Разбиение на блоки
Основная идея минимизации ДКА состоит в объединении состояний автомата в блоки таким образом, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки и будут состояниями минимального автомата.
=== Разбиение на блоки Псевдокод===<tex>W</tex> {{---}} очередь из сплитеров.<tex>P</tex> {{---}} множество всех блоков ДКА. <tex>W \leftarrow \{ F, Q - F \}</tex> <tex>P \leftarrow \{ F, Q - F \}</tex> While <tex>W</tex> is not empty do select and remove <tex>S</tex> from <tex>W</tex> for all <tex>a \in \Sigma</tex> do <tex>l_a \leftarrow \delta^{-1} (S, a)</tex> for all <tex>R</tex> in <tex>P</tex> such that <tex>R \cap l_a \ne \emptyset</tex> and <tex>R \not \subseteq l_a </tex> do partition <tex>R</tex> into <tex>R_1</tex> and <tex>R_2 : R_1 \leftarrow R \cap l_a </tex> and <tex>R_2 \leftarrow R - R_1</tex> replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex> if <tex>R \in W</tex> then 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 add <tex>R_2</tex> to <tex>W</tex>
