Конечный автомат: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
''Конечный автомат'' ([[Finite-state automation]])--- распознаватель, | |||
используемый для задания [[регулярное множество| регулярных множеств]]. | используемый для задания [[регулярное множество| регулярных множеств]]. ''Конечный автомат'' состоит из входной ленты, входной головки и | ||
управляющего устройства. Входная лента --- это линейная | управляющего устройства. Входная лента --- это линейная | ||
последовательность клеток, или ячеек, каждая из которых | последовательность клеток, или ячеек, каждая из которых | ||
может содержать любой символ из | может содержать любой символ из <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],
[Касьянов-Поттосин]