Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) — различия между версиями
Glukos (обсуждение | вклад) (→Время работы алгоритма) |
м (rollbackEdits.php mass rollback) |
||
(не показано 60 промежуточных версий 15 участников) | |||
Строка 7: | Строка 7: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Класс <tex> | + | Класс <tex>C</tex> '''разбивает''' класс <tex>R</tex> по символу <tex>a</tex> на <tex>R_1</tex> и <tex>R_2</tex>, если |
− | # <tex>\forall r \in R_1 \,\,\, \delta(r, a) \in | + | # <tex>\forall r \in R_1 \,\,\, \delta(r, a) \in C</tex> |
− | # <tex>\forall r \in R_2 \,\,\, \delta(r, a) \notin | + | # <tex>\forall r \in R_2 \,\,\, \delta(r, a) \notin C</tex> |
}} | }} | ||
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний. | Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний. | ||
Строка 15: | Строка 15: | ||
Итеративно строим разбиение множества состояний следующим образом. | Итеративно строим разбиение множества состояний следующим образом. | ||
− | # Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex> | + | # Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний (<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>). |
− | # Перебираются символы алфавита <tex> | + | # Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <tex>\langle F,\ c \rangle</tex> и <tex>\langle Q \setminus F, c \rangle</tex> помещаются в очередь. |
− | # Из очереди извлекается пара <tex> | + | # Из очереди извлекается пара <tex>\langle C,\ a \rangle</tex>, <tex>C</tex> далее именуется как сплиттер. |
− | # | + | # Каждый класс <tex>R</tex> текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер <tex>(R_1)</tex>, а второй из всех оставшихся <tex>(R_2)</tex>. |
− | # | + | # Если <tex>R</tex> разбился на два непустых подкласса (то есть <tex> R_1 \ne \emptyset \ \land \ R_2 \ne \emptyset </tex>). |
+ | ## В разбиении <tex>P</tex> класс <tex>R</tex> заменяется на свои подклассы <tex>R_1</tex> и <tex>R_2</tex>. | ||
+ | ## Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <tex>\langle R_1, c \rangle</tex> и <tex>\langle R_2, c \rangle</tex> помещаются в очередь. | ||
# Пока очередь не пуста, выполняем п.3 – п.5. | # Пока очередь не пуста, выполняем п.3 – п.5. | ||
===Псевдокод=== | ===Псевдокод=== | ||
− | <tex>Q</tex> {{---}} множество состояний ДКА | + | *<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА, |
− | <tex>F</tex> {{---}} множество терминальных состояний | + | *<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний, |
− | <tex> | + | *<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{---}} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>), |
− | <tex>P</tex> {{---}} разбиение множества состояний ДКА | + | *<tex>\mathtt{S}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>, |
− | <tex>R</tex> {{---}} класс состояний ДКА. | + | *<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА, |
− | <tex>P \leftarrow \{ F, Q \setminus F \}</tex> | + | *<tex>\mathtt{R}</tex> {{---}} класс состояний ДКА. |
− | + | ||
− | + | '''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>: '''vector''' | |
− | + | <tex>\mathtt{P} \leftarrow \{ F,\ Q \setminus F \}</tex> | |
− | + | <tex>\mathtt{S} \leftarrow \varnothing </tex> | |
− | + | '''for''' <tex>c \in \Sigma</tex> | |
− | + | push <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</tex> | |
− | + | '''while''' <tex>\mathtt{S} \ne \varnothing</tex> | |
− | + | <tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''from''' <tex>\mathtt{S}</tex> | |
− | + | '''for''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> | |
− | + | <tex> R_1, R_2 \leftarrow </tex> <tex>\mathtt{split}(R,\ C,\ a)</tex> | |
− | + | '''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex> | |
− | + | replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with <tex>R_1</tex> '''and''' <tex>R_2</tex> | |
− | + | '''for''' <tex>c \in \Sigma</tex> | |
− | Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить. | + | insert <tex>\langle R_1,\ c \rangle</tex> '''in''' <tex>\mathtt{S}</tex> |
+ | insert <tex>\langle R_2,\ c \rangle</tex> '''in''' <tex>\mathtt{S}</tex> | ||
+ | '''return''' <tex>\mathtt{P}</tex> | ||
+ | |||
+ | Когда очередь <tex>S</tex> станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить. | ||
+ | |||
+ | ===Время работы=== | ||
+ | Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex> {{---}} алфавит. Это следует из того, что если пара <tex>\langle C,\ a \rangle</tex> попала в очередь, и класс <tex>C</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>C_1</tex> и <tex>C_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|C| \geqslant |C_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку. | ||
== Алгоритм Хопкрофта== | == Алгоритм Хопкрофта== | ||
+ | Рассмотрим алгоритм, позволяющий решить задачу быстрее, чем за <tex> O(n^2) </tex>. | ||
{{Лемма | {{Лемма | ||
− | |statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение | + | |statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение классов (текущего разбиения) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению классов по символу <tex>a</tex> всеми тремя классами <tex>R, R_1, R_2</tex>. |
|proof = | |proof = | ||
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется | Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется | ||
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R \ \land \ \delta(r, a) \in R_1 \ \lor</tex> |
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R \ \land \ \delta(r, a) \notin R_1 \ \lor</tex> |
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R \ \land \ \delta(r, a) \notin R_1</tex> |
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется | А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется | ||
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 \ \lor</tex> |
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex> | :<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex> | ||
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. <br/> | Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. <br/> | ||
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. <br/> | Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. <br/> | ||
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется | Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется | ||
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1 | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1 \ \land \ \delta(r, a) \notin R_2 \ \lor</tex> |
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1 | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1 \ \land \ \delta(r, a) \in R_2 \ \lor</tex> |
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1 | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1 \ \land \ \delta(r, a) \notin R_2</tex> |
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется | А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется | ||
− | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \in R \ \lor</tex> |
− | :<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex> | + | :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> |
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение. | Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение. | ||
}} | }} | ||
− | Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет | + | Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет пары в очередь. |
− | Если | + | После замены класса <tex>R</tex> в разбиении <tex>P</tex> на его подклассы <tex>R_1</tex> и <tex>R_2</tex>, как и раньше перебираем символы алфавита <tex>c \in \Sigma</tex>. |
− | Если | + | |
− | :<tex>\ | + | Если пара <tex>\langle R,\ c \rangle</tex> уже есть в очереди, то согласно лемме можно просто заменить её на пары <tex>\langle R_1, c \rangle</tex> и <tex>\langle R_2, c \rangle</tex>. |
− | + | ||
− | + | Если пары <tex>\langle R,\ c \rangle</tex> нет в очереди, то достаточно добавить любую из пар <tex>\langle R_1, c \rangle</tex> и <tex>\langle R_2, c \rangle</tex>. Это следует из следующих соображений: <tex>R</tex> может быть в разбиении только если в очередь были положены пары <tex>\langle R,\ a \rangle</tex> для <tex>\forall a \in \Sigma</tex>, а поскольку в очереди пары <tex>\langle R,\ c \rangle</tex> нет, то мы её уже успели рассмотреть, следовательно классы из разбиения <tex>P</tex> уже были разбиты по <tex>\langle R,\ c \rangle</tex>. | |
+ | |||
+ | === Реализация === | ||
+ | |||
+ | *<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА, | ||
+ | *<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний, | ||
+ | *<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{---}} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>), | ||
+ | *<tex>\mathtt{S}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>, | ||
+ | *<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА, | ||
+ | *<tex>\mathtt{R}</tex> {{---}} класс состояний ДКА. | ||
+ | |||
+ | '''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>: '''vector''' | ||
+ | <tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> | ||
+ | <tex>\mathtt{S} \leftarrow \varnothing </tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | push <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</tex> | ||
+ | '''while''' <tex>\mathtt{S} \ne \varnothing</tex> | ||
+ | <tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''from''' <tex>\mathtt{S}</tex> | ||
+ | '''for''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> | ||
+ | <tex> R_1, R_2 \leftarrow </tex> <tex>\mathtt{split}(R,\ C,\ a)</tex> | ||
+ | '''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex> | ||
+ | replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with' <tex>R_1</tex> '''and''' <tex>R_2</tex> | ||
+ | '''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex> <font color=darkgreen>// смотрим, есть ли пара <tex>\langle R,\ c \rangle</tex> в очереди </font> | ||
+ | remove <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex> <font color=darkgreen>// заменяем её на пары <tex>\langle R_1, c \rangle</tex>, <tex>\langle R_2, c \rangle</tex> если пара есть </font> | ||
+ | push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''else''' | ||
+ | '''if''' <tex> |\mathtt{P}[R_1]| \leqslant |\mathtt{P}[R_2]| </tex> <font color=darkgreen>// вставляем любую иначе</font> | ||
+ | push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''else''' | ||
+ | push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''return''' <tex>\mathtt{P}</tex> | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</tex>). | ||
+ | |||
+ | '''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>: '''vector''' | ||
+ | <tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> | ||
+ | <tex>\mathtt{S} \leftarrow \varnothing </tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | push <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</tex> | ||
+ | '''while''' <tex>\mathtt{S} \ne \varnothing</tex> | ||
+ | <tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''from''' <tex>\mathtt{S}</tex> | ||
+ | <tex>\mathtt{Inverse} \leftarrow \{r \ | \ r \in Q, \ \delta(r, a) \in C\}</tex> | ||
+ | <tex>T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}</tex> <font color=darkgreen>// находим классы, из состояний которых есть ребро в состояния сплиттера </font> | ||
+ | '''for''' <tex>R</tex> '''in''' <tex>T'</tex> <font color=darkgreen>// перебираем только классы входящие в <tex>T'</tex></font> | ||
+ | <tex> R_1, R_2 \leftarrow </tex> <tex>\mathtt{split}(R,\ C,\ a)</tex> | ||
+ | '''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex> | ||
+ | replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with <tex>R_1</tex> '''and''' <tex>R_2</tex> | ||
+ | '''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex> | ||
+ | remove <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex> | ||
+ | push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''else''' | ||
+ | '''if''' <tex> |\mathtt{P}[R_1]| \leqslant |\mathtt{P}[R_2]| </tex> | ||
+ | push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''else''' | ||
+ | push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> | ||
+ | '''return''' <tex>\mathtt{P}</tex> | ||
+ | |||
+ | |||
+ | Каждая итерация цикла <tex> \mathrm{while} </tex> может быть выполнена за <tex> O(|Q| + |\mathtt{Inverse}|)\,</tex> для текущей пары <tex>\langle C,\ a \rangle</tex>. Покажем, как можно достичь этой оценки. | ||
+ | |||
+ | Классы разбиения <tex>P</tex> будем поддерживать с помощью множеств на [[Хеш-таблица | хэш-таблицах]] (само же разбиение {{---}} обычный вектор, индекс {{---}} номер класса). Это позволит нам эффективно переносить состояния из одного класса в другой (за <tex>O(1)</tex>). | ||
+ | |||
+ | *<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>, | ||
+ | *<tex>\mathtt{Queue}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>, где <tex>C</tex> {{---}} номер класса (сплиттера), | ||
+ | *<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма). | ||
+ | |||
+ | Для обработки <tex>T'</tex> за <tex>O(|Q| + |\mathtt{Inverse}|)\,</tex> нам понадобится следующая структура: | ||
+ | *<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>, | ||
+ | *<tex>\mathtt{Count}</tex> {{---}} целочисленный массив, где <tex>\mathtt{Count}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>, | ||
+ | *<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>. | ||
+ | |||
+ | '''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>: '''vector''' | ||
+ | <tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | push <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex> | ||
+ | '''while''' <tex>\mathtt{Queue} \ne \varnothing</tex> | ||
+ | <tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''from''' <tex>\mathtt{Queue}</tex> | ||
+ | <tex>\mathtt{Involved} \leftarrow \varnothing</tex> | ||
+ | '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> | ||
+ | <tex>i = \mathtt{Class}[r]</tex> | ||
+ | '''if''' <tex>\mathtt{Count}[i] == 0</tex> | ||
+ | insert <tex>i</tex> '''into''' <tex>\mathtt{Involved}</tex> | ||
+ | <tex>\mathtt{Count}[i]++</tex> | ||
+ | '''for''' <tex> i \in \mathtt{Involved}</tex> | ||
+ | '''if''' <tex>\mathtt{Count}[i] < |\mathtt{P}[i]|</tex> | ||
+ | insert <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>// создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> | ||
+ | <tex>\mathtt{Twin}[i] = |\mathtt{P}|</tex> <font color=darkgreen> //запишем в <tex>\mathtt{Twin[i]}</tex> индекс нового класса</font> | ||
+ | '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> | ||
+ | <tex>i = \mathtt{Class}[r]</tex> | ||
+ | <tex>j = \mathtt{Twin}[i]</tex> | ||
+ | '''if''' <tex>j \neq 0</tex> | ||
+ | remove <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex> | ||
+ | add <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex> | ||
+ | '''for''' <tex> i \in \mathtt{Involved}</tex> | ||
+ | <tex>j = \mathtt{Twin}[i]</tex> | ||
+ | '''if''' <tex> j \neq 0 </tex> | ||
+ | '''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> <font color=darkgreen>// парный класс должен быть меньшего размера</font> | ||
+ | <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>// swap за <tex>\mathtt{O(1)}</tex> {{---}} просто переставить указатели</font> | ||
+ | '''for''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen> // обновляем номера классов для вершин, у которых они изменились</font> | ||
+ | <tex>\mathtt{Class}[r] = j</tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | push <tex>\langle j, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex> | ||
+ | <tex>\mathtt{Count}[i] = 0</tex> | ||
+ | <tex>\mathtt{Twin}[i] = 0</tex> | ||
+ | '''return''' <tex>\mathtt{P}</tex> | ||
+ | |||
+ | |||
+ | Стоит отметить, что массивы <tex>\mathtt{Count},\ \mathtt{Twin}\,</tex> аллоцируются ровно один раз при инициализации алгоритма. | ||
+ | |||
+ | Также стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle i, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>\langle \mathtt{Twin}[i], c \rangle</tex>. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\langle \mathtt{Twin}[i], c \rangle</tex>. | ||
+ | Кроме того, вместо очереди можно использовать вообще произвольную структуру, хранящую элементы, в том числе стэк, множество, так как порядок извлечения нам по сути не важен. | ||
+ | |||
+ | ===Время работы=== | ||
− | === | + | {{Лемма |
− | <tex>Q</tex> {{---}} | + | |about = 1 |
− | <tex> | + | |id = Лемма1 |
− | <tex> | + | |statement = |
− | <tex> | + | Количество классов, созданных во время выполнения алгоритма, не превышает <tex>2 |Q| - 1</tex>. |
− | <tex> | + | |proof = |
− | + | Представим дерево, которое соответствует операциям разделения классов на подклассы. Корнем этого дерева является все множество состояний <tex>Q</tex>. Листьями являются классы эквивалентности, оставшиеся после работы алгоритма. Так как дерево бинарное {{---}} каждый класс может породить лишь два новых, а количество листьев не может быть больше <tex>|Q|</tex>, то количество узлов этого дерева не может быть больше <tex>2 |Q| - 1</tex>, что доказывает утверждение леммы. | |
− | + | }} | |
− | + | ||
− | + | {{Лемма | |
− | + | |about = 2 | |
− | + | |id = Лемма2 | |
− | + | |statement = | |
− | + | Количество итераций цикла <tex>\mathrm{while}</tex> не превышает <tex> 2 |\Sigma| |Q| </tex>. | |
− | + | |proof = | |
− | + | Для доказательства этого утверждения достаточно показать, что количество пар <tex>\langle C,\ a \rangle</tex> добавленных в очередь <tex>S</tex> не превосходит <tex> 2 |\Sigma| |Q| </tex>, так как на каждой итерации мы извлекаем одну пару из очереди. | |
− | + | ||
− | + | По [[#Лемма1 | лемме(1)]] количество классов не превосходит <tex>2 |Q| - 1</tex>. Пусть <tex>C</tex> элемент текущего разбиения. Тогда количество пар <tex>\langle C,\ a \rangle</tex>, <tex>\ a \in \Sigma</tex> не может быть больше <tex>|\Sigma|</tex>. Отсюда следует, что всего различных пар, которые можно добавить в очередь, не превосходит <tex> 2 |\Sigma| |Q| </tex>. | |
− | + | }} | |
− | + | ||
− | + | {{Лемма | |
− | + | |about = 3 | |
− | + | |id = Лемма3 | |
− | + | |statement = | |
− | + | Пусть <tex>a \in \Sigma</tex> и <tex>p \in Q</tex>. Тогда количество пар <tex>\langle C,\ a \rangle</tex>, где <tex>p \in C</tex>, которые мы удалим из очереди, не превосходит <tex>\log_2(|Q|)</tex> для фиксированных <tex>a</tex> и <tex>p</tex>. | |
+ | |proof = | ||
+ | Рассмотрим пару <tex>\langle C,\ a \rangle</tex>, где <tex>p \in C</tex>, которую мы удаляем из очереди. И пусть <tex>\langle C',a \rangle</tex> следующая пара, где <tex>p \in C'</tex> и которую мы удалим из очереди. Согласно нашему алгоритму класс <tex>C'</tex> мог появиться в очереди только после операции <tex>\mathtt{replace}</tex>. Но после первого же разбиения класса <tex>C</tex> на подклассы мы добавим в очередь пару <tex>\langle C'', a \rangle</tex>, где <tex>C''</tex> меньший из образовавшихся подклассов, то есть <tex>|C''| \leqslant |C| \ / \ 2</tex>. Так же заметим, что <tex>C' \subseteq C''</tex>, а следовательно <tex>|C'| \leqslant |C| \ / \ 2</tex>. Но тогда таких пар не может быть больше, чем <tex>\log_2(|Q|)</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |about = 4 | ||
+ | |id = Лемма4 | ||
+ | |statement = | ||
+ | <tex>\sum |\mathtt{Inverse}|</tex> по всем итерациям цикла <tex>\mathrm{while}</tex> не превосходит <tex>|\Sigma| |Q| \log_2(|Q|)</tex>. | ||
+ | |proof = | ||
+ | Пусть <tex>x, y \in Q</tex>, <tex>a \in \Sigma</tex> и <tex> \delta(x, a) = y</tex>. Зафиксируем эту тройку. Заметим, что количество раз, которое <tex>x</tex> встречается в <tex>\mathtt{Inverse}\,</tex> при условии, что <tex> \delta(x, a) = y</tex>, совпадает с числом удаленных из очереди пар <tex>\langle C,\ a \rangle</tex>, где <tex>y \in C</tex>. Но по [[#Лемма3 | лемме(3)]] эта величина не превосходит <tex>\log_2(|Q|)</tex>. Просуммировав по всем <tex> x \in Q </tex> и по всем <tex> a \in \Sigma</tex> мы получим утверждение леммы. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement = | ||
+ | Время работы алгоритма Хопкрофта равно <tex>O(|\Sigma| |Q| \log(|Q|)</tex>. | ||
+ | |proof = | ||
+ | Оценим, сколько времени занимает каждая часть алгоритма: | ||
+ | |||
+ | *Построение массива <tex>\mathtt{Inv}</tex> занимает <tex>O(|\Sigma| |Q|)</tex> времени. | ||
+ | |||
+ | *По [[#Лемма2 | второй лемме]] количество итераций цикла <tex>\mathrm{while}</tex> не превосходит <tex>O(|\Sigma| |Q|)</tex>. | ||
+ | |||
+ | *Операции с множеством <tex>T'</tex> и разбиение классов на подклассы требуют <tex>O(\sum(|\mathtt{Inverse}|))\,</tex> времени. Но по [[#Лемма4 | лемме(4)]] <tex>\sum(|\mathtt{Inverse}|)\,</tex> не превосходит <tex>|\Sigma| |Q| \log_2(|Q|)</tex>, то есть данная часть алгоритма выполняется за <tex>O(|\Sigma| |Q| \log_2(|Q|))</tex>. | ||
+ | |||
+ | *В [[#Лемма1 | лемме(1)]] мы показали, что в процессе работы алгоритма не может появится больше, чем <tex>2 |Q| - 1</tex> классов, из чего следует, что количество операций <tex>\mathtt{replace}</tex> равно <tex>O(|\Sigma| |Q|)</tex>. | ||
+ | |||
+ | Итого, получается, что время работы алгоритма Хопкрофта не превышает <tex> O(|\Sigma| |Q|) + O(|\Sigma| |Q|) + O(|\Sigma| |Q| \log_2(|Q|)) + O(|\Sigma| |Q|) = O(|\Sigma| |Q| \log_2(|Q|))</tex>. | ||
+ | }} | ||
+ | |||
+ | === Альтернативная реализация === | ||
+ | Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее). | ||
+ | |||
+ | Все классы разбиения будем по-прежнему хранить в векторе хэш-сетов <tex>\mathtt{P}</tex>. | ||
+ | |||
+ | *<tex>\mathtt{Class}[r]</tex> {{---}} индекс класса в <tex>\mathtt{P}</tex>, которому принадлежит состояние <tex>r</tex>, | ||
+ | *<tex>\mathtt{Queue}</tex> {{---}} очередь из пар <tex>\langle C,\ a \rangle</tex>, | ||
+ | *<tex>\mathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex> (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма), | ||
+ | *<tex>\mathtt{Involved}</tex> {{---}} ассоциативный массив из номеров классов в векторы из номеров вершин. | ||
+ | |||
+ | <tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>: | ||
+ | <tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | insert <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex> | ||
+ | '''while''' <tex>\mathtt{Queue} \ne \varnothing</tex> | ||
+ | <tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''from''' <tex>\mathtt{Queue}</tex> | ||
+ | <tex>\mathtt{Involved} = \{\}</tex> | ||
+ | '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> | ||
+ | <tex>i = \mathtt{Class}[r]</tex> | ||
+ | '''if''' <tex>\mathtt{Involved}[i] == \varnothing</tex> | ||
+ | <tex>\mathtt{Involved}[i] = \{\}</tex> | ||
+ | add <tex>r</tex> '''to''' <tex>\mathtt{Involved}[i]</tex> | ||
+ | '''for''' <tex> i \in \mathtt{Involved}</tex> <font color=darkgreen>//Перебираем ключи <tex>\mathtt{Involved}</tex></font> | ||
+ | '''if''' <tex>|\mathtt{Involved}[i]| < |\mathtt{P}[i]|</tex> | ||
+ | '''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>//Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> | ||
+ | <tex>j = |\mathtt{P}|</tex> <font color=darkgreen>//Запишем в <tex>j</tex> индекс нового класса</font> | ||
+ | '''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex> | ||
+ | remove <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex> | ||
+ | add <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex> | ||
+ | '''if''' <tex>|\mathtt{P}[j]| > |\mathtt{P}[i]|</tex> <font color=darkgreen>//Парный класс должен быть меньшего размера</font> | ||
+ | <tex>\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex> <font color=darkgreen>//swap за <tex>\mathtt{O(1)}</tex> {{---}} просто переставить указатели</font> | ||
+ | '''for''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen>//Обновляем номера классов для вершин, у которых они изменились</font> | ||
+ | <tex>\mathtt{Class}[r] = j</tex> | ||
+ | '''for''' <tex>c \in \Sigma</tex> | ||
+ | push <tex>\langle j, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex> | ||
+ | '''return''' <tex>\mathtt{P}</tex> | ||
+ | |||
+ | == См. также == | ||
− | + | * [[Алгоритм Бржозовского]] | |
− | |||
− | |||
− | == | + | == Источники информации == |
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 177 — ISBN 5-8459-0261-4 (рус.) | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 177 — ISBN 5-8459-0261-4 (рус.) | ||
* ''D. Gries.'' Describing an algorithm by Hopcroft. Technical Report TR-72-151, Cornell University, December 1972. | * ''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. | ||
+ | * [http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf ''John Hopcroft'' An O(nlogn) algorithm for minimizing states in a finite automation] | ||
+ | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Автоматы и регулярные языки]] | [[Категория: Автоматы и регулярные языки]] |
Текущая версия на 19:19, 4 сентября 2022
Пусть дан автомат, распознающий определенный язык. Требуется найти эквивалентный автомат с наименьшим количеством состояний.
Минимизация ДКА
Если в ДКА существуют два эквивалентных состояния, то при их объединении мы получим эквивалентный ДКА, так как распознаваемый язык не изменится. Основная идея минимизации состоит в разбиении множества состояний на классы эквивалентности, полученные классы и будут состояниями минимизированного ДКА.
Простой алгоритм
Определение: |
Класс | разбивает класс по символу на и , если
Если класс
может быть разбит по символу , то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний. Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.Итеративно строим разбиение множества состояний следующим образом.
- Первоначальное разбиение множества состояний — класс допускающих состояний и класс недопускающих состояний ( ).
- Перебираются символы алфавита , все пары и помещаются в очередь.
- Из очереди извлекается пара , далее именуется как сплиттер.
- Каждый класс текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу переходят в сплиттер , а второй из всех оставшихся .
- Если
- В разбиении класс заменяется на свои подклассы и .
- Перебираются символы алфавита , все пары и помещаются в очередь.
разбился на два непустых подкласса (то есть ).
- Пока очередь не пуста, выполняем п.3 – п.5.
Псевдокод
- — множество состояний ДКА,
- — множество терминальных состояний,
- — функция перехода ( — состояние, в которое можно совершить переход из по символу ),
- — очередь пар ,
- — разбиение множества состояний ДКА,
- — класс состояний ДКА.
function findEquivalenceClasses: vector for push , into while pop from for in if and replace in with and for insert in insert in return
Когда очередь
станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.Время работы
Время работы алгоритма оценивается как
, где — количество состояний ДКА, а — алфавит. Это следует из того, что если пара попала в очередь, и класс использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса и , причем можно гарантировать лишь следующее уменьшение размера: . Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем раз. Учитывая, что ребер всего , получаем указанную оценку.Алгоритм Хопкрофта
Рассмотрим алгоритм, позволяющий решить задачу быстрее, чем за
.Лемма: |
Класс и , тогда разбиение классов (текущего разбиения) по символу любыми двумя классами из эквивалентно разбиению классов по символу всеми тремя классами . |
Доказательство: |
Разобьем все классы с помощью и по символу , тогда для любого класса из текущего разбиения выполняетсяА так как и то выполняетсяИз этого следует, что разбиение всех классов с помощью А так как и то выполняется |
Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет пары в очередь. После замены класса
в разбиении на его подклассы и , как и раньше перебираем символы алфавита .Если пара
уже есть в очереди, то согласно лемме можно просто заменить её на пары и .Если пары
нет в очереди, то достаточно добавить любую из пар и . Это следует из следующих соображений: может быть в разбиении только если в очередь были положены пары для , а поскольку в очереди пары нет, то мы её уже успели рассмотреть, следовательно классы из разбиения уже были разбиты по .Реализация
- — множество состояний ДКА,
- — множество терминальных состояний,
- — функция перехода ( — состояние, в которое можно совершить переход из по символу ),
- — очередь пар ,
- — разбиение множества состояний ДКА,
- — класс состояний ДКА.
function findEquivalenceClasses: vector for push , into while pop from for in if and replace in with' and if in // смотрим, есть ли пара в очереди remove from // заменяем её на пары , если пара есть push into push into else if // вставляем любую иначе push into else push into return
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за (его нужно будет эффективно находить для каждой пары ).
function findEquivalenceClasses: vector for push , into while pop from // находим классы, из состояний которых есть ребро в состояния сплиттера for in // перебираем только классы входящие в if and replace in with and if in remove from push into push into else if push into else push into return
Каждая итерация цикла может быть выполнена за для текущей пары . Покажем, как можно достичь этой оценки.
Классы разбиения хэш-таблицах (само же разбиение — обычный вектор, индекс — номер класса). Это позволит нам эффективно переносить состояния из одного класса в другой (за ).
будем поддерживать с помощью множеств на- — номер класса, которому принадлежит состояние ,
- — очередь пар , где — номер класса (сплиттера),
- — массив состояний, из которых есть ребра по символу в состояние (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма).
Для обработки
за нам понадобится следующая структура:- — список из номеров классов, содержащихся во множестве ,
- — целочисленный массив, где хранит количество состояний из класса , которые содержатся в ,
- — массив, хранящий в номер нового класса, образовавшегося при разбиении класса .
function findEquivalenceClasses: vector for push , into while pop from for and if insert into for if insert into // создадим пустой класс в разбиении //запишем в индекс нового класса for and if remove from add to for if if // парный класс должен быть меньшего размера // swap за — просто переставить указатели for // обновляем номера классов для вершин, у которых они изменились for push to return
Стоит отметить, что массивы аллоцируются ровно один раз при инициализации алгоритма.
Также стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого
пара уже была в очереди, то мы добавим её "вторую половинку" . Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же . Кроме того, вместо очереди можно использовать вообще произвольную структуру, хранящую элементы, в том числе стэк, множество, так как порядок извлечения нам по сути не важен.Время работы
Лемма (1): |
Количество классов, созданных во время выполнения алгоритма, не превышает . |
Доказательство: |
Представим дерево, которое соответствует операциям разделения классов на подклассы. Корнем этого дерева является все множество состояний | . Листьями являются классы эквивалентности, оставшиеся после работы алгоритма. Так как дерево бинарное — каждый класс может породить лишь два новых, а количество листьев не может быть больше , то количество узлов этого дерева не может быть больше , что доказывает утверждение леммы.
Лемма (2): |
Количество итераций цикла не превышает . |
Доказательство: |
Для доказательства этого утверждения достаточно показать, что количество пар По добавленных в очередь не превосходит , так как на каждой итерации мы извлекаем одну пару из очереди. лемме(1) количество классов не превосходит . Пусть элемент текущего разбиения. Тогда количество пар , не может быть больше . Отсюда следует, что всего различных пар, которые можно добавить в очередь, не превосходит . |
Лемма (3): |
Пусть и . Тогда количество пар , где , которые мы удалим из очереди, не превосходит для фиксированных и . |
Доказательство: |
Рассмотрим пару | , где , которую мы удаляем из очереди. И пусть следующая пара, где и которую мы удалим из очереди. Согласно нашему алгоритму класс мог появиться в очереди только после операции . Но после первого же разбиения класса на подклассы мы добавим в очередь пару , где меньший из образовавшихся подклассов, то есть . Так же заметим, что , а следовательно . Но тогда таких пар не может быть больше, чем .
Лемма (4): |
по всем итерациям цикла не превосходит . |
Доказательство: |
Пусть лемме(3) эта величина не превосходит . Просуммировав по всем и по всем мы получим утверждение леммы. | , и . Зафиксируем эту тройку. Заметим, что количество раз, которое встречается в при условии, что , совпадает с числом удаленных из очереди пар , где . Но по
Теорема: |
Время работы алгоритма Хопкрофта равно . |
Доказательство: |
Оценим, сколько времени занимает каждая часть алгоритма:
|
Альтернативная реализация
Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее).
Все классы разбиения будем по-прежнему хранить в векторе хэш-сетов
.- — индекс класса в , которому принадлежит состояние ,
- — очередь из пар ,
- — массив состояний, из которых есть ребра по символу в состояние (мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма),
- — ассоциативный массив из номеров классов в векторы из номеров вершин.
: for insert , into while pop from for and if add to for //Перебираем ключи if insert into //Создадим пустой класс в разбиении //Запишем в индекс нового класса for in remove from add to if //Парный класс должен быть меньшего размера //swap за — просто переставить указатели for //Обновляем номера классов для вершин, у которых они изменились for push into return
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 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.
- John Hopcroft An O(nlogn) algorithm for minimizing states in a finite automation