Изменения

Пусть нам дан исходный [[Недетерминированные конечные автоматы|недетерменированный конечный автомат ]]: [[Файл:DKA.jpg]].

По нашему заданию эквивалентного ДКА мы получаем : [[Файл:NKA_definition.jpg]].

#Поместим Помещаем в очередь множество из одной стартовой вершины - — <tex>\{1\}</tex>: <tex>Q = \{\{1\}\}</tex>.#Вытащили Достаём из очереди множество <tex>\{1\}</tex>: <tex>Q = \{\}</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> в очередь, т.к. оно уже там было.#Пометим Помечаем все терминальные вершины, в данном случае - — <tex>\{1, 2\}</tex>.

А в В итоге получили эквивалентный получаем ДКА, чуть меньшеэквивалентный исходному: [[Файл:NKA_algorithm.jpg]].