Конечный автомат

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

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

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

где

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

Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов. Процесс продолжается до тех пор, пока не будет достигнуто одно из состояний F.

Виды

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

Зеркальный автомат — это автомат, в графе состояний которого направление стрелок, помеченных буквами входного алфавита, изменено на обратное, а входящие состояния заменены на допускающие, а допускающие на входящие состояния.