403
правки
Изменения
Нет описания правки
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>S</tex> {{---}} очередьмножество пар <tex>(C, a)</tex>.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>S \leftarrow \varnothing </tex>
'''for all''' <tex>c \in \Sigma</tex> <tex>Sinsert</tex> <tex>(F, c)</tex>'''.pushto'''(<tex>F, cS</tex>) <tex>Sinsert</tex>'''.push'''(<tex>(Q \setminus F, c)</tex>) '''while notto''' <tex>S</tex> '''.isEmptywhile'''() <tex>(C, a)S \ne \varnothing </tex> <tex> \leftarrow remove</tex> <tex>S(C, a)</tex>'''.popfrom'''()<tex>S</tex> '''for all''' <tex>R</tex> '''in''' <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (C, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
Когда очередь станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
