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

Что такое конечный автомат

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

Автомат задают набором: множеством состояний, входным алфавитом, начальным состоянием, множеством конечных (допускающих) состояний и функцией переходов, которая по текущему состоянию и входному символу определяет следующее состояние.

Как работает автомат

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

Состояние	Вход 0	Вход 1
S0 (начальное)	S0	S1
S1	S2	S1
S2 (допускающее)	S2	S1

Разбор примера

Пусть автомат из таблицы выше принимает цепочки, в которых встречается подцепочка 10. Проследим обработку входа 0110:

старт: S0 символ 0 -> S0 символ 1 -> S1 символ 1 -> S1 символ 0 -> S2 (допускающее) Итог: цепочка принята

Автомат запомнил, что встретил единицу (перешёл в S1), а затем ноль после неё (перешёл в S2). Заметим: автомат не хранит всю строку, ему достаточно текущего состояния — в этом сила и ограничение модели.

Где применяют

• лексический анализ в трансляторах и поиск по шаблону;
• проверка корректности форматов: дат, чисел, адресов;
• управление техническими устройствами: светофор, банкомат, турникет.

Детерминированные и недетерминированные автоматы

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

Чего автомат не умеет

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

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

Кратко о главном

• Конечный автомат имеет конечное число состояний и переходы по символам.
• Его задают состояниями, алфавитом, началом, концами и функцией переходов.
• Цепочка принимается, если после её чтения автомат в допускающем состоянии.
• Автомат хранит только текущее состояние, а не всю входную строку.
• Применяют в анализе текста, проверке форматов и управлении устройствами.