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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
 
Нет описания правки
Строка 1: Строка 1:
'''Конечный автомат''' ([[Finite-state automation]])--- распознаватель,
''Конечный автомат'' ([[Finite-state automation]])--- распознаватель,
используемый для задания [[регулярное множество| регулярных множеств]]. '''Конечный автомат''' состоит из входной ленты, входной головки и
используемый для задания [[регулярное множество| регулярных множеств]]. ''Конечный автомат'' состоит из входной ленты, входной головки и
управляющего устройства. Входная лента --- это линейная
управляющего устройства. Входная лента --- это линейная
последовательность клеток, или ячеек, каждая из которых
последовательность клеток, или ячеек, каждая из которых
может содержать любой символ из $\Sigma$. В каждый данный
может содержать любой символ из <math>\Sigma</math>. В каждый данный
момент входная головка читает, или, как иногда говорят,
момент входная головка читает, или, как иногда говорят,
обозревает одну входную ячейку, а управляющее устройство
обозревает одну входную ячейку, а управляющее устройство
Строка 23: Строка 23:
на одну ячейку вправо. Для каждой текущей конфигурации в общем случае
на одну ячейку вправо. Для каждой текущей конфигурации в общем случае
существует конечное множество возможных следующих шагов, любой из
существует конечное множество возможных следующих шагов, любой из
которых '''конечный автомат''' может сделать, исходя из этой конфигурации.
которых ''конечный автомат'' может сделать, исходя из этой конфигурации.
 
''Недетерминированный конечный автомат''
(или просто ''конечный автомат'') --- это пятерка
<math>M=(Q,\Sigma,\delta,q_0,F)</math>, в которой
 
(1) <math>Q</math> --- конечное множество ''состояний'';
 
(2) <math>\Sigma</math> --- конечное множество допустимых ''входных
символов'';
 
(3) <math>\delta</math> --- отображение множества <math>Q\times\Sigma</math> в
множество подмножеств <math>Q</math>, называемое ''функцией переходов'';
 
(4) <math>q_0\in Q</math> --- выделенное ''начальное состояние'';
 
(5) <math>F\subseteq Q</math> --- множество ''заключительных состояний''.
 
''Конечный автомат'' <math>M</math> называется ''детерминированным'',
если множество <math>\delta(q,a)</math> содержит не более одного
состояния для любых <math>q\in Q</math> и <math>a\in\Sigma</math>. Если
<math>\delta(q,a)</math> всегда содержит точно одно состояние, то
автомат <math>M</math> называется ''полностью определенным''.
 
Любая пара <math>(q,\omega)\in Q\times\Sigma^*</math>
называется ''конфигурацией'' автомата <math>M</math>. Конфигурация
<math>(q_0,\omega)</math> называется ''начальной'', а пара <math>(q,e)</math>,
где <math>q\in F</math>, называется ''заключительной'' (или ''допускающей'').
 
Tакт работы автомата <math>M</math> представляется бинарным отношением
<math>\vdash_M</math>, определенным на конфигурациях. Если
<math>\delta(q,a)</math> содержит <math>p</math>, то
<math>(q,a\omega)\vdash_M(p,\omega)</math> для всех
<math>\omega\in\Sigma^*</math>. Отношения <math>\vdash_{M}^{+}</math> и <math>\vdash_{M}^{*}</math>
являются соответственно транзитивным замыканием и
рефлексивным и транзитивным замыканием отношения <math>\vdash_M</math>.
 
Автомат <math>M</math> ''допускает'' цепочку <math>\omega\in\Sigma^*</math>, если
<math>(q_0,\omega)\vdash_{M}^{*}(q,e)</math> для некоторого <math>q\in F</math>. ''
Языком'', ''определяемым'' (''распознаваемым'', ''допускаемым'')
автоматом <math>M</math> (обозначается <math>L(M)</math>), называется множество
входных цепочек, допускаемых автоматом <math>M</math>, т.е.
<math>L(M)=\{\omega:\omega\in\Sigma^*</math> и
<math>(q_0,\omega)\vdash_{M}^{*}(q,e)</math> для некоторого <math>q\in F\}</math>.
 
 
Часто бывает удобно использовать графическое представление
''конечного автомата''  в виде так называемой ''диаграммы''
(или ''графа переходов'') автомата ---
[[орграф|орграфа]], [[вершина|вершины]] которого помечены
символами состояний и в котором есть дуга <math>(p,q)</math>, если
существует такой символ <math>a\in\Sigma</math>, что <math>q\in\delta(p,a)</math>.
Кроме того, дуга <math>(p,q)</math> помечается списком, состоящим из
таких <math>a</math>, что <math>q\in\delta(p,a)</math>.
 
 
== См. также ==
 
[[Преобразователь]],
 
[[Теорема о детерминизации]].
 
==Литература==
 
[Ахо-Ульман],
 
[Касьянов/95],
 
[Касьянов-Поттосин]

Версия от 20:14, 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],

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