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