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

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

Глядя на конечное состояние, вы можете кое-что различить в серии входных данных, ведущих к этому состоянию.

Существует два типа основных конечных автоматов:

детерминированный конечный автомат Этот тип допускает только один возможный переход для любого разрешенного входа. Это похоже на утверждение «если» : это if x then doThis else doThat невозможно. Компьютер должен выполнить один из двух вариантов.

недетерминированный конечный автомат Учитывая некоторое состояние, ввод может привести к более чем одному другому состоянию.

Рисунок 1: Детерминированный конечный автомат. Машина переходит из состояния 1 в состояние 2 для входа X и из состояния 1 в состояние 3 для входа Y. На рисунке 1 состояние начинается в Состоянии 1; состояние меняется на состояние 2 при вводе «X» или на состояние 3 при вводе «Y».

Рисунок 2: Недетерминированный конечный автомат. Машина может оставаться в состоянии 1, переходя в себя, или может переходить из состояния 1 в состояние 2 для входа X. На рисунке 2 при наличии входного сигнала «X» состояние может сохраниться или измениться на состояние 2.

Обратите внимание, что любое регулярное выражение может быть представлено конечным автоматом.