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

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

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

Алгоритм

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

Разбиения на блоки

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

Псевдокод

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

 [math]W \leftarrow \{ F, Q \setminus F \}[/math]
 [math]P \leftarrow \{ F, Q \setminus 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 : 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] |R_1| \le |R_2|[/math] then
           add [math]R_1[/math] to [math]W[/math]
         else
           add [math]R_2[/math] to [math]W[/math]

Время работы алгоритма

Благодаря системе добавления множеств состояний в множество сплиттеров, каждое ребро будет рассмотрено не более чем [math]\log{n}[/math] раз. А так как ребер у нас порядка [math] |\Sigma| * n [/math] то получаем [math] O(n\log{n})[/math]