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

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

Как устроен автомат

Работу автомата можно рассматривать как выполнение алгоритма: входное слово обрабатывается слева направо, по одному символу. Важна только текущая информация, сохранённая в состоянии; все ранее прочитанные символы учитываются через него.

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

Для каждого шага используется переход между состояниями. Его удобно записывать в таблице переходов. В простейшем, детерминированном автомате для каждой пары «состояние и символ» задано ровно одно следующее состояние.

Формальное описание

Здесь \(Q\) — конечное множество состояний, \(\Sigma\) — входной алфавит, \(\delta\) — функция переходов, \(q_0\) — начальное состояние, а \(F\) — множество заключительных состояний. Если после чтения всего слова автомат оказался в состоянии из \(F\), слово считается принятым согласно условию принятия слова автоматом.