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

Перейти к навигации Перейти к поиску
нет описания правки
м (Защищена страница «Конечный автомат» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
Нет описания правки
Строка 22: Строка 22:
<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> --- конечное множество допустимых ''входных
Строка 30: Строка 30:
множество подмножеств <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> представляется бинарным отношением
Строка 63: Строка 63:


Часто бывает удобно использовать графическое представление
Часто бывает удобно использовать графическое представление
'''конечного автомата'''  в виде так называемой ''диаграммы''
'''конечного автомата'''  в виде так называемой [[Диаграмма конечного автомата|''диаграммы'']]
(или ''графа переходов'') автомата ---
(или [[Граф переходов автомата|''графа переходов'']]) автомата ---
[[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены
[[орграф|''орграфа'']], [[вершина|''вершины'']] которого помечены
символами состояний и в котором есть дуга <math>(p,q)</math>, если
символами состояний и в котором есть дуга <math>(p,q)</math>, если

Навигация