403
правки
Изменения
м
→Реализация
===Реализация===
<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА.<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний.<tex>\mathtt{S}</tex> {{---}} очередь из пар <tex>(C, a)</tex>.<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА.<tex>R</tex> {{---}} класс состояний ДКА.
<tex>\mathtt{P} \leftarrow \{ \mathtt{F, Q} \setminus \mathtt{F} \}</tex>
Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|\mathtt{Inverse}|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки.
Разбиение <tex> \mathtt{P} </tex> можно поддерживать четырьмя массивами:
*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>;
*<tex>\mathtt{Part}[i]</tex> {{---}} указатель на голову [[Список#Двусвязный список|двусвязного списка]], содержащего состояния, принадлежащие классу <tex> i </tex>;
<tex>\mathtt{Twin}[j] = 0</tex>
Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>\mathtt{S}</tex>, будем использовать массив <tex>\mathtt{InQueue}</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>\mathtt{InQueue}[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди.
Так как при разбиении очередного класса <tex>R</tex> на подклассы <tex>R_1</tex> и <tex>R_2</tex> мы в действительности создаем лишь один новый класс, то замена класса <tex>R</tex> в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом <tex>\mathtt{InQueue}</tex>. В результате каждая операция с очередью требует <tex>O(1)</tex> времени.
