403
правки
Изменения
м
→Реализация
<tex>S \leftarrow \varnothing </tex>
'''for''' <tex>c \in \Sigma</tex>
'''insert''' <tex> insert \ (min (F, Q \setminus F), c)</tex> '''toin''' <tex>S</tex>
'''while''' <tex>S \ne \varnothing</tex>
<tex>(C, a) \leftarrow </tex> '''pop'''(<tex>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> '''split(<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>
'''replace''' <tex>replace \ (R, c)</tex> '''in''' <tex>S</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex>
'''else'''
'''insert''' <tex>insert \ (min(R_1, R_2), c)</tex> '''toin''' <tex>S</tex>
Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|Inverse|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки.
