Конечный автомат (КА, finite state machine) — модель устройства, которое в каждый момент находится в одном из конечного набора состояний и переходит между ними по входным сигналам. Это способ описать управляющую логику: светофор, контроллер протокола, торговый автомат.
Автомат задают пятью элементами: множеством состояний, входным алфавитом, выходным алфавитом, функцией переходов (какое следующее состояние) и функцией выходов (какой выход). Память автомата — это его текущее состояние, хранимое в регистре триггеров.
Различают два типа. В автомате Мура выход зависит только от текущего состояния. В автомате Мили выход зависит и от состояния, и от текущих входов. Автомат Мили реагирует быстрее (выход меняется в том же такте), но автомат Мура устойчивее: его выходы синхронны и не «дёргаются» вслед за входами.
Любой автомат Мили можно преобразовать в эквивалентный Мур и наоборот; выбор — компромисс между скоростью реакции и стабильностью выходов.