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

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


Строка 19: Строка 19:


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


(1) <math>Q</math> --- конечное множество [[Состояние автомата|''состояний'']];
(1) <math>\,Q</math> конечное множество [[Состояние автомата|''состояний'']];


(2) <math>\Sigma</math> --- конечное множество допустимых ''входных
(2) <math>\,\Sigma</math> конечное множество допустимых ''входных
символов'';
символов'';


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


(4) <math>q_0\in Q</math> --- выделенное [[Начальное состояние автомата|''начальное состояние'']];
(4) <math>q_0\in Q</math> выделенное [[Начальное состояние автомата|''начальное состояние'']];


(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>. Если
<math>\delta(q,a)</math> всегда содержит точно одно состояние, то
<math>\,\delta(q,a)</math> всегда содержит точно одно состояние, то
автомат <math>M</math> называется [[Полностью определенный конечный автомат|''полностью определенным'']].
автомат <math>\,M</math> называется [[Полностью определенный конечный автомат|''полностью определенным'']].


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


Tакт работы автомата <math>M</math> представляется бинарным отношением
Tакт работы автомата <math>\,M</math> представляется бинарным отношением
<math>\vdash_M</math>, определенным на конфигурациях. Если
<math>\vdash_M</math>, определенным на конфигурациях. Если
<math>\delta(q,a)</math> содержит <math>p</math>, то
<math>\,\delta(q,a)</math> содержит <math>\,p</math>, то
<math>(q,a\omega)\vdash_M(p,\omega)</math> для всех
<math>(q,a\omega)\vdash_M(p,\omega)</math> для всех
<math>\omega\in\Sigma^*</math>. Отношения <math>\vdash_{M}^{+}</math> и <math>\vdash_{M}^{*}</math>
<math>\omega\in\Sigma^*</math>. Отношения <math>\vdash_{M}^{+}</math> и <math>\vdash_{M}^{*}</math>
Строка 65: Строка 65:
Часто бывает удобно использовать графическое представление
Часто бывает удобно использовать графическое представление
'''конечного автомата'''  в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']]
'''конечного автомата'''  в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']]
(или [[Граф переходов автомата|''графа переходов'']]) автомата ---
(или [[Граф переходов автомата|''графа переходов'']]) автомата
[[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены
[[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены
символами состояний и в котором есть дуга <math>(p,q)</math>, если
символами состояний и в котором есть дуга <math>\,(p,q)</math>, если
существует такой символ <math>a\in\Sigma</math>, что <math>q\in\delta(p,a)</math>.
существует такой символ <math>a\in\Sigma</math>, что <math>q\in\delta(p,a)</math>.
Кроме того, дуга <math>(p,q)</math> помечается списком, состоящим из
Кроме того, дуга <math>\,(p,q)</math> помечается списком, состоящим из
таких <math>a</math>, что <math>q\in\delta(p,a)</math>.
таких <math>\,a</math>, что <math>q\in\delta(p,a)</math>.


[[Файл:Finite-state automation.gif|550px]]
[[Файл:Finite-state automation.gif|550px]]


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


== См. также ==
== См. также ==


[[Преобразователь]],  
* ''[[Преобразователь]],''


[[Теорема о детерминизации]].
* ''[[Теорема о детерминизации]].''


==Литература==
==Литература==


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


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


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


[[Категория: Теория автоматов]]
[[Категория: Теория автоматов]]

Навигация