Структуры данных и модели вычислений

         

Автоматное задание языков


Недетерминированные конечные автоматы

с -переходами. Недетерминированным конечным автоматом с -переходами над алфавитом называется набор

где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний ( и — переходная функция.

Такой автомат можно представить нагруженным ориентированным мультиграфом (диаграммой) следующим образом. Вершинами графа объявить состояния, то есть элементы множества , и если , то из состояния в состояние провести дугу, помеченную символом .

Язык , порождаемый автоматом , состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния , по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества не обязательно при первом попадании туда. При чтении символов следует воспринимать

как пустое слово.

Пример.

Пусть алфавит , , и переходная функция задана таблицей

Диаграмма автомата изображена на рис. 13.1


Рис. 13.1. 

Недетерминированные конечные автоматы без

-переходов. Недетерминированным конечным автоматом без -переходов над алфавитом называется набор

где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и

— переходная функция. Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие в том, что дуги теперь могут быть помечены только символами алфавита .

Язык , порождаемый таким автоматом , состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния , по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества не обязательно при первом попадании туда.

Детерминированные конечные автоматы. Детерминированным конечным автоматом над алфавитом называется набор

где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и — переходная функция.

Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие от недетерминированного автомата состоит в том, что из каждого состояния выходит ровно одна дуга, помеченная конкретной буквой алфавита .



Содержание  Назад  Вперед