403
правки
Изменения
м
→Псевдокод
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</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{F}, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''insert''' <tex>(\mathtt{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>) '''for''' <tex>R</tex> '''in''' <tex>\mathtt{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>
'''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> '''insert''' <tex>(R_1, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''insert''' <tex>(R_2, c)</tex> '''in''' <tex>\mathtt{S}</tex>
Когда очередь <tex>S</tex> станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
