Изменения

Перейти к: навигация, поиск
Простой алгоритм
{{Определение
|definition =
Класс <tex>SC</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 SC</tex> # <tex>\forall r \in R_2 \,\,\, \delta(r, a) \notin SC</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>QF</tex> и класс недопускающих состояний (<tex>\mathtt{P} \leftarrow \{ F, \ Q \setminus F\}</tex>).# Перебираются символы алфавита <tex>a c \in \Sigma</tex>, все пары <tex>(Q\langle F, a)\ c \rangle</tex> и <tex>(\langle Q \setminus F, a)c \rangle</tex> помещаются в очередь.# Из очереди извлекается пара <tex>(S\langle C, \ a)\rangle</tex>, <tex>SC</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.
===Псевдокод===
*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА.,*<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний.,*<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{---}} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>),*<tex>W\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>W \mathtt{S} \leftarrow \{ \}varnothing </tex> '''for all ''' <tex>a c \in \Sigma</tex> push <tex>W\langle F,\ c \rangle</tex>.push(, <tex>\langle Q \setminus F, a\ c \rangle</tex>) '''into''' <tex>W\mathtt{S}</tex>.push( '''while''' <tex>Q \setminus F, amathtt{S} \ne \varnothing</tex>) while not <tex>W\langle C,\ a \rangle</tex>.isEmpty() <tex>W\leftarrow</tex>.pop('''from''' <tex>\mathtt{S, a}</tex>) '''for all ''' <tex>R</tex> '''in ''' <tex>\mathtt{P}</tex> <tex>R_1 = R , R_2 \cap \delta^{-1} (S, a) leftarrow </tex> <tex>R_2 = \mathtt{split}(R ,\ C,\setminus R_1a)</tex> '''if ''' <tex> |R_1| \ne 0\varnothing </tex> '''and ''' <tex>|R_2| \ne 0\varnothing </tex> replace <tex>R</tex> '''in ''' <tex>\mathtt{P}</tex> with <tex>R_1</tex> '''and ''' <tex>R_2</tex> '''for''' <tex>Wc \in \Sigma</tex>.push( insert <tex>\langle R_1,\ c \rangle</tex> '''in''' <tex>\mathtt{S}</tex>) insert <tex>\langle R_2,\ c \rangle</tex> '''in''' <tex>W\mathtt{S}</tex>.push( '''return''' <tex>R_2\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>.
{{Лемма
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \ \land \ \delta(r, a) \in R_1\ \lor</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \ \land \ \delta(r, a) \notin R_1\ \lor</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \ \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> or
:<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</tex> and <tex> \ \land \ \delta(r, a) \notin R_2\ \lor</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \ \land \ \delta(r, a) \in R_2\ \lor</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \ \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> or :<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>B\langle C,\ a \rangle</tex> из текущего разбиения выполняется ).  '''function''' findEquivalenceClasses<tex>(Q,\ F,\ \delta)</tex>:'''vector''' <tex>\forall r mathtt{P} \leftarrow \{ F, \ Q \setminus F \}</tex> <tex>\mathtt{S} \leftarrow \varnothing </tex> '''for''' <tex>c \in B \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> or : replace <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> with <tex>R_1</tex> '''and''' <tex>R_2</tex> '''if''' <tex> \forall r langle R,\ c \rangle</tex> '''in B ''' <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 \deltarangle</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}\notin R,</tex> аллоцируются ровно один раз при инициализации алгоритма. то Также стоит отметить, что собственно наличие/отсутствие пары в очередь очереди можно добавить только меньшее из не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle i, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>R_1\langle \mathtt{Twin}[i], c \rangle</tex> . Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>R_2\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>F2 |\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>Wp \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>P\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>Ry \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>W O(\leftarrow sum(|\mathtt{ Inverse}|))\,</tex> времени. Но по [[#Лемма4 | лемме(4)]] <tex>\sum(|\mathtt{Inverse}|)\,</tex> if не превосходит <tex> |F\Sigma| |Q| \log_2(|Q|)</tex>, то есть данная часть алгоритма выполняется за <tex>O(| \le Sigma| |Q | \setminus Flog_2(|Q|))</tex>. for all *В [[#Лемма1 | лемме(1)]] мы показали, что в процессе работы алгоритма не может появится больше, чем <tex>2 |Q| - 1</tex> классов, из чего следует, что количество операций <tex>a \in mathtt{replace}</tex> равно <tex>O(|\Sigma| |Q|)</tex>.  Итого, получается, что время работы алгоритма Хопкрофта не превышает <tex>WO(|\Sigma| |Q|) + O(|\Sigma| |Q|) + O(|\Sigma| |Q| \log_2(|Q|)) + O(|\Sigma| |Q|) = O(|\Sigma| |Q| \log_2(|Q|))</tex>.push}} === Альтернативная реализация ===Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее). Все классы разбиения будем по-прежнему хранить в векторе хэш-сетов <tex>\mathtt{P}</tex>. *<tex>\mathtt{Class}[r]</tex> {{---}} индекс класса в <tex>\mathtt{P}</tex>F, aкоторому принадлежит состояние <tex>r</tex>), else for all *<tex>\mathtt{Queue}</tex> {{---}} очередь из пар <tex>\langle C,\ a \in rangle</tex>,*<tex>\Sigmamathtt{Inv}[r][a]</tex> {{---}} массив состояний, из которых есть ребра по символу <tex>a</tex> в состояние <tex>r</tex>(мы не меняем исходный автомат, потому может быть построен раз перед началом работы алгоритма), *<tex>W\mathtt{Involved}</tex>{{---}} ассоциативный массив из номеров классов в векторы из номеров вершин.push(  <tex>\mathtt{findEquivalenceClasses}(Q ,\setminus F, a\ \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 not ''' <tex>W\mathtt{Queue} \ne \varnothing</tex>.isEmpty() <tex>\langle C,\ a \rangle</tex> <tex>W\leftarrow</tex>.pop('''from''' <tex>\mathtt{Queue}</tex> <tex>S, a\mathtt{Involved} = \{\}</tex>) '''for each ''' <tex>Rq \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> <tex>Pi = \mathtt{Class}[r]</tex> '''if''' <tex>\mathtt{Involved}[i] == \varnothing</tex> split by <tex>S\mathtt{Involved}[i] = \{\}</tex> replace add <tex>r</tex> '''to''' <tex>R\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> with '''insert''' <tex>R_1\{\}</tex> and '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>//Создадим пустой класс в разбиении <tex>R_2\mathtt{P}</tex></font> if ( <tex>R, aj = |\mathtt{P}|</tex>) in <font color=darkgreen>//Запишем в <tex>Wj</tex> индекс нового класса</font> replace ( '''for''' <tex>R, ar</tex>) '''in ''' <tex>W\mathtt{Involved}[i]</tex> with ( remove <tex>R_1, ar</tex>) and ('''from''' <tex>R_2, a\mathtt{P}[i]</tex>) else add <tex>r</tex> '''to''' <tex>\mathtt{P}[j]</tex> '''if ''' <tex> |R_1\mathtt{P}[j]| > | \le |R_2mathtt{P}[i]|</tex> <font color=darkgreen>//Парный класс должен быть меньшего размера</font> <tex>W\mathtt{swap}(\mathtt{P}[i],\ \mathtt{P}[j])</tex>.push<font color=darkgreen>//swap за <tex>\mathtt{O(1)}</tex> {{---}} просто переставить указатели</font> '''for''' <tex>r \in \mathtt{P}[j]</tex>R_1<font color=darkgreen>//Обновляем номера классов для вершин, aу которых они изменились</font> <tex>\mathtt{Class}[r] = j</tex>) else '''for''' <tex>Wc \in \Sigma</tex>. push(<tex>R_2\langle j, ac \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex> '''return''' <tex>\mathtt{P}</tex>) == См. также ==
==Время работы алгоритма==Время работы алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовася в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</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]
 
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
295
правок

Навигация