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

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

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

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

\(\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.