Изменения

= Постановка задачи =Пусть дан автомат , распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат ]] с наименьшим количеством состояний, который распознает этот же язык.

= Алгоритм = Минимизация ДКА ==Если в ДКА существуют два [[ Эквивалентность_состояний_ДКА | эквивалентных состояния]], то при их объединении мы получим [[ Эквивалентность_состояний_ДКА | эквивалентный ДКА]], так как распознаваемый язык не изменится. Основная идея минимизации ДКА состоит в объединении разбиении множества состояний автомата в блоки таким образомна классы эквивалентности, что любые два состояния из разных блоков неэквивалентны и любые состояния из одного блока эквивалентны. Получившиеся блоки полученные классы и будут состояниями минимального автоматаминимизированного ДКА.

===Разбиения на блокиПростой алгоритм =={{Определение|definition =Пусть Класс <tex>C</tex> '''разбивает''' класс <tex>QR</tex> {{---}} множество состояний ДКА. Разделим по символу <tex>Qa</tex> на 2 блока <tex>FR_1</tex> и <tex>Q \setminus FR_2</tex>, где если # <tex>F\forall r \in R_1 \,\,\, \delta(r, a) \in C</tex> {{---}} множество терминальных состояний и # <tex>Q \setminus Fforall r \in R_2 \,\,\, \delta(r, a) \notin C</tex> {{---}} множество нетерминальных Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний(так как существует строка которая их различает). Теперь будем делить блоки Если класс нельзя разбить, то он состоит из эквивалентных состояний.Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор, пока они не будут содержать только эквивалентные состоянияэто возможно.  Итеративно строим разбиение множества состояний следующим образом. Для этого создадим множество сплиттеров, где сплиттер # Первоначальное разбиение множества состояний {{---}} это множество класс допускающих состояний <tex>F</tex> и класс недопускающих состояний. Для каждой буквы (<tex>a\mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> из ).# Перебираются символы алфавита <tex>c \in \Sigma</tex> создадим множество , все пары <tex>l_a\langle F,\ c \rangle</tex>и <tex>\langle Q \setminus F, состоящее из состояний имеющих ребро c \rangle</tex> помещаются в текущий сплиттер по букве очередь.# Из очереди извлекается пара <tex>\langle C,\ a\rangle</tex>, <tex>C</tex> далее именуется как сплиттер. Если какой-нибудь блок имеет не нулевое пересечение с # Каждый класс <tex>l_aR</tex>, а также не является его подмножеством, то его можно разделить текущего разбиения разбиваются на два новых блока2 подкласса (один из которых может быть пустым). Первый блок состоит из состояний, которые имеют ребра по символу <tex>a</tex> переходят в текущий сплиттер по букве <tex>a(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>W\langle R_1, c \rangle</tex> и обновим множество блоков <tex>P\langle R_2, c \rangle</tex>помещаются в очередь. Продолжаем деление до тех пор пока множество сплиттеров # Пока очередь не пустопуста, выполняем п.3 – п.5.

*<tex>W\mathtt{Q}</tex> {{---}} множество сплиттеров.состояний ДКА,*<tex>P\mathtt{F}</tex> {{---}} множество всех блоков ДКА.терминальных состояний, *<tex>W \leftarrow \mathtt{ F, Q \setminus F \delta}</tex> {{---}} функция перехода (<tex>P \leftarrow \{ Fdelta (r, Q \setminus F \}a)</tex> while {{---}} состояние, в которое можно совершить переход из <tex>Wr</tex> is not empty do select and remove по символу <tex>Sa</tex> from ),*<tex>W<\mathtt{S}</tex> for all {{---}} очередь пар <tex>\langle C,\ a \in \Sigmarangle</tex> do, *<tex>l_a \leftarrow \delta^mathtt{-1P} (S, a)</tex> for all {{---}} разбиение множества состояний ДКА,*<tex>\mathtt{R}</tex> in {{---}} класс состояний ДКА.  '''function''' findEquivalenceClasses<tex>P : R (Q,\cap l_a F,\ne \emptysetdelta)</tex> and : '''vector''' <tex>R \not mathtt{P} \leftarrow \{ F,\ Q \setminus F \subseteq l_a }</tex> do partition <tex>R\mathtt{S} \leftarrow \varnothing </tex> into '''for''' <tex>R_1c \in \Sigma</tex> and push <tex>R_2 : R_1 \leftarrow R langle F,\ c \cap l_a rangle</tex> and , <tex>R_2 \leftarrow R - R_1langle Q \setminus F,\ c \rangle</tex> replace '''into''' <tex>R<\mathtt{S}</tex> in '''while''' <tex>P\mathtt{S} \ne \varnothing</tex> with <tex>R_1\langle C,\ a \rangle</tex> and <tex>R_2\leftarrow</tex> if pop '''from''' <tex>R \in Wmathtt{S}</tex> then replace '''for''' <tex>R</tex> '''in ''' <tex>W\mathtt{P}</tex> with <tex>R_1, R_2 \leftarrow </tex> and <tex>R_2\mathtt{split}(R,\ C,\ a)</tex> else '''if ''' <tex> |R_1| \le |R_2|ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex> then add replace <tex>R_1R</tex> to '''in''' <tex>W\mathtt{P}</tex> else add with <tex>R_2R_1</tex> to '''and''' <tex>WR_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>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.|proof = Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется:<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 \ \land \ \delta(r, a) \notin R_1 \ \lor</tex>:<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>\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>R_2</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>\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 \ \land \ \delta(r, a) \in R_2 \ \lor</tex>:<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>\forall r \in B \,\,\, \delta(r, a) \in R \ \lor</tex>:<tex>\forall r \in B \,\,\, \delta(r, a) \notin 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>\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>.Кроме того, вместо очереди можно использовать вообще произвольную структуру, хранящую элементы, в том числе стэк, множество, так как порядок извлечения нам по сути не важен. ===Время работы=== {{Лемма|about = 1|id = Лемма1|statement =Количество классов, созданных во время выполнения алгоритма, не превышает <tex>2 |Q| - 1</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 (рус.)* ''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]