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>\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> времени.
