Конечные автоматы (finite-state machine)

Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

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

У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.

Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.


Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Читать дальше →

https://habr.com/post/358304/?utm_source=habrahabr&utm_medium=rss&utm_campaign=358304