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

Материал из Викиконспекты
Версия от 22:18, 10 ноября 2011; 192.168.0.2 (обсуждение) (Постановка задачи)
Перейти к: навигация, поиск

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

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

Алгоритм

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

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

Пусть [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]

Литература

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : 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.