Алгоритм построения ДКА по НКА

Для всякого недетерминированного конечного автомата можно построить детерминированный конечный автомат, задающий точно такой же язык. Вершины ДКА - это подмножества множества вершин исходного НКА. Чтобы получить вершину ДКА (т.е. подмножество вершин исходного НКА), в которую осуществляется переход по данному символу из данной вершины ДКА (т.е. из подмножества M вершин НКА), надо объединить все вершины НКА, которые получаются всевозможными переходами по данному символу из всех вершин подмножества M, а затем добавить также вершины, достижимые с помощью переходов по пустой цепочке. Начальная вершина ДКА - это объединение всех начальных вершин НКА плюс вершины, достижимые из начальных с помощью переходов по пустым цепочкам. Конечные вершины ДКА - это подмножества вершин исходного НКА, содержащие хотя бы одну конечную вершину.

Примеры: (с 84)

ДКА эквивалентный НКА показанному на рис. выше

Шаг 1. Из состояния q0 по символу b попадаем в состояние q0, по символу a попадаем в состояние q0+q1.

Шаг 2. Из q0+q1по b попадаем в q0+q2, по a в q0+q1+q2.

Шаг 3. Из q0+q2по b попадаем в q0, по a - в q0+q1. Из q0+q1+q2 по b попадаем в q0+q2, по a - в q0+q1+q2.

Полезное расширение стандартного НКА – ε-НКА, или НКА с эпсилон-переходами.

«Эпсилон-переходом» называется переход между состояниями, который может быть выполнен автоматом «просто так», без входного символа. На графах и в таблицах такие переходы обычно помечаются символом ε.

Одно из наиболее полезных свойств ε-переходов – возможность простого объединения нескольких автоматов в один.

Пример:

В данном случае объединяемыми автоматами являются НКА, изображённые на рисунке 5, а результирующий автомат рис. 6 допускает цепочки, допустимые хотя бы одним из них.

Рис. 5 Составные части автомата, показанного на рис.6

Рис.6 ε- НКА