Изменения

<tex> insert </tex> <tex>\ (min (F, Q \setminus F), c)</tex> '''to''' <tex>S</tex>

<tex>remove (C, a) \leftarrow pop(S)</tex> <tex>(CT = \{R \ | \ R \in P, a)\ R</tex> '''fromsplit by''' <tex>S(C, a) \}</tex> '''for each''' <tex>R</tex> '''in''' <tex>P</tex> '''split by''' <tex>(C, a)T</tex>

<tex>replace</tex> <tex>\ (R, c)</tex> '''in''' <tex>S</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex>

<tex>insert\ (min(R_1, R_2), c)</tex> '''to''' <tex>S</tex> К сожалению, совсем не очевидно, как быстро находить множество <tex>T</tex>. С другой стороны, понятно, что <tex>T</tex> {{---}} это подмножество классов текущего разбиения, из которых в ДКА существует переход в сплиттер <tex>C</tex> по символу <tex>a</tex>. Пусть <tex>Inverse = \{r \ | \ r \in Q, \ \delta(r, a) \in C\}</tex>, а <tex>T' = \{R \ | \ R \in P, \ R \cap Inverse \neq \varnothing\}</tex>. Тогда <tex> T \subset T'</tex>. Модифицируем наш алгоритм: для каждой очередной пары <tex> (C, a) </tex> будем находить <tex> T' </tex>, и с каждым классом состояний из <tex> T' </tex> будем производить те же действия, что и раньше.  <tex>P \leftarrow \{ F, Q \setminus F \}</tex> <tex>S \leftarrow \varnothing </tex> '''for''' <tex>c \in \Sigma</tex> <tex> insert \ (min (F, Q \setminus F), c)</tex> '''to''' <tex>S</tex> '''while''' <tex>S \ne \varnothing</tex> <tex>(C, a) \leftarrow pop(S)</tex> <tex>Inverse \leftarrow \{r \ | \ r \in Q, \ \delta(r, a) \in C\}</tex> <tex>T' \leftarrow \{R \ | \ R \in P, \ R \cap Inverse \neq \varnothing\}</tex> '''for each''' <tex>R</tex> '''in''' <tex>T'</tex> '''if''' <tex>R</tex> '''split by''' <tex>(C, a)</tex> <tex> R_1, R_2 \leftarrow </tex> <tex> split(R, C, a) </tex> <tex>replace</tex> <tex>R</tex> '''in''' <tex>P</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex> '''for''' <tex>c \in \Sigma</tex> '''if''' <tex>(R, c)</tex> '''in''' <tex>S</tex> <tex>replace \ (R, c)</tex> '''in''' <tex>S</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex> '''else''' <tex>insert \ (min(R_1, R_2), c)</tex> '''to''' <tex>S</tex>