Аноним

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

Материал из WikiGrapp
нет описания правки
Нет описания правки
Нет описания правки
Строка 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:


[Касьянов-Поттосин]
[Касьянов-Поттосин]
[[Категория: Теория автоматов]]