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

Материал из свободной русской энциклопедии «Традиция»

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

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

,

где

• K — конечное множество состояний автомата,
• — единственно допустимое начальное состояние автомата,
• — множество конечных состояний, причём допустимо F = Ø, и F = K,
• Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом,
• — функция переходов.

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