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

Конечный автомат (Finite-state automation) — распознаватель, используемый для задания регулярных множеств. Конечный автомат состоит из входной ленты, входной головки и управляющего устройства. Входная лента — это линейная последовательность клеток, или ячеек, каждая из которых может содержать любой символ из $\mathrm{\Sigma }$. В каждый данный момент входная головка читает, или, как иногда говорят, обозревает одну входную ячейку, а управляющее устройство находится в одном состоянии из конечного множества $Q$, т.е. имеет конечную память.

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

Недетерминированный конечный автомат (или просто конечный автомат) — это пятерка $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$, в которой

(1) $Q$ — конечное множество состояний;

(2) $\mathrm{\Sigma }$ — конечное множество допустимых входных символов;

(3) $\delta$ — отображение множества $Q\times \mathrm{\Sigma }$ в множество подмножеств $Q$, называемое функцией переходов;

(4) $q_0\in Q$ — выделенное начальное состояние;

(5) $F\subseteq Q$ — множество заключительных состояний.

Конечный автомат $M$ называется детерминированным, если множество $\delta (q,a)$ содержит не более одного состояния для любых $q\in Q$ и $a\in \mathrm{\Sigma }$. Если $\delta (q,a)$ всегда содержит точно одно состояние, то автомат $M$ называется полностью определенным.

Любая пара $(q,\omega )\in Q\times {\mathrm{\Sigma }}^{\ast }$ конфигурацией автомата $M$. Конфигурация $(q_0,\omega )$ называется начальной, а пара $(q,e)$, где $q\in F$, называется заключительной (или допускающей).

Tакт работы автомата $M$ представляется бинарным отношением ${⊢}_M$, определенным на конфигурациях. Если $\delta (q,a)$ содержит $p$, то $(q,a\omega ){⊢}_M(p,\omega )$ для всех $\omega \in {\mathrm{\Sigma }}^{\ast }$. Отношения ${⊢}_M^{+}$ и ${⊢}_M^{\ast }$ являются соответственно транзитивным замыканием и рефлексивным и транзитивным замыканием отношения ${⊢}_M$.

Автомат $M$ допускает цепочку $\omega \in {\mathrm{\Sigma }}^{\ast }$, если $(q_0,\omega ){⊢}_M^{\ast }(q,e)$ для некоторого $q\in F$.

Языком, определяемым (распознаваемым, допускаемым) автоматом $M$ (обозначается $L(M)$), называется множество входных цепочек, допускаемых автоматом $M$, т.е. $L(M)=\{\omega :\omega \in {\mathrm{\Sigma }}^{\ast }$ и $(q_0,\omega ){⊢}_M^{\ast }(q,e)$ для некоторого $q\in F\}$.

Часто бывает удобно использовать графическое представление конечного автомата в виде так называемой диаграммы (или графа переходов) автомата — орграфа, вершины которого помечены символами состояний и в котором есть дуга $(p,q)$, если существует такой символ $a\in \mathrm{\Sigma }$, что $q\in \delta (p,a)$. Кроме того, дуга $(p,q)$ помечается списком, состоящим из таких $a$, что $q\in \delta (p,a)$.

На рисунке приведены два конечных автомата, допускающих язык $\{a^n{b}^m:n>0,m>0\}$: $M_1$ — недетерминированный, $M_2$ — детерминированный полностью определенный.

См. также

• Преобразователь,

• Теорема о детерминизации.

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.