4194
правки
Конечный автомат: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | (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_1</math> — недетерминированный, <math>\,M_2</math> — детерминированный полностью определенный. | ||
== См. также == | == См. также == | ||
[[Преобразователь]], | * ''[[Преобразователь]],'' | ||
[[Теорема о детерминизации]]. | * ''[[Теорема о детерминизации]].'' | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] | ||
