1023
правки
Конечный автомат: различия между версиями
Материал из WEGA
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
''Конечный автомат'' ([[Finite-state automation]])--- распознаватель, | '''Конечный автомат''' ([[Finite-state automation]])--- распознаватель, | ||
используемый для задания [[регулярное множество| регулярных множеств]]. ''Конечный автомат'' состоит из входной ленты, входной головки и | используемый для задания [[регулярное множество| регулярных множеств]]. '''Конечный автомат''' состоит из входной ленты, входной головки и | ||
управляющего устройства. Входная лента --- это линейная | управляющего устройства. Входная лента --- это линейная | ||
последовательность клеток, или ячеек, каждая из которых | последовательность клеток, или ячеек, каждая из которых | ||
| Строка 26: | Строка 26: | ||
''Недетерминированный конечный автомат'' | ''Недетерминированный конечный автомат'' | ||
(или просто ''конечный автомат'') --- это пятерка | (или просто '''конечный автомат''') --- это пятерка | ||
<math>M=(Q,\Sigma,\delta,q_0,F)</math>, в которой | <math>M=(Q,\Sigma,\delta,q_0,F)</math>, в которой | ||
| Строка 41: | Строка 41: | ||
(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>. Если | ||
| Строка 70: | Строка 70: | ||
Часто бывает удобно использовать графическое представление | Часто бывает удобно использовать графическое представление | ||
''конечного автомата'' в виде так называемой ''диаграммы'' | '''конечного автомата''' в виде так называемой ''диаграммы'' | ||
(или ''графа переходов'') автомата --- | (или ''графа переходов'') автомата --- | ||
[[орграф|орграфа]], [[вершина|вершины]] которого помечены | [[орграф|орграфа]], [[вершина|вершины]] которого помечены | ||
| Строка 92: | Строка 92: | ||
[Касьянов-Поттосин] | [Касьянов-Поттосин] | ||
[[Категория: Теория автоматов]] | |||
