Изменения
Нет описания правки
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
'''for all ''' <tex>a \in \Sigma</tex> <tex>W</tex>'''.push'''(<tex>F, a</tex>) <tex>W</tex>'''.push'''(<tex>Q \setminus F, a</tex>) '''while not ''' <tex>W</tex>'''.isEmpty() ''' <tex>W</tex>'''.pop'''(<tex>S, a</tex>) '''for all ''' <tex>R</tex> '''in ''' <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
'''if ''' <tex> |R_1| \ne 0</tex> '''and ''' <tex>|R_2| \ne 0</tex> '''replace ''' <tex>R</tex> '''in ''' <tex>P</tex> '''with ''' <tex>R_1</tex> '''and ''' <tex>R_2</tex> <tex>W</tex>'''.push'''(<tex>R_1</tex>) <tex>W</tex>'''.push'''(<tex>R_2</tex>)
Когда очередь станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
===Время работы===
Время работы алгоритма оценивается как <tex>O(|\Sigma| * n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку.
== Алгоритм Хопкрофта==
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
'''if ''' <tex> |F| \le |Q \setminus F|</tex> '''for all ''' <tex>a \in \Sigma</tex> <tex>W</tex>'''.push'''(<tex>F, a</tex>)
else
'''for all ''' <tex>a \in \Sigma</tex> <tex>W</tex>'''.push'''(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
'''while not ''' <tex>W</tex>'''.isEmpty() ''' <tex>W</tex>'''.pop'''(<tex>S, a</tex>) '''for each ''' <tex>R</tex> '''in ''' <tex>P</tex> '''split by ''' <tex>S</tex> '''replace ''' <tex>R</tex> '''in ''' <tex>P</tex> '''with ''' <tex>R_1</tex> '''and ''' <tex>R_2</tex> '''if ''' (<tex>R, a</tex>) '''in ''' <tex>W</tex> '''replace ''' (<tex>R, a</tex>) '''in ''' <tex>W</tex> '''with ''' (<tex>R_1, a</tex>) '''and ''' (<tex>R_2, a</tex>) '''else''' '''if ''' <tex> |R_1| \le |R_2|</tex> <tex>W</tex>'''.push'''(<tex>R_1, a</tex>) '''else''' <tex>W</tex>'''.push'''(<tex>R_2, a</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>, получаем указанную оценку.<br>В случае с простым алгоритмом при последующем разбиении класса <tex>S</tex> в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>, отсюда получаем время работы <tex>O(|\Sigma| * n^2)</tex>указанная оценка.
== Литература ==
