172
правки
Изменения
→Псевдокод
<tex>P</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 elsefor 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 all <tex>a \in \Sigma</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> |\Sigma| * n </tex>, участвует не более чем в <tex> \log{n}</tex> разбиениях.
