В статье рассмотрены простые конечные автоматы и их реализация на C++ с помощью switch-конструкций, таблиц времени исполнения и библиотеки Boost Statechart.
Введение
Грубо говоря, конечный автомат (Finite State Machine), глазами пользователя – это черный ящик, в который можно что-то передать и что-то оттуда получить. Это очень удобная абстракция, которая позволяет скрыть сложный алгоритм, кроме того конечные автоматы очень эффективны.
Конечные автоматы изображают в виде диаграмм состоящих из состояний и переходов. Поясню на простом примере:
Как вы наверное догадались – это диаграмма состояний лампочки. Начальное состояние обозначается черным кружком, переходы стрелками, некоторые стрелки подписаны – это события после которых автомат переходит в другое состояние. Итак, сразу из начального состояния, мы попадаем в состояние Light Off – лампа не горит. Если нажать кнопку, то автомат изменит свое состояние и перейдет по стрелке помеченной Push Button, в состояние Light On – лампа горит. Перейти из этого состояния можно опять же по стрелке, после нажатия кнопки, в состояние Light Off.
Также широко используются таблицы переходов:
| Текущее состояние | Событие | Состояние после перехода | Действие |
| Light Off | Push Button | Light On | Загорается лампа |
| Light On | Push Button | Light Off | Лампа гаснет |
Практическое применение автоматов
Конечные автоматы широко используются в программировании. Например очень удобно представить работу устройства в виде автомата. Это сделает код проще и позволит легко с ним экспериментировать и поддерживать.
Также конечные автоматы применяют для написания всевозможных парсеров и анализаторов текста, с помощью них можно эффективно проводить поиск подстрок, регулярные выражения тоже транслируются в конечный автомат.
