Изменения

Перейти к: навигация, поиск

Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Нет изменений в размере, 05:55, 21 января 2012
Нет описания правки
Пусть нам дан [[Недетерминированные конечные автоматы|недетерменированный конечный автомат]]: [[Файл:DKA.jpg]]
По нашему заданию эквивалентного ДКА мы получаем: [[Файл:NKA_definition.jpgpng]]
#Помещаем в очередь множество из одной стартовой вершины — <tex>\{1\}</tex>: <tex>Q = \{\{1\}\}</tex>.
#Помечаем все терминальные вершины, в данном случае — <tex>\{1, 2\}</tex>.
В итоге получаем ДКА, эквивалентный исходному: [[Файл:NKA_algorithm.pngjpg]].
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
Анонимный участник

Навигация