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

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

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

Минимизация ДКА

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

Простой алгоритм

Определение:

Класс [math]S[/math] разбивает класс [math]R[/math] по символу [math]a[/math] на [math]R_1[/math] и [math]R_2[/math], если [math]\forall r \in R_1 \,\,\, \delta(r, a) \in S[/math] [math]\forall r \in R_2 \,\,\, \delta(r, a) \notin S[/math]

Если класс [math]R[/math] может быть разбит по символу [math]a[/math], то он содержит хотя бы одну пару неэквивалентных состояний (их можно различить любой строкой начинающейся с символа [math]a[/math]). Если класс нельзя разбить, то он состоит из эквивалентных состояний. Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Псевдокод

[math]Q[/math] — множество состояний ДКА. [math]F[/math] — множество терминальных состояний. [math]W[/math] — очередь. [math]P[/math] — разбиение множества состояний ДКА. [math]R[/math] — класс состояний ДКА.

 [math]W \leftarrow \{ F, Q \setminus F \}[/math]
 [math]P \leftarrow \{ F, Q \setminus F \}[/math]
 while not [math]W[/math].isEmpty() 
   [math]W[/math].pop([math]S[/math])
   for all [math]a \in \Sigma[/math]
     for all [math]R[/math] in [math]P[/math] 
       [math]R_1 = R \cap \delta^{-1} (S, a) [/math]
       [math]R_2 = R \setminus R_1[/math]
       if [math] |R_1| \ne 0[/math] and [math]|R_2| \ne 0[/math]
         replace [math]R[/math] in [math]P[/math] with [math]R_1[/math] and [math]R_2[/math]
         [math]W[/math].push([math]R_1[/math])
         [math]W[/math].push([math]R_2[/math])

Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс не может быть разбит.

Алгоритм Хопкрофта

Алгорит Хопкрофта является улучшением простого алгоритма.

Итеративно строим разбиение множества состояний следующим образом.

1. Первоначальное разбиение множества состояний — класс допускающих состояний и класс недопускающих состояний.
2. Меньший из них помещается в очередь.
3. Из очереди извлекается класс, далее именуемый как сплиттер.
4. Перебираются все символы из алфавита [math]\Sigma[/math], где [math]c[/math] — текущий символ.
5. Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу [math]c[/math] переходят в сплиттер, а второй из всех оставшихся.
6. Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также меньший из двух подклассов добавляется в очередь.
7. Пока очередь не пуста, алгоритм выполняет п.3 – п.6.

Псевдокод

[math]Q[/math] — множество состояний ДКА. [math]F[/math] — множество терминальных состояний. [math]W[/math] — очередь. [math]P[/math] — разбиение множества состояний ДКА. [math]R[/math] — класс состояний ДКА.

 if [math] |F| \le |Q \setminus F|[/math]
     [math]W[/math].push([math]F[/math])
   else
     [math]W[/math].push([math]Q \setminus F[/math])
 [math]P \leftarrow \{ F, Q \setminus F \}[/math]
 while not [math]W[/math].isEmpty() 
   [math]W[/math].pop([math]S[/math])
   for all [math]a \in \Sigma[/math]
     for all [math]R[/math] in [math]P[/math] 
       [math]R_1 = R \cap \delta^{-1} (S, a) [/math]
       [math]R_2 = R \setminus R_1[/math]
       if [math] |R_1| \ne 0[/math] and [math]|R_2| \ne 0[/math]
         replace [math]R[/math] in [math]P[/math] with [math]R_1[/math] and [math]R_2[/math]
         if [math]R[/math] in [math]W[/math]
             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]
                 [math]W[/math].push([math]R_1[/math])
               else
                 [math]W[/math].push([math]R_2[/math])

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

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

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 177 — ISBN 5-8459-0261-4 (рус.)
• J. E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-71-190, Stanford University, January 1971.