Конечный автомат (в теории алгоритмов) — математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.

Формально конечный автомат определяется как пятёрка

$\backslash boldsymbol\{M\; =\; (K\; ,\; \backslash Sigma\; ,\; \backslash pi\; ,\; s\; ,\; F)\}$

Где K — конечное множество состояний автомата, $s\; \backslash in\; K$ — единственно допустимое начальное состояние автомата, $F\; \backslash subset\; K$ — множество конечных состояний, причём допустимо F=Ø, и F=K, Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, $\backslash pi\; :\; K\; \backslash times\; \backslash Sigma\; \backslash rightarrow\; K$ — функция переходов. Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов. Процесс продолжается до тех пор, пока не будет достигнуто одно из состояний F.

Конечные автоматы широко используются на практике, например в синтаксических анализаторах, а также в других случаях когда количество состояний объекта и переходов между ними сравнительно невелико.

Английский вариант статьи, более полный: http://en.wikipedia.org/wiki/Finite_state_machine

Теория алгоритмов | Теория автоматов

Краен автомат | Konečný automat | Endlicher Automat | Finite state machine | Autómata finito | Äärellinen automaatti | Automate fini | אוטומט סופי | Automa a stati finiti | 有限オートマトン | Eindige toestandsautomaat | Máquina de estado finito | Automat finit | Ändlig automat | 有限状态自动机