Конечные автоматы

Регулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы. Недетерминированный конечный автомат (НКА) - по определению есть пятерка M = (Q, T, D, q0, F), где

Q - конечное множество состояний,
T - конечное множество допустимых входных символов (входной алфавит),
D - функция переходов (отображающая множество
во множество подмножеств множества Q), определяющая поведение управляющего устройства,
- начальное состояние управляющего устройства,
- множество заключительных состояний.

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

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

Рис. 3.2.

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара

, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q0, w) называется начальной, а конфигурация (q, e), где

- заключительной (или допускающей). Тактом автомата M называется бинарное отношение

, определенное на конфигурациях M следующим образом: если

, где

для всех

Будем обозначать символом

транзитивное (реф- лексивно-транзитивное) замыкание отношения

. Будем говорить, что автомат M допускает цепочку w, если

для некоторого

. Языком, допускаемым, (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. То есть,

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

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий