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

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

Q - конечное множество состояний,
T - конечное множество допустимых входных символов (входной алфавит),
D - функция переходов (отображающая множество
$Q \times (T \cup \{e\})$
во множество подмножеств множества Q), определяющая поведение управляющего устройства,
$q_0 \in Q$
- начальное состояние управляющего устройства,
$F \subseteq Q$
- множество заключительных состояний.

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

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

Рис. 3.2.

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

$(q, w) \in Q \times T^*$

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

$q \in F$

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

$\vdash$

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

$p \in D(q, a)$

, где

$a 2\in T \cup \{e\}, \; \text{то} \; (q, aw) \vdash (p, w)$

для всех

$w 2\in T^*$

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

$\vdash^+ (\vdash^*)$

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

$\vdash$

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

$(q_0, w) \vdash^* (q, e)$

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

$q \in F$

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

$L(M)=\{w \mid w \in T^* \; \text{и} \; (q_0,w) \vdash^* (q,e) \; \text{для некоторого} \; q \in F \}$

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

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