Изменения
Нет описания правки
Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний (<tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>).
# Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <<tex>F,\ c</tex>> и <<tex>Q \setminus F, c</tex>> помещаются в очередь.
# Из очереди извлекается пара <<tex>C,\ a</tex>>, <tex>C</tex> далее именуется как сплиттер.
*<tex>R</tex> {{---}} класс состояний ДКА.
<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex> <tex>\mathtt{P} \leftarrow \{ \mathtt{F,\ Q} \setminus \mathtt{F} \}</tex>
<tex>\mathtt{S} \leftarrow \varnothing </tex>
'''for''' <tex>c \in \Sigma</tex>
*<tex>R</tex> {{---}} класс состояний ДКА.
<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex> <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>
<tex>\mathtt{S} \leftarrow \varnothing </tex>
'''for''' <tex>c \in \Sigma</tex>
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за T' (его нужно будет эффективно находить для каждой пары <<tex>C,\ a</tex>>).
<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex> <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>
<tex>\mathtt{S} \leftarrow \varnothing </tex>
'''for''' <tex>c \in \Sigma</tex>
'''while''' <tex>\mathtt{S} \ne \varnothing</tex>
<<tex>C,\ a</tex>> <tex>\leftarrow</tex> '''pop''' '''from''' <tex>\mathtt{S}</tex>
<tex>\mathtt{Inverse} \leftarrow \{r \ | \ r \in \mathtt{Q}, \ \delta(r, a) \in C\}</tex>
<tex>T' \leftarrow \{R \ | \ R \in \mathtt{P}, \ R \cap \mathtt{Inverse} \neq \varnothing\}</tex>
'''for''' <tex>R</tex> '''in''' <tex>T'</tex>
*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.
<tex>\mathtt{findEquivalenceClasses}(\mathtt{Q},\ \mathtt{F},\ \delta)</tex> <tex>\mathtt{P} \leftarrow \{ \mathtt{F, \ Q} \setminus \mathtt{F} \}</tex>
'''for''' <tex>c \in \Sigma</tex>
'''push''' <<tex>F,\ c</tex>>, <<tex>Q \setminus F,\ c</tex>> '''into''' <tex> \mathtt{Queue}</tex>
