Конечный автомат — это математическая абстракция, используемая для разработки алгоритмов. Конечный автомат считывает набор входных данных и переходит в другое состояние на основе этих входных данных.
Состояние — это описание состояния системы, ожидающей выполнения перехода. Переход — это набор действий, которые необходимо выполнить при выполнении условия или получении события. На диаграмме состояний кружки представляют каждое возможное состояние, а стрелки представляют переходы между состояниями.
Глядя на конечное состояние, вы можете кое-что различить в серии входных данных, ведущих к этому состоянию.
Существует два типа основных конечных автоматов:
детерминированный конечный автомат
Этот тип допускает только один возможный переход для любого разрешенного входа. Это похоже на утверждение «если» : это 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.
Обратите внимание, что любое регулярное выражение может быть представлено конечным автоматом.