1632
правки
Изменения
м
'''push''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</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>
<tex>\mathtt{pushSetsToQueue}(S,\ R_1,\ R_2,\ c)</tex> {{---}} функция, которая добавляет одну из пар <tex>\langle R_1, c \rangle</tex>, <tex>\langle R_2, c \rangle</tex> в очередь S.
'''push''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</tex>
'''push''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{S}</tex>
'''push''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex> <tex>\mathtt{InQueue}[F][c] \ \leftarrow \ </tex> ''true'' <tex>\mathtt{InQueue}[Q \setminus F][c] \ \leftarrow \ </tex> ''true''
'''insert''' <tex>i</tex> '''ininto''' <tex>\mathtt{Involved}</tex>
'''if''' <tex>j = \mathtt{Twin}[i] \neq 0</tex> '''removeif''' <tex>j \neq 0</tex> remove <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex> '''add''' <tex>r</tex> '''to''' <tex>\mathtt{P}[\mathtt{Twin}[i]j]</tex> '''for''' <tex> j i \in \mathtt{Involved}</tex> <tex>j = \mathtt{Twin}[i]</tex> '''if''' <tex> \mathtt{Twin}[j] \neq 0 </tex> '''forif''' <tex>c |\in mathtt{P}[j]| > |\Sigmamathtt{P}[i]|</tex> <font color=darkgreen>// парный класс должен быть меньшего размера</font> <tex>\mathtt{pushSetsToQueueswap}(\mathtt{QueueP},\ j[i],\ \mathtt{TwinP}[j],)</tex> <font color=darkgreen>// swap за <tex>\ cmathtt{O(1)}</tex> {{---}} просто переставить указатели</font> '''for''' <tex>r \in \mathtt{CountP}[j] </tex> <font color= 0darkgreen> // обновляем номера классов для вершин, у которых они изменились</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{TwinCount}[ji] = 0</tex> <tex>\mathtt{InQueueTwin}[Ci][a] \ \leftarrow = 0</tex> ''false''
Стоит отметить, что массивы <tex>\mathtt{Count}, \mathtt{Twin}</tex> аллоцируются ровно один раз при инициализации алгоритма.
Осталось только реализовать Стоит отметить, что массивы <tex>\mathtt{pushSetsToQueueCount}</tex>. <tex>,\mathtt{pushSetsToQueue}(\mathtt{QueueTwin},\ R_1,\ R_2,\ c)</tex>:аллоцируются ровно один раз при инициализации алгоритма. <tex>cnt1 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_1]</tex> <tex>cnt2 \leftarrow <Также стоит отметить, что собственно наличие/tex> '''size of''' отсутствие пары в очереди можно не проверять. Если для некоторого <tex>\mathtt{P}[R_2]</tex> '''if''' <tex> \mathtt{InQueue}[R_1][c] == </tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex> '''push''' пара <tex>\langle R_1i, c \rangle</tex> '''to''' уже была в очереди, то мы добавим её "вторую половинку" <tex>\mathtt{Queue}</tex> <tex>langle \mathtt{InQueueTwin}[R_1i][c] \ \leftarrow \ </tex> ''true'' '''else''' '''push''' <tex>\langle R_2, c \rangle</tex> '''to''' . Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\mathtt{Queue}</tex> <tex>langle \mathtt{InQueueTwin}[R_2i][, c] \ \leftarrow \ rangle</tex> ''true''.Кроме того, вместо очереди можно использовать вообще произвольную структуру, хранящую элементы, в том числе стэк, множество, так как порядок извлечения нам по сути не важен.
Заметим, что вообще нам не важен порядок доставания элементов из "очереди", потому вместо очереди Все классы разбиения будем по-прежнему хранить в векторе хэш-сетов <tex>\mathtt{QueueP}</tex> и массива <tex>\mathtt{InQueue}</tex> можно обойтись одним множеством пар (оставим название <tex>\mathtt{Queue}</tex>).
'''insert''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</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''' '''size of''' <tex>|\mathtt{Involved}[i] | <</tex> '''size of''' <tex>|\mathtt{P}[i]|</tex> '''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen> //Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> <tex>j = </tex> '''size of''' <tex>|\mathtt{P}|</tex> <font color=darkgreen> //Запишем в <tex>j</tex> индекс нового класса</font>
remove <tex>r</tex> '''removefrom''' <tex>\mathtt{P}[i]</tex> add <tex>r</tex> '''fromto''' <tex>\mathtt{P}[ij]</tex> '''addif''' <tex>r|\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> '''tofor''' <tex>r \in \mathtt{P}[j]</tex> <font color=darkgreen>//Обновляем номера классов для вершин, у которых они изменились</font> <tex>\mathtt{Class}[r] = j</tex>
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>:
<tex>cnt1 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_1]</tex>
<tex>cnt2 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_2]</tex>
'''if''' \lnot(<tex>\langle R_1, c \rangle</tex> '''in''' <tex>\mathtt{Queue}</tex>) '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''insert''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
'''else'''
'''insert''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
== Сравнение с алгоритмом из оригинальной статьи Хопкрофта ==
В оригинальной статье <ref>[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]</ref> использовалась дополнительная структура, которую мы обозначим, как <tex>\mathtt{ClassInv}</tex>, в <tex>\mathtt{ClassInv}[C][a]</tex> будем хранить множество состояний, из которых есть ребро по символу <tex>a</tex> в состояние <tex>C</tex> (аналогично <tex>Inv</tex>, только для классов).
<tex>\mathtt{ClassInv}[C][a] = \{ s\ |\ \mathtt{Class}[s] == C \ \land \ \delta^{-1} (s, a) \neq \emptyset \}</tex>
<tex>\mathtt{pushSetsToQueue}</tex> реализуем так:
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>:
<tex>cnt1 \leftarrow \mathtt{ClassInv}[R_1][c]</tex>
<tex>cnt2 \leftarrow \mathtt{ClassInv}[R_2][c]</tex>
'''if''' <tex> \mathtt{InQueue}[R_1][c] ==</tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
'''insert''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_1]</tex>
'''else'''
'''push''' <tex>\langle R_2, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
'''insert''' <tex> c </tex> '''into''' <tex>\mathtt{InQueue}[R_2]</tex>
Циклы
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
(...)
реализуются так:
'''for''' <tex>q \in \mathtt{ClassInv}[C][a]</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
(...)
Тогда время работы внутреннего цикла можно будет оценить как <tex>O(|\mathtt{ClassInv}[C][a]| + |\mathtt{Inverse}|)</tex>. А реализация <tex>\mathtt{pushSetsToQueue}</tex> выбирает множество, на котором <tex>O(|\mathtt{ClassInv}[C][a]|)</tex> будет меньшим.
Кроме того, вместо [[Хеш-таблица | хэш-таблиц]] для хранения множеств (<tex>\mathtt{ClassInv}</tex>, разбиение <tex>P</tex>) можно использовать комбинацию из двусвязного списка и вектора (добавление/удаление через список, поиск через вектор). Что и используется в оригинальной статье.
== Примечания ==
<references/>
rollbackEdits.php mass rollback
# Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <tex>\langle F,\ c \rangle</tex> и <tex>\langle Q \setminus F, c \rangle</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> помещаются в очередь.
===Псевдокод===
*<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>\mathtt{findEquivalenceClasses}(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>
'''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>
'''return''' <tex>\mathtt{P}</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>R, R_1, R_2a</tex> по символу всеми тремя классами <tex>aR, R_1, R_2</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</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>\mathtt{findEquivalenceClasses}(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>
'''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> '''replaceif''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{PS}</tex> <font color=darkgreen>// смотрим, есть ли пара <tex>\langle R,\ c \rangle</tex> в очереди </font> remove <tex>\langle R, c \rangle</tex> '''withfrom''' <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> '''andinto''' <tex>\mathtt{S}</tex> push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''forelse''' '''if''' <tex>c |\mathtt{P}[R_1]| \in leqslant |\Sigmamathtt{P}[R_2]| </tex> <font color=darkgreen>// вставляем любую иначе</font> push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueueS}(S,</tex> '''else''' push <tex>\ R_1langle R_2,c \ R_2,rangle</tex> '''into''' <tex>\ c)mathtt{S}</tex>
'''return''' <tex>\mathtt{P}</tex>
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</tex>).
'''function''' findEquivalenceClasses<tex>\mathtt{findEquivalenceClasses}(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>
'''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> '''replaceif''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{PS}</tex> remove <tex>\langle R, c \rangle</tex> '''withfrom''' <tex>\mathtt{S}</tex> push <tex>\langle R_1, c \rangle</tex> '''andinto''' <tex>\mathtt{S}</tex> push <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''forelse''' '''if''' <tex>c |\mathtt{P}[R_1]| \in leqslant |\Sigmamathtt{P}[R_2]| </tex> push <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueueS}(S,</tex> '''else''' push <tex>\ R_1langle R_2,c \ R_2,rangle</tex> '''into''' <tex>\ c)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{InQueue}</tex> {{---}} двумерный массив булеанов, <tex>\mathtt{InQueue}[C][a] == </tex> ''true'', если <tex>\langle C,\ a \rangle</tex> находится в очереди <tex>\mathtt{Queue}</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>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:'''vector'''
<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex>
'''for''' <tex>c \in \Sigma</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>
<tex>\mathtt{Count}[i]++</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{Count}[i] <</tex> '''size of''' <tex>|\mathtt{P}[i]|</tex> '''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen> //Создадим создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> <tex>\mathtt{Twin}[i]} = </tex> '''size of''' <tex>|\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>
'''return''' <tex>\mathtt{P}</tex>
===Время работы===
<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> мы получим утверждение леммы.
}}
*По [[#Лемма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>\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>
'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> pop '''take any from''' <tex>\mathtt{Queue}</tex> //Взять любую пару из <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{Involved}[i] == \varnothing</tex>
'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>
'''for''' <tex>c \in \Sigma</tex>
push <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ i,\ langle j,\ c)</tex> '''remove''' <tex>\langle C,\ a \rangle</tex> '''frominto''' <tex> \mathtt{Queue}</tex>
'''return''' <tex>\mathtt{P}</tex>
== См. также ==
* [[Алгоритм Бржозовского]]
== Источники информации ==