Изменения
→Алгоритм Томпсона
===Асимптотика===
Так как количество подмножеств множества состояний НКА не более, чем <tex>2^n</tex>, а каждое подмножество мы обрабатываем ровно один раз за время <tex>O(n)</tex>, получаем верхнюю оценку времени работы алгоритма {{---}} <tex>O(n \cdot 2^n)</tex>.
===Пример===
Пусть нам дан исходный автомат [[Файл:DKA.jpg]].
По нашему заданию эквивалентного ДКА мы получаем [[Файл:NKA_definition.jpg]].
#Поместим в очередь множество из одной стартовой вершины - <tex>\{1\}</tex>: <tex>Q = \{\{1\}\}</tex>
#Вытащили из очереди множество <tex>\{1\}</tex>
#<tex>q_d(\{1\}, a) = \{1, 2\}</tex>, положили множество <tex>\{1, 2\}</tex> в очередь: <tex>Q = \{\{1, 2\}\}</tex>
#<tex>q_d(\{1\}, b) = \{1\}</tex>, нам не надо класть множество <tex>\{1\}</tex> в очередь, т.к. оно уже там было
#Вытащили из очереди множество <tex>\{1, 2\}</tex>: <tex>Q = \{\}</tex>
#<tex>q_d(\{1, 2\}, a) = \{1, 2\}</tex>, нам не надо класть множество <tex>\{1, 2\}</tex> в очередь, т.к. оно уже там было
#<tex>q_d(\{1, 2\}, b) = \{1, 2\}</tex>, нам не надо класть множество <tex>\{1, 2\}</tex> в очередь, т.к. оно уже там было
А в итоге получили эквивалентный ДКА, чуть меньше: [[Файл:NKA_algorithm.jpg]].
