Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

Постановка задачи

Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык.

Алгоритм

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

Псевдокод

[math]W[/math] — очередь из сплитеров. [math]P[/math] — множество всех блоков ДКА.

 [math]W \leftarrow \{ F, Q - F \}[/math]
 [math]P \leftarrow \{ F, Q - F \}[/math]
 While [math]W[/math] is not empty do 
   select and remove [math]S[/math] from [math]W[/math]
   for all [math]a \in \Sigma[/math] do
     [math]l_a \leftarrow \delta^{-1} (S, a)[/math]
     for all [math]R[/math] in [math]P[/math] such that [math]R \cap l_a \ne \emptyset[/math] and [math]R \not \subseteq l_a [/math] do
       partition [math]R[/math] into [math]R_1[/math] and [math]R_2 : R_1 \leftarrow R \cap l_a [/math] and [math]R_2 \leftarrow R - R_1[/math]
       replace [math]R[/math] in [math]P[/math] with [math]R_1[/math] and [math]R_2[/math]
       if [math]R \in W[/math] then
         replace [math]R[/math] in [math]W[/math] with [math]R_1[/math] and [math]R_2[/math]
       else
         if [math]\mid R_1 \mid \le \mid R_2 \mid[/math] then
           add [math]R_1[/math] to [math]W[/math]
         else
           add [math]R_2[/math] to [math]W[/math]