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>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W S \leftarrow \{ \}varnothing </tex> '''for all''' <tex>a c \in \Sigma</tex> <tex>WS</tex>'''.push'''(<tex>F, ac</tex>) <tex>WS</tex>'''.push'''(<tex>Q \setminus F, ac</tex>) '''while not''' <tex>WS</tex>'''.isEmpty()''' () <tex>W(C, a)</tex> <tex> \leftarrow </tex> <tex>S</tex>'''.pop'''(<tex>S, a</tex>)
'''for all''' <tex>R</tex> '''in''' <tex>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>P</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
'''for all''' <tex> c \in \Sigma </tex>
<tex>WS</tex>'''.push'''(<tex>R_1, c</tex>) <tex>WS</tex>'''.push'''(<tex>R_2, c</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>, получаем указанную оценку.
== Алгоритм Хопкрофта==
