403
правки
Изменения
м
→Реализация
<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{min } (\mathtt{F, Q } \setminus \mathtt{F}), c)</tex> '''in''' <tex>\mathtt{S}</tex>
'''while''' <tex>S \ne \varnothing</tex>
<tex>(C, a) \leftarrow</tex> '''pop'''(<tex>\mathtt{S}</tex>) <tex>T = \{R \ | \ R \in \mathtt{P}, \ R</tex> '''split by''' <tex>(C, a) \}</tex>
'''for each''' <tex>R</tex> '''in''' <tex>T</tex>
<tex> R_1, R_2 \leftarrow </tex> '''split'''(<tex>R, C, a</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>
'''if''' <tex>(R, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''replace''' <tex> (R, c)</tex> '''in''' <tex>\mathtt{S}</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex>
'''else'''
'''insert''' <tex>(\mathtt{min}(R_1, R_2), c)</tex> '''in''' <tex>\mathtt{S}</tex>
К сожалению, совсем не очевидно, как быстро находить множество <tex>T</tex>. С другой стороны, понятно, что <tex>T \subset T'</tex>, где <tex>T'</tex> {{---}} это множество классов текущего разбиения, из состояний которых в автомате существует переход в состояния сплиттера <tex>C</tex> по символу <tex>a</tex>.
Модифицируем наш алгоритм: для каждой очередной пары <tex> (C, a) </tex> будем находить <tex> T' </tex>, и с каждым классом состояний из <tex> T' </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{min } (\mathtt{F, 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>) <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 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>R, C, a</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>
'''if''' <tex>(R, c)</tex> '''in''' <tex>\mathtt{S}</tex>
'''replace''' <tex>(R, c)</tex> '''in''' <tex>S</tex> '''with''' <tex>(R_1, c)</tex> '''and''' <tex>(R_2, c)</tex>
'''else'''
'''insert''' <tex>(\mathtt{min}(R_1, R_2), c)</tex> '''in''' <tex>\mathtt{S}</tex>
Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|Inverse|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки.
Сам же алгоритм обработки <tex>T'</tex> будет выглядеть так:
<tex>\mathtt{Involved } \leftarrow \varnothing</tex> '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> <tex>i = \mathtt{Class}[q]</tex> '''if''' <tex>\mathtt{Size}[i] == 0</tex> '''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex> <tex>\mathtt{Size}[i]++</tex> '''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex> <tex>i = \mathtt{Class}[q]</tex> '''if''' <tex>\mathtt{Size}[i] < \mathtt{Card}[i]</tex> '''if''' <tex>\mathtt{Twin}[i] == 0</tex> <tex>\mathtt{Counter}++</tex> <tex>\mathtt{Twin[i] } = \mathtt{Counter}</tex> '''move''' <tex>r</tex> '''from''' <tex>i</tex> '''to''' <tex>\mathtt{Twin}[i]</tex> '''for''' <tex> j \in \mathtt{Involved}</tex> <tex>\mathtt{Size}[j] = 0</tex> <tex>\mathtt{Twin}[j] = 0</tex>
Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>InQueue</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>InQueue[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди.
