Недетерминированные конечные автоматы
с -переходами. Недетерминированным конечным автоматом с -переходами над алфавитом называется набор
где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний ( и — переходная функция.
Такой автомат можно представить нагруженным ориентированным мультиграфом (диаграммой) следующим образом. Вершинами графа объявить состояния, то есть элементы множества , и если , то из состояния в состояние провести дугу, помеченную символом .
Язык , порождаемый автоматом , состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния , по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества не обязательно при первом попадании туда. При чтении символов следует воспринимать
как пустое слово.
Пример.
Пусть алфавит , , и переходная функция задана таблицей
Диаграмма автомата изображена на рис. 13.1
Рис. 13.1.
Недетерминированные конечные автоматы без
-переходов. Недетерминированным конечным автоматом без -переходов над алфавитом называется набор
где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и
— переходная функция. Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие в том, что дуги теперь могут быть помечены только символами алфавита .
Язык , порождаемый таким автоматом , состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния , по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества не обязательно при первом попадании туда.
Детерминированные конечные автоматы. Детерминированным конечным автоматом над алфавитом называется набор
где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и — переходная функция.
Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие от недетерминированного автомата состоит в том, что из каждого состояния выходит ровно одна дуга, помеченная конкретной буквой алфавита .