19
правок
Изменения
Нет описания правки
'''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>
<tex>\mathtt{pushSetsToQueue}(S,\ R,\ R_1,\ R_2)</tex>
'''return''' <tex>\mathtt{P}</tex>
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R,\ R_1,\ R_2)</tex>:
<tex>\mathrm{cnt1} \leftarrow |\mathtt{P}[R_1]|</tex>
<tex>\mathrm{cnt2} \leftarrow |\mathtt{P}[R_2]|</tex>
'''for''' <tex>c \in \Sigma</tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex>
'''remove''' <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''if''' <tex> \mathrm{cnt1} \leqslant \mathrm{cnt2} </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</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>
<tex>\mathtt{pushSetsToQueue}(S,\ R,\ R_1,\ R_2)</tex>
'''return''' <tex>\mathtt{P}</tex>
