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

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

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

Алгоритм

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

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

Пусть [math]Q[/math] - множество состояний ДКА. Разделим [math]Q[/math] на 2 блока [math]F[/math] и [math]Q - F[/math], где [math]F[/math] - множество терминальных состояний и [math]Q - 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 - 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] |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]