Конечный автомат: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
''Конечный автомат'' ([[Finite-state automation]])--- распознаватель,
'''Конечный автомат''' ([[Finite-state automation]])--- распознаватель,
используемый для задания [[регулярное множество| регулярных множеств]]. ''Конечный автомат'' состоит из входной ленты, входной головки и
используемый для задания [[регулярное множество| регулярных множеств]]. '''Конечный автомат''' состоит из входной ленты, входной головки и
управляющего устройства. Входная лента --- это линейная
управляющего устройства. Входная лента --- это линейная
последовательность клеток, или ячеек, каждая из которых
последовательность клеток, или ячеек, каждая из которых
Строка 26: Строка 26:


''Недетерминированный конечный автомат''
''Недетерминированный конечный автомат''
(или просто ''конечный автомат'') --- это пятерка
(или просто '''конечный автомат''') --- это пятерка
<math>M=(Q,\Sigma,\delta,q_0,F)</math>, в которой
<math>M=(Q,\Sigma,\delta,q_0,F)</math>, в которой


Строка 41: Строка 41:
(5) <math>F\subseteq Q</math> --- множество ''заключительных состояний''.
(5) <math>F\subseteq Q</math> --- множество ''заключительных состояний''.


''Конечный автомат'' <math>M</math> называется ''детерминированным'',
'''Конечный автомат''' <math>M</math> называется ''детерминированным'',
если множество <math>\delta(q,a)</math> содержит не более одного
если множество <math>\delta(q,a)</math> содержит не более одного
состояния для любых <math>q\in Q</math> и <math>a\in\Sigma</math>. Если
состояния для любых <math>q\in Q</math> и <math>a\in\Sigma</math>. Если
Строка 70: Строка 70:


Часто бывает удобно использовать графическое представление
Часто бывает удобно использовать графическое представление
''конечного автомата''  в виде так называемой ''диаграммы''
'''конечного автомата'''  в виде так называемой ''диаграммы''
(или ''графа переходов'') автомата ---
(или ''графа переходов'') автомата ---
[[орграф|орграфа]], [[вершина|вершины]] которого помечены
[[орграф|орграфа]], [[вершина|вершины]] которого помечены
Строка 92: Строка 92:


[Касьянов-Поттосин]
[Касьянов-Поттосин]
[[Категория: Теория автоматов]]

Версия от 20:25, 13 апреля 2009

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

\noindent\begin{minipage}{57mm} \unitlength=1mm \begin{picture}(52,81) \put(0,81){\special{em: graph 49.pcx}} \end{picture}\end{minipage}\begin{minipage}{60mm}\parindent=5mm


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

Недетерминированный конечный автомат (или просто конечный автомат) --- это пятерка [math]\displaystyle{ M=(Q,\Sigma,\delta,q_0,F) }[/math], в которой

(1) [math]\displaystyle{ Q }[/math] --- конечное множество состояний;

(2) [math]\displaystyle{ \Sigma }[/math] --- конечное множество допустимых входных символов;

(3) [math]\displaystyle{ \delta }[/math] --- отображение множества [math]\displaystyle{ Q\times\Sigma }[/math] в множество подмножеств [math]\displaystyle{ Q }[/math], называемое функцией переходов;

(4) [math]\displaystyle{ q_0\in Q }[/math] --- выделенное начальное состояние;

(5) [math]\displaystyle{ F\subseteq Q }[/math] --- множество заключительных состояний.

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

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

Tакт работы автомата [math]\displaystyle{ M }[/math] представляется бинарным отношением [math]\displaystyle{ \vdash_M }[/math], определенным на конфигурациях. Если [math]\displaystyle{ \delta(q,a) }[/math] содержит [math]\displaystyle{ p }[/math], то [math]\displaystyle{ (q,a\omega)\vdash_M(p,\omega) }[/math] для всех [math]\displaystyle{ \omega\in\Sigma^* }[/math]. Отношения [math]\displaystyle{ \vdash_{M}^{+} }[/math] и [math]\displaystyle{ \vdash_{M}^{*} }[/math] являются соответственно транзитивным замыканием и рефлексивным и транзитивным замыканием отношения [math]\displaystyle{ \vdash_M }[/math].

Автомат [math]\displaystyle{ M }[/math] допускает цепочку [math]\displaystyle{ \omega\in\Sigma^* }[/math], если [math]\displaystyle{ (q_0,\omega)\vdash_{M}^{*}(q,e) }[/math] для некоторого [math]\displaystyle{ q\in F }[/math]. Языком, определяемым (распознаваемым, допускаемым) автоматом [math]\displaystyle{ M }[/math] (обозначается [math]\displaystyle{ L(M) }[/math]), называется множество входных цепочек, допускаемых автоматом [math]\displaystyle{ M }[/math], т.е. [math]\displaystyle{ L(M)=\{\omega:\omega\in\Sigma^* }[/math] и [math]\displaystyle{ (q_0,\omega)\vdash_{M}^{*}(q,e) }[/math] для некоторого [math]\displaystyle{ q\in F\} }[/math].


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


См. также

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

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

Литература

[Ахо-Ульман],

[Касьянов/95],

[Касьянов-Поттосин]