244
правки
Изменения
Нет описания правки
===Пример===
Пусть нам дан [[Недетерминированные конечные автоматы|недетерменированный конечный автомат]]: [[Файл:DKA.jpgpng]]
По нашему заданию эквивалентного ДКА мы получаем: [[Файл:NKA_definition.png]]
#Помещаем в очередь множество из одной стартовой вершины — <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>\{1, 2\}</tex>.
В итоге получаем ДКА, эквивалентный исходному: [[Файл:NKA_algorithm.jpgpng]].
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
