403
правки
Изменения
Нет описания правки
{{Определение
|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>F</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a c \in \Sigma</tex>, все пары <tex>(F, ac)</tex> и <tex>(Q \setminus F, ac)</tex> помещаются в очередь.# Из очереди извлекается пара <tex>(SC, a)</tex>, <tex>SC</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>WS</tex> {{---}} очередьпар <tex>(C, a)</tex>.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>\mathtt{P } \leftarrow \{ \mathtt{ F, Q } \setminus \mathtt{F } \}</tex> <tex>W \mathtt{S} \leftarrow \{ \}varnothing </tex> '''for all''' <tex>a c \in \Sigma</tex> '''insert''' <tex>W(\mathtt{F}, c)</tex>'''.pushin'''(<tex>F, a\mathtt{S}</tex>) '''insert''' <tex>W(\mathtt{Q} \setminus \mathtt{F}, c)</tex>'''.pushin'''(<tex>Q \setminus F, amathtt{S}</tex>) '''while not''' <tex>W\mathtt{S} \ne \varnothing </tex>'''.isEmpty()''' <tex>W(C, a) \leftarrow</tex>'''.pop'''(<tex>\mathtt{S, a}</tex>) '''for all''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> <tex>R_1 = R \cap \delta^{-1} (SC, a) </tex>
<tex>R_2 = R \setminus R_1</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 all''' <tex> c \in \Sigma </tex> '''insert''' <tex>W(R_1, c)</tex>'''.pushin'''(<tex>R_1, c\mathtt{S}</tex>) '''insert''' <tex>W(R_2, c)</tex>'''.pushin'''(<tex>R_2, c\mathtt{S}</tex>)Когда очередь <tex>S</tex> станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
===Время работы===
Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(SC, a)</tex> попала в очередь, и класс <tex>SC</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>S_1C_1</tex> и <tex>S_2C_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|SC| \ge |S_iC_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку.
== Алгоритм Хопкрофта==
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.
===ПсевдокодРеализация===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>WS</tex> {{---}} очередьиз пар <tex>(C, a)</tex>.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>\mathtt{P } \leftarrow \{ \mathtt{ F, Q } \setminus \mathtt{F } \}</tex> <tex>W \mathtt{S} \leftarrow \{ \}varnothing </tex> '''for all''' <tex>a c \in \Sigma</tex> <tex>W</tex>'''.pushinsert'''<tex> ('''\mathtt{min'''} (<tex>\mathtt{F, Q } \setminus \mathtt{F}), c)</tex>), '''in''' <tex>a\mathtt{S}</tex>) '''while not''' <tex>W\mathtt{S} \ne \varnothing</tex>'''.isEmpty()''' <tex>W(C, a) \leftarrow</tex>'''.pop'''(<tex>\mathtt{S}</tex>) <tex>T \leftarrow \{R \ | \ R \in \mathtt{P}, \ R</tex> splits by <tex>(C, a) \}</tex>) '''for each''' <tex>R</tex> '''in''' <tex>PT</tex> <tex> R_1, R_2 \leftarrow </tex> '''split by''' (<tex>(SR, C, a)</tex> ) '''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex> '''iffor''' (<tex>R, a</tex>) '''c \in''' <tex>W\Sigma</tex> '''replaceif''' (<tex>(R, ac)</tex>) '''in''' <tex>W\mathtt{S}</tex> '''withreplace''' (<tex>R_1(R, ac)</tex>) '''andin''' (<tex>R_2, a\mathtt{S}</tex>) '''else''' '''ifwith''' <tex> |(R_1| \le |R_2|</tex> <tex>W, c)</tex>'''.pushand'''(<tex>R_1(R_2, ac)</tex>)
'''else'''
'''insert''' <tex>W(\mathtt{min}(R_1, R_2), c)</tex>'''in''' <tex>\mathtt{S}</tex> К сожалению, совсем не очевидно, как быстро находить множество <tex>T</tex>.pushС другой стороны, понятно, что <tex>T \subset T'</tex>, где <tex>T'</tex> {{---}} это множество классов текущего разбиения, из состояний которых в автомате существует переход в состояния сплиттера <tex>C</tex> по символу <tex>a</tex>. Модифицируем наш алгоритм: для каждой очередной пары <tex> (C, a) </tex> будем находить <tex> T'</tex>, и с каждым классом состояний из <tex> T' </tex> будем производить те же действия, что и раньше. <tex>\mathtt{P} \leftarrow \{ \mathtt{F, Q} \setminus \mathtt{F} \}</tex> <tex>\mathtt{S} \leftarrow \varnothing </tex> '''for''' <tex>c \in \Sigma</tex> '''insert''' <tex>(\mathtt{min} (\mathtt{F, Q} \setminus \mathtt{F}), c)</tex>'''in''' <tex>\mathtt{S}</tex> '''while''' <tex>\mathtt{S} \ne \varnothing</tex> <tex>(C, a) \leftarrow</tex> '''pop'''(<tex>\mathtt{S}</tex>) <tex>\mathtt{Inverse} \leftarrow \{r \ | \ r \in \mathtt{Q}, \ \delta(r, a) \in C\}</tex> <tex>T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}</tex> '''for each''' <tex>R</tex> '''in''' <tex>T'</tex> '''if''' <tex>R</tex> splits by <tex>(C, a)</tex> <tex> R_1, R_2\leftarrow </tex> '''split'''(<tex>R, C, a</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> '''if''' <tex>(R, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''replace''' <tex>(R, c)</tex> '''in''' <tex>S</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex> '''else''' '''insert''' <tex>(\mathtt{min}(R_1, R_2), c)</tex> '''in''' <tex>\mathtt{S}</tex> Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|Inverse|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки. Разбиение <tex> P </tex> можно поддерживать четырьмя массивами:*<tex>Class[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>;*<tex>Part[i]</tex> {{---}} указатель на голову [[Список#Двусвязный список|двусвязного списка]], содержащего состояния, принадлежащие классу <tex> i </tex>;*<tex>Card[i]</tex> {{---}} количество состояний в классе <tex>i</tex>;*<tex>Place[r]</tex> {{---}} указатель на состояние <tex>r</tex> в списке <tex>Part[Class[r]]</tex>. Так как мы храним указатель, где находится состояние в двусвязном списке, то операцию перемещения состояния из одного класса в другой можно выполнить за <tex>O(1)</tex>. Чтобы эффективно находить множество <tex>Inverse</tex>, построим массив <tex>Inv</tex>, который для состояния <tex>r</tex> и символа <tex>a</tex> в <tex>Inv[r][a]</tex>хранит множество состояний, из которых существует переход в <tex>r</tex> по символу <tex>a</tex>. Так как наш алгоритм не меняет изначальный автомат, то массив <tex>Inv</tex> можно построить перед началом основной части алгоритма, что займет <tex>O(|\Sigma| |Q|)</tex> времени. Теперь научимся за <tex>O(|Inverse|)</tex> обрабатывать множество <tex>T'</tex> и разбивать классы. Для этого нам понадобится следующая структура:*<tex>Counter</tex> {{---}} количество классов;*<tex>Involved</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>;*<tex>Size</tex> {{---}} целочисленный массив, где <tex>Size[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>Inverse</tex>;*<tex>Twin</tex> {{---}} массив, хранящий в <tex>Twin[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>. Сам же алгоритм обработки <tex>T'</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}[q]</tex> '''if''' <tex>\mathtt{Size}[i] == 0</tex> '''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex> <tex>\mathtt{Size}[i]++</tex> '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> <tex>i = \mathtt{Class}[q]</tex> '''if''' <tex>\mathtt{Size}[i] < \mathtt{Card}[i]</tex> '''if''' <tex>\mathtt{Twin}[i] == 0</tex> <tex>\mathtt{Counter}++</tex> <tex>\mathtt{Twin[i]} = \mathtt{Counter}</tex> '''move''' <tex>r</tex> '''from''' <tex>i</tex> '''to''' <tex>\mathtt{Twin}[i]</tex> '''for''' <tex> j \in \mathtt{Involved}</tex> <tex>\mathtt{Size}[j] = 0</tex> <tex>\mathtt{Twin}[j] = 0</tex> Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>InQueue</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>InQueue[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди. Так как при разбиении очередного класса <tex>R</tex> на подклассы <tex>R_1</tex> и <tex>R_2</tex> мы в действительности создаем лишь один новый класс, то замена класса <tex>R</tex> в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом <tex>InQueue</tex>. В результате каждая операция с очередью требует <tex>O(1)</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.
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]