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

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

Содержание

1 Минимизация ДКА
2 Простой алгоритм
- 2.1 Псевдокод
- 2.2 Время работы
3 Алгоритм Хопкрофта
- 3.1 Реализация
- 3.2 Время работы
4 Литература

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

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

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

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

Класс разбивает класс по символу на и , если

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

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

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

Псевдокод

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

 [math]\mathtt{P} \leftarrow \{ \mathtt{F, Q} \setminus \mathtt{F} \}[/math]
 [math]\mathtt{S} \leftarrow \varnothing [/math]
 for [math]c \in \Sigma[/math]
   insert [math](\mathtt{F}, c)[/math] in [math]\mathtt{S}[/math]
   insert [math](\mathtt{Q} \setminus \mathtt{F}, c)[/math] in [math]\mathtt{S}[/math]
 while [math] \mathtt{S} \ne \varnothing [/math]
   [math](C, a) \leftarrow[/math] pop([math]\mathtt{S}[/math])
   for [math]R[/math] in [math]\mathtt{P}[/math] 
     [math]R_1 = R \cap \delta^{-1} (C, a) [/math]
     [math]R_2 = R \setminus R_1[/math]
     if [math] R_1 \ne \varnothing [/math] and [math] R_2 \ne \varnothing [/math]
       replace [math]R[/math] in [math]\mathtt{P}[/math] with [math]R_1[/math] and [math]R_2[/math]
       for [math] c \in \Sigma [/math] 
         insert [math](R_1, c)[/math] in [math]\mathtt{S}[/math]
         insert [math](R_2, c)[/math] in [math]\mathtt{S}[/math]

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

Время работы

Время работы алгоритма оценивается как [math]O(|\Sigma| \cdot n^2)[/math], где [math] n [/math] — количество состояний ДКА, а [math] \Sigma [/math]— алфавит. Это следует из того, что если пара [math](C, a)[/math] попала в очередь, и класс [math]C[/math] использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса [math]C_1[/math] и [math]C_2[/math], причем можно гарантировать лишь следующее уменьшение размера: [math]|C| \ge |C_i| + 1[/math]. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем [math]O(n)[/math] раз. Учитывая, что ребер всего [math]O(|\Sigma| \cdot n)[/math], получаем указанную оценку.

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

Лемма:

Класс и , тогда разбиение всех классов (текущее разбиение) по символу любыми двумя классами из эквивалентно разбиению всех классов с помощью по символу .

Доказательство:

Разобьем все классы с помощью [math]R [/math] и [math] R_1[/math] по символу [math]a[/math], тогда для любого класса [math]B[/math] из текущего разбиения выполняется

and or

and

А так как [math]R = R_1 \cup R_2[/math] и [math]R_1 \cap R_2 = \varnothing[/math] то выполняется

or

Из этого следует, что разбиение всех классов с помощью [math]R_2[/math] никак не повлияет на текущее разбиение.
Аналогично доказывается и для разбиения с помощью [math]R [/math] и [math] R_2[/math] по символу [math]a[/math].
Разобьем все классы с помощью [math]R_1[/math] и [math] R_2[/math] по символу [math]a[/math], тогда для любого класса [math]B[/math] из текущего разбиения выполняется

and or

and

А так как [math]R = R_1 \cup R_2[/math] и [math]R_1 \cap R_2 = \varnothing[/math] то выполняется

or

Из этого следует, что разбиение всех классов с помощью никак не повлияет на текущее разбиение.

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь. Если класс [math]R[/math] уже есть в очереди, то согласно лемме можно просто заменить его на [math]R_1[/math] и [math]R_2[/math]. Если класса [math]R[/math] нет в очереди, то согласно лемме в очередь можно добавить класс [math]R[/math] и любой из [math]R_1[/math] и [math]R_2[/math], а так как для любого класса [math]B[/math] из текущего разбиения выполняется

or

то в очередь можно добавить только меньшее из [math]R_1[/math] и [math]R_2[/math].

Реализация

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

 [math]\mathtt{P} \leftarrow \{ \mathtt{F, Q} \setminus \mathtt{F} \}[/math]
 [math]\mathtt{S} \leftarrow \varnothing [/math]
 for [math]c \in \Sigma[/math]
   insert [math] (\mathtt{min} (\mathtt{F, Q} \setminus \mathtt{F}), c)[/math] in [math]\mathtt{S}[/math]
 while [math]S \ne \varnothing[/math]
   [math](C, a) \leftarrow[/math] pop([math]\mathtt{S}[/math])
   [math]T \leftarrow \{R \ | \ R \in \mathtt{P}, \ R[/math] split by [math](C, a) \}[/math]
   for each [math]R[/math] in [math]T[/math]
     [math] R_1, R_2 \leftarrow [/math] split([math]R, C, a[/math])  
     replace [math]R[/math] in [math]\mathtt{P}[/math] with [math]R_1[/math] and [math]R_2[/math]
     for [math]c \in \Sigma[/math]
       if [math](R, c)[/math] in [math]\mathtt{S}[/math]
         replace [math] (R, c)[/math] in [math]\mathtt{S}[/math] with [math](R_1, c)[/math] and [math](R_2, c)[/math]
       else
         insert [math](\mathtt{min}(R_1, R_2), c)[/math] in [math]\mathtt{S}[/math]

К сожалению, совсем не очевидно, как быстро находить множество [math]T[/math]. С другой стороны, понятно, что [math]T \subset T'[/math], где [math]T'[/math] — это множество классов текущего разбиения, из состояний которых в автомате существует переход в состояния сплиттера [math]C[/math] по символу [math]a[/math].

Модифицируем наш алгоритм: для каждой очередной пары [math] (C, a) [/math] будем находить [math] T' [/math], и с каждым классом состояний из [math] T' [/math] будем производить те же действия, что и раньше.

 [math]\mathtt{P} \leftarrow \{ \mathtt{F, Q} \setminus \mathtt{F} \}[/math]
 [math]\mathtt{S} \leftarrow \varnothing [/math]
 for [math]c \in \Sigma[/math]
   insert [math](\mathtt{min} (\mathtt{F, Q} \setminus \mathtt{F}), c)[/math] in [math]\mathtt{S}[/math]
 while [math]\mathtt{S} \ne \varnothing[/math]
   [math](C, a) \leftarrow[/math] pop([math]\mathtt{S}[/math])
   [math]\mathtt{Inverse} \leftarrow \{r \ | \ r \in \mathtt{Q}, \ \delta(r, a) \in C\}[/math]
   [math]T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}[/math]
   for each [math]R[/math] in [math]T'[/math]
     if [math]R[/math] split by [math](C, a)[/math]
       [math] R_1, R_2 \leftarrow [/math] split([math]R, C, a[/math])  
       replace [math]R[/math] in [math]\mathtt{P}[/math] with [math]R_1[/math] and [math]R_2[/math]
       for [math]c \in \Sigma[/math]
         if [math](R, c)[/math] in [math]\mathtt{S}[/math]
           replace [math](R, c)[/math] in [math]S[/math] with [math](R_1, c)[/math] and [math](R_2, c)[/math]
         else
           insert [math](\mathtt{min}(R_1, R_2), c)[/math] in [math]\mathtt{S}[/math]

Каждая итерация цикла [math] while [/math] не может быть выполнена быстрее, чем за [math] O(|Inverse|) [/math] для текущей пары [math] (C,a)[/math]. Покажем, как достичь этой оценки.

Разбиение [math] P [/math] можно поддерживать четырьмя массивами:

[math]Class[r][/math] — номер класса, которому принадлежит состояние [math]r[/math];
[math]Part[i][/math] — указатель на голову двусвязного списка, содержащего состояния, принадлежащие классу [math] i [/math];
[math]Card[i][/math] — количество состояний в классе [math]i[/math];
[math]Place[r][/math] — указатель на состояние [math]r[/math] в списке [math]Part[Class[r]][/math].

Так как мы храним указатель, где находится состояние в двусвязном списке, то операцию перемещения состояния из одного класса в другой можно выполнить за [math]O(1)[/math].

Чтобы эффективно находить множество [math]Inverse[/math], построим массив [math]Inv[/math], который для состояния [math]r[/math] и символа [math]a[/math] в [math]Inv[r][a][/math] хранит множество состояний, из которых существует переход в [math]r[/math] по символу [math]a[/math]. Так как наш алгоритм не меняет изначальный автомат, то массив [math]Inv[/math] можно построить перед началом основной части алгоритма, что займет [math]O(|\Sigma| |Q|)[/math] времени.

Теперь научимся за [math]O(|Inverse|)[/math] обрабатывать множество [math]T'[/math] и разбивать классы. Для этого нам понадобится следующая структура:

[math]Counter[/math] — количество классов;
[math]Involved[/math] — список из номеров классов, содержащихся во множестве [math]T'[/math];
[math]Size[/math] — целочисленный массив, где [math]Size[i][/math] хранит количество состояний из класса [math]i[/math], которые содержатся в [math]Inverse[/math];
[math]Twin[/math] — массив, хранящий в [math]Twin[i][/math] номер нового класса, образовавшегося при разбиении класса [math]i[/math].

Сам же алгоритм обработки [math]T'[/math] будет выглядеть так:

 [math]\mathtt{Involved} \leftarrow \varnothing[/math]
 for [math]q \in C[/math] and [math]r \in \mathtt{Inv}[q][a][/math]
   [math]i = \mathtt{Class}[q][/math]
   if [math]\mathtt{Size}[i] == 0[/math]
     insert [math]i[/math] in [math]\mathtt{Involved}[/math]
   [math]\mathtt{Size}[i]++[/math]
 for [math]q \in C[/math] and [math]r \in \mathtt{Inv}[q][a][/math]
   [math]i = \mathtt{Class}[q][/math]
   if [math]\mathtt{Size}[i] \lt  \mathtt{Card}[i][/math]
     if [math]\mathtt{Twin}[i] == 0[/math]
       [math]\mathtt{Counter}++[/math]
       [math]\mathtt{Twin[i]} = \mathtt{Counter}[/math]
     move [math]r[/math] from [math]i[/math] to [math]\mathtt{Twin}[i][/math]
 for [math] j \in \mathtt{Involved}[/math]
   [math]\mathtt{Size}[j] = 0[/math]
   [math]\mathtt{Twin}[j] = 0[/math]

Для быстрой проверки, находится ли пара [math](C,a)[/math] в очереди [math]S[/math], будем использовать массив [math]InQueue[/math] размера [math]|Q| \times |\Sigma|[/math], где [math]InQueue[C][a] = true[/math], если пара [math](C,a)[/math] содержится в очереди. Так как при разбиении очередного класса [math]R[/math] на подклассы [math]R_1[/math] и [math]R_2[/math] мы в действительности создаем лишь один новый класс, то замена класса [math]R[/math] в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом [math]InQueue[/math]. В результате каждая операция с очередью требует [math]O(1)[/math] времени.

Время работы

Лемма (1):

Количество классов, созданных во время выполнения алгоритма, не превышает .

Доказательство:

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

Лемма (2):

Количество итераций цикла не превышает .

Доказательство:

Для доказательства этого утверждения достаточно показать, что количество пар [math](C,a)[/math] добавленных в очередь [math]S[/math] не превосходит [math] 2 |\Sigma| |Q| [/math], так как на каждой итерации мы извлекаем одну пару из очереди.

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

Лемма (3):

Пусть и . Тогда количество пар , где , которые мы удалим из очереди, не превосходит для фиксированных и .

Доказательство:

Рассмотрим пару , где , которую мы удаляем из очереди. И пусть следующая пара, где и которую мы удалим из очереди. Согласно нашему алгоритму класс мог появиться в очереди только после операции . Но после первого же разбиения класса на подклассы мы добавим в очередь пару , где меньший из образовавшихся подклассов, то есть . Так же заметим, что , а следовательно . Но тогда таких пар не может быть больше, чем .

Лемма (4):

по всем итерациям цикла не превосходит .

Доказательство:

Пусть , и . Зафиксируем эту тройку. Заметим, что количество раз, которое встречается в при условии, что , совпадает с числом удаленных из очереди пар , где . Но по лемме(3) эта величина не превосходит . Просуммировав по всем и по всем мы получим утверждение леммы.

Теорема:

Время работы алгоритма Хопкрофта равно .

Доказательство:

Оценим, сколько времени занимает каждая часть алгоритма:

Построение массива [math]Inv[/math] занимает [math]O(|\Sigma| |Q|)[/math] времени.

По второй лемме количество итераций цикла [math]while[/math] не превосходит [math]O(|\Sigma| |Q|)[/math].

Операции с множеством [math]T'[/math] и разбиение классов на подклассы требуют [math]O(\sum(|Inverse|))[/math] времени. Но по лемме(4) [math]\sum(|Inverse|)[/math] не превосходит [math]|\Sigma| |Q| \log_2(|Q|)[/math], то есть данная часть алгоритма выполняется за .

В лемме(1) мы показали, что в процессе работы алгоритма не может появится больше, чем [math]2 |Q| - 1[/math] классов, из чего следует, что количество операций [math]replace[/math] равно [math]O(|\Sigma| |Q|)[/math].

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

Литература

Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 177 — ISBN 5-8459-0261-4 (рус.)
D. Gries. Describing an algorithm by Hopcroft. Technical Report TR-72-151, Cornell University, December 1972.
Hang Zhou. Implementation of Hopcroft's Algorithm, 19 December 2009.

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

Содержание

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

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

Псевдокод

Время работы

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

Реализация

Время работы

Литература

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты