Главная › Услуги › Конечный автомат: теория и реализация. Конечные автоматы, как программировать без запарок Конечный автомат с состояниями s a b

Конечный автомат: теория и реализация. Конечные автоматы, как программировать без запарок Конечный автомат с состояниями s a b

Конечный автомат: теория и реализация

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

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

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

Конечный автомат (или попросту FSM - Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра - переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

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

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

Обратите внимание на то, что при направлении домой или из дома муравей не будет бояться курсора мыши. Почему? А потому что нет соответствующего перехода.

Реализация простого конечного автомата

Конечный автомат можно реализовать при помощи одного класса. Назовем его FSM. Идея состоит в том, чтобы реализовать каждое состояние как метод или функцию. Также будем использовать свойство activeState для определения активного состояния.

Public class FSM { private var activeState:Function; // указатель на активное состояние автомата public function FSM() { } public function setState(state:Function) :void { activeState = state; } public function update() :void { if (activeState != null) { activeState(); } } }

Всякое состояние есть функция. Причем такая, что она будет вызываться при каждом обновлении кадра игры. Как уже говорилось, в activeState будет храниться указатель на функцию активного состояния.

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM - это делает наш класс более универсальным.

Использование конечного автомата

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

Наш муравей представлен классом Ant , в котором есть поле brain . Это как раз экземпляр класса FSM .

Public class Ant { public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) { position = new Vector3D(posX, posY); velocity = new Vector3D(-1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { } public function update():void { // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); } (...) }

Класс Ant также содержит свойства velocity и position . Эти переменные будут использоваться для расчета движения с помощью метода Эйлера . Функция update() вызывается при каждом обновлении кадра игры.

Ниже приводится реализация каждого из методов, начиная с findLeaf() - состояния, ответственного за поиск листьев.

Public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Состояние goHome() - используется для того, чтобы муравей отправился домой.

Public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

И, наконец, состояние runAway() - используется при уворачивании от курсора мыши.

Public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочек. brain.setState(findLeaf); } }

Улучшение FSM: автомат, основанный на стеке

Представьте себе, что муравью на пути домой также нужно убегать от курсора мыши. Вот так будут выглядеть состояния FSM:

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

Решением такой проблемы является конечный автомат, основанный на стеке. В отличие от простого FSM, который мы реализовали выше, данный вид FSM использует стек для управления состояниями. В верхней части стека находится активное состояние, а переходы возникают при добавлении/удалении состояний из стека.

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

Public class StackFSM { private var stack:Array; public function StackFSM() { this.stack = new Array(); } public function update() :void { var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) { currentStateFunction(); } } public function popState() :Function { return stack.pop(); } public function pushState(state:Function) :void { if (getCurrentState() != state) { stack.push(state); } } public function getCurrentState() :Function { return stack.length > 0 ? stack : null; } }

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

Важно отметить, что при использовании конечного автомата на основе стека каждое состояние несет ответственность за свое удаление из стека при отсутствии необходимости в нем. Например, состояние attack() само должно удалять себя из стека в том случае, если враг был уже уничтожен.

Public class Ant { (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) { (...) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (...) } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); } } (...) }

Вывод

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

Реализация конечного автомата с функциями-состояниями является простым, но в то же время мощным методом. Даже более сложные переплетения состояний могут быть реализованы при помощи FSM.

Элементы теории автоматов

План:

1. Понятие автомата, принцип работы автомата

2. Способы задания конечных автоматов

3. Общие задачи теории автоматов

Теоретические сведения

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

Понятие автомата, принцип работы автомата

Понятие автомат рассматривается в двух аспектах:

1. Автомат – устройство , выполняющее некоторые функции без непосредственно участия человека. Автомат это реальное устройство, понятное, почему и как оно работает, хотя бы для тех людей, которые его сконструировали и изготовили. Автомобиль, трактор, самолет, светофор, телевизор, телефон – все это автоматы. В этом аспекте ЭВМ следует понимать как автомат, который работает по программе, составленной человеком.

2. Автомат – математическое понятие , обозначающее математическую модель реальных технических устройств. Автомат это абстрактное устройство, непонятно почему и как оно работает и, вообще, почему оно может работать. В этом аспекте автомат есть «черный ящик», который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно неважно что, как и почему производит те или иные действия.

Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний.

Алгебраическая теория автоматов является разделом теоретической кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.

Общая теория автоматов содержит различные подразделы. В зависимости от предмета изучения она делится на абстрактную теорию автоматов и структурную теорию автоматов.

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

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

Определение конечных автоматов

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

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

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

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

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

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

1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал «железного» слугу - автомат, который выполнял в доме обязанности привратника.

2. Астроном Иоганн Мюллер (Региамонтан) (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана II.

3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. Он создал образ механической утки, точной копии своего живого двойника - плавала, чистила перья, глотала с ладони зерна. Его механический флейтист, исполнявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.

4. Русский изобретатель 19 в. А. М. Гамулецкий создал целый механический кабинет, в котором было множество сконструированных им автоматов. Здесь в том числе была и говорящая голова чародея и амур, играющий на арфе, которые поражали воображение современников.

5. Первый примитивный арифмометр сконструировал в 1641 г. Блез Паскаль. Толчком для открытия были мучения его отца – налогового, инспектора, который днями и ночами работал с большими вычислениями. Изобретя арифмометр, восемнадцати летний сын избавил отца от сложных вычислений, а миру подарил первый калькулятор, производящий сложение и вычитание чисел.

6. Первый шахматный автомат был построен в 1890 г. испанским инженером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).

7. Первую вычислительную машину с автоматическим управлением создал Чарльз Баббедж в 1822 г. Он спроектировал арифмометр , который имел запоминающие и арифметические устройства. Эти устройства стали прототипами аналогичных устройств современным ЭВМ.

Виды автоматов.

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

Любой автомат имеет собственные базовые множества, которые включают в себя:алфавит входа, алфавит выхода, множество состояний автомата.

Характерной особенностью конечного автомата является наличие памяти, которая определяет состояние автомата в зависимости от времени. Внешним проявлением различных состояний автомата является его реакция на однотипные воздействия (сигналы).

В работе конечных цифровых автоматов важным понятием является время.

Автоматы можно классифицировать по различным признакам.

1. По виду деятельности - автоматы делятся на: информационные, управляющие и вычислительные.

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

К управляющим автоматам принято относить устройства для управления некоторым процессом, в том числе конкретно: лифтом, конвейером, станком, шлагбаумом.

К вычислительным автоматам относятся микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.

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

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

3. Цифровые автоматы - автоматы, которые преобразует цифровую информацию. В таком автомате входные сигналы задаются в виде конечного множества мгновенных символов: их длительность настолько мала, что ею можно пренебречь. За фиксированное время происходит преобразование входных символов, а на выходе происходит скачкообразный переход из одного состояния в другое состояние.

4. Абстрактные автоматы - отображающие множество слов входного алфавита Х во множество слов выходного алфавита Y.

Абстрактный автомат есть:

~ Математическая модель,

~ Алгоритм действия некоторого преобразования кодовых последовательностей,

~ Закон преобразования входного алфавита в выходной.

5. Синхронные и асинхронные автоматы . В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, автоматы делятся насинхронные и асинхронные автоматы.

В синхронных автоматах продолжительность входных сигналов и время переходов согласовано между собой. Они используются в вычислительных комплексах, АСУ и т.д.

В асинхронных автоматах продолжительность входных сигналов и время переходов не согласовано между собой. Они зависят от внешних источников - различных событий, а интервал дискретности является переменным (например, в кодовых замках). В асинхронных автоматах очередное изменение значений входных сигналов может произойти только при условии, что закончился переходный процесс, вызванный предыдущим изменением этих сигналов.

6. Автоматы делятся на конечные и бесконечные автоматы. Если в основании классификации лежит объем памяти, то различие заключается в том, имеет ли автомат конечное или бесконечное число внутренних состояний.

Под бесконечным автоматом обычно понимают определенную математическую идеализацию представлений об автомате, имеющую бесконечное число состояний. Память такого автомата потенциально может неограниченно возрастать. Например, известные абстрактные автоматы Поста и Тьюринга являются бесконечными автоматами, но сама ЭВМ или ее отдельные части - конечными автоматами.

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

В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием самого автомата в предшествующий момент времени.

В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.

Вероятностный автомат - это дискретный преобразователь информации, функционирование которого в каждый момент времени зависит только от состояний памяти и описывается статистическими законами.

8. Универсальный автомат. В теории автоматов доказано, что для выполнения различных преобразований информации достаточно построить универсальный автомат с помощью программы и соответствующего кодирования, способный решать любые задачи.

Математическая модель цифрового автомата с одним входом задается пятью объектами:

X- конечное множество входных символов, входной алфавит:

Х= {x 1 (t), x 2 (t), …, x n (t)};

Y- конечное множество выходных символов, выходной алфавит:

У={y 1 (t), y 2 (t), …, y n (t)};

Q ~ конечное множество состояний автомата:

Q= {q 0 (t), q 1 (t), q 2 (t), …, q n (t)}, q 0 - начальное состояние;

δ(q, х ) - функция перехода автомата из одного состояния в другое: (Q х X) ®Q;

λ(q, х ) ~ функция выхода автомата: (Q x Х) ® Y.

Таким образом, конечный автомат С= (X, Q, У, δ, λ.) определяется рекуррентными соотношениями

q(0) = q 0 , q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),

t- дискретизированный момент времен или это есть образ монотонной функции t :. Т ® N, причем Т - обычное непрерывное время, N - множество натуральных чисел.

Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г 0) – показывает число изменений, произошедших до момента времени Г 0 .

Примером дискретизации служит обычный кинематограф: время разбито на интервалы длительностью 1/24с. Человеческий глаз воспринимает следование дискретных кадров как непрерывное движение.

9. Синхронные автоматы делятся на автоматы Мили и автоматы Мура . В зависимости от способа организации функции выхода синхронные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).

В автоматах Мили - выходной сигнал y (t) x (t) и состоянием q (t- 1) автомата в предшествующий момент времени (t- 1). Математической моделью таких автоматов служит система уравнений:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t-1), х(t)),

В автоматах Мура выходной сигнал y (t) однозначно определяется входным сигналом x (t) и состоянием q (t) в данный момент времени t. Математической моделью таких автоматов является система:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t)),

В таких автоматах функция выхода зависит только от состояний автомата в данный момент времени и не зависит от входного сигнала. Таким образом, входная строка такого автомата однократно считывается слева направо, осуществляя поочередный просмотр символов. В определенный момент времени конечный автомат находится в некотором внутреннем состоянии, которое изменяется после считывания очередного символа. Новое состояние можно охарактеризовать считанным символом и текущим состоянием.

10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущими входными символами, т.е. в этом автомате все состояния эквивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неизменна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.

11 Логические автоматы – есть автоматы у которых входной алфавит состоит из 2 т двоичных наборов длины т, а выходной - из 2 n двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.

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

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

Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов ) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф , вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов - табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу - один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированный конечный автомат

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: , где:

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет - так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Специализированные языки программирования

Язык последовательных функциональных схем SFC (Sequential Function Chart) - графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

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

Примечания

См. также

Секвенциальная логика (Последовательностная логика)

Ссылки

Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - М.: ВИНИТИ, 1976. - Т. 13. - С. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Применение конечных автоматов для решения задач автоматизации
Пример реализации конечного автомата на языке Python для фреймворка Django

Wikimedia Foundation . 2010 .

Кейнс, Джон Мейнард
Диаграмма состояний (теория автоматов)

Смотреть что такое "Конечный автомат" в других словарях:

конечный автомат - КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. конечный автомат Спецификация последовательности… …

Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: Finite state machine См … Финансовый словарь

конечный автомат - baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas

КОНЕЧНЫЙ АВТОМАТ - автомат, у к рого множество состояний, а также множество входных и выходных сигналов являются конечными. К. а. может быть моделью технич. устройства (ЭВМ, релейное устройство) либо биол. системы (идеализир. нервная система животного). Важными… … Большой энциклопедический политехнический словарь

конечный автомат в модульном исполнении - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite modular automaton … Справочник технического переводчика

конечный автомат доступности - (МСЭ Т Y.1711). Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика

Конечный автомат с памятью - Конечный автомат с памятью математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния. Для описания конечного автомата с памятью используются языки операторных схем, регулярных… … Википедия

детерминированный конечный автомат - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика

Автомат Мура - (автомат второго рода) в теории вычислений конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван … Википедия

В данной статье под термином «конечный автомат» подразумевается алгоритм, который может находиться в одном из небольшого количества состояний. «Состояние» - это некое условие, определяющее заданную взаимосвязь входных и выходных сигналов, а также входных сигналов и последующих состояний. Смышленый читатель сразу отметит, что конечные автоматы, описанные в данной статье, это автоматы Мили. Автомат Мили – это конечный автомат, где выходные сигналы являются функциями текущего состояния и входного сигнала, в отличие от автомата Мура, в котором выходные сигналы – это функции только состояния. В обоих случаях последующее состояние – это функция текущего состояния и входного сигнала.

Рассмотрим пример простого конечного автомата. Представьте, что в текстовой строке вам нужно распознать последовательность символов «//». На рисунке 1 показано, как это выполняется при помощи конечного автомата. Первое появление слеша не дает выходного сигнала, но приводит к тому, что автомат переходит во второе состояние. Если во втором состоянии автомат не находит слеша, он возвращается к первому, поскольку необходимо наличие 2-х слешей подряд. Если второй слеш найден, автомат выдает сигнал «готово».

Выясните, что необходимо заказчику.

Составьте диаграмму перехода состояний

Закодируйте «скелет» конечного автомата без детализации операций перехода.

Убедитесь, что переходы функционируют правильно.

Конкретизируйте детали переходов.

Проведите тест.

Пример конечного автомата

Рассмотрим более интересный пример конечного автомата - программу, контролирующую втягивание и выдвижение шасси самолета. Хотя у большинства самолетов эта процедура выполняется при помощи электрогидравлического управляющего механизма (просто потому, что на борту отсутствует компьютер), в некоторых случаях, например в беспилотных летательных аппаратах, стоит использовать программное управление.

Для начала разберемся с оборудованием. Шасси самолета состоит из передней опоры, основного левого шасси и основного правого шасси. Они приводятся в действие гидравлическим механизмом. Гидравлический насос с электроприводом подает давление на силовой исполнительный механизм. При помощи программного обеспечения насос включается или выключается. Компьютер регулирует положение клапана направления - «вниз» или «вверх», чтобы позволить давлению поднять или опустить шасси. Каждая из опор шасси имеет концевой выключатель: один из них закрывается, если шасси поднято, другой - если оно зафиксировано в положении «вниз». Чтобы определить, находится ли самолет на земле, концевой выключатель на стойке передней опоры замыкается, если вес самолета приходится на переднюю опору. Средства управления пилота состоят из верхнего/нижнего рычага шасси и трех лампочек (по одной на каждую опору), которые могут выключаться, загораться зеленым (положение «вниз») или красным светом (положение «переход»).

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

Безусловно, это важно, но заказчик считает, что на этом все заканчивается. А как насчет остальных случаев? Достаточно ли задвигать шасси в тот момент, когда самолет отрывается от земли? Что, если самолет подскочит на кочке на взлетно-посадочной полосе? Что, если пилот переведет рычаг переключения скоростей в положение «вверх» во время парковки и, как следствие, начнет взлетать? Должно ли шасси в этом случае подняться?

Одним из преимуществ мышления в терминах конечного автомата является то, что вы можете быстро нарисовать диаграмму перехода состояний на проекционной доске, прямо перед заказчиком, и пройти весь процесс вместе с ним. Принято такое обозначение перехода состояний: «событие, которое явилось причиной перехода»/«выходной сигнал как результат перехода». Если бы мы разрабатывали только то, о чем изначально просил заказчик («не задвигать шасси, если самолет находится на земле»), то мы бы получили автомат, изображенный на рисунке 2.

При составлении диаграммы перехода состояний (или любого другого алгоритма) помните о следующем:

Компьютеры работают очень быстро по сравнению с механической аппаратурой

Инженер-механик, который объясняет, что требуется сделать, возможно, не знает о компьютерах и алгоритмах всего того, что знаете вы. И это тоже положительный момент, в противном случае, вы бы не потребовались!

Как поведет себя ваша программа, если сломается механическая или электрическая деталь?

Конечный автомат, основанный на том, что действительно требуется заказчику, показан на рисунке 3. Здесь мы хотим воспрепятствовать втягиванию шасси самолета до тех пор, пока он точно не будет в воздухе. Для этого после открытия переключателя приземления автомат в течение нескольких секунд находится в ожидании. Мы также хотим реагировать на нарастающий фронт рычага пилота, а не на уровень, что позволит избежать проблем, если кто-то подвинет рычаг, пока самолет находится на парковке. Втягивание или выдвижение шасси занимает несколько секунд, и мы должны быть готовы к ситуации, что пилот в процессе этой операции передумает и переместит рычаг в противоположном направлении. Также обратите внимание, что если самолет снова приземлится, пока мы находимся в состоянии «Waiting for takeoff», таймер перезапустится и втягивание шасси произойдет, только если самолет будет находиться в воздухе в течение 2-х секунд.

Реализация конечного автомата

Листинг 1 – это моя реализация конечного автомата изображенного на рисунке 3. Давайте обсудим некоторые детали кода.

/*листинг 1*/

typedef enum {GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR} State_Type;

/*Этот массив содержит указатели на функции, вызываемые в определенных состояниях*/

void (*state_table)() = {GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear};

State_Type curr_state;

InitializeLdgGearSM();

/*Сердце автомата – этот бесконечный цикл. Функция, соответствующая

Текущему состоянию, вызывается один раз в итерацию */

while (1) {

state_table();

DecrementTimer();

void InitializeLdgGearSM(void )

curr_state = GEAR_DOWN;

/*Остановка аппаратуры, выключение лампочек и т.д.*/

void GearDown(void )

/* Переходим в состояние ожидания, если самолет

Не на земле и поступила команда поднять шасси*/

if ((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) {

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

void RaisingGear(void )

if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {

curr_state = GEAR_UP;

/*Если пилот изменил свое решение, перейти в состояние «опускание шасси»*/

if (gear_lever == DOWN) {

curr_state = LOWERING_GEAR;

void GearUp(void )

/*если пилот передвинул рычаг в положение «вниз»,

Переходим в состояние «опускание шасси»*/

if (gear_lever == DOWN) {

curr_state = LOWERING_GEAR;

void WtgForTakeoff(void )

/* Ожидание перед поднятием шасси.*/

if (timer <= 0.0) {

curr_state = RAISING_GEAR;

/*Если мы снова коснулись или пилот поменял решение – начать все заново*/

if ((squat_switch == DOWN) || (gear_lever == DOWN)) {

curr_state = GEAR_DOWN;

/* Don"t want to require that he toggle the lever again

This was just a bounce.*/

prev_gear_lever = DOWN;

void LoweringGear(void )

if (gear_lever == UP) {

curr_state = RAISING_GEAR;

if ((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) {

curr_state = GEAR_DOWN;

Во-первых, вы можете заметить, что функциональность каждого состояния реализуется отдельной Си функцией. Конечно, можно было бы реализовать автомат, используя оператор switch с отдельным case `ом для каждого состояния, однако это может привести к очень длинной функции (10-20 строк кода на 1 состояние для каждого из 20-30 состояний). Также это может привести к ошибкам, если будете изменять код на конечных стадиях тестирования. Возможно, вы никогда не забывали оператор break в конце case`a, но со мной такие случаи бывали. Код одного состояния никогда не попадет в код другого, если для каждого состояния у вас будет отдельная функция.

Чтобы избежать применения оператора switch, я использую массив указателей на функции состояний, а переменную, используемую в качестве индекса массива, объявляю типа enum.

Для простоты оборудование ввода-вывода, ответственное за считывание состояния переключателей, включение и выключение насосов и т.д., представлено в виде простых переменных. Предполагается, что данные переменные представляют собой «магические адреса», связанные с оборудованием невидимыми средствами.

Другая очевидная вещь - в этот момент код не играет особой роли. Он просто переходит от одного состояния к другому. Это важный промежуточный этап и его не следует игнорировать. Кстати, было бы неплохо добавить операторы печати, заключенные между директивами условной компиляции (#ifdef DEBUG .. #endif), которые бы выводили текущее состояние и значения входных сигналов.

Залог успеха кроется в коде, который вызывает переход состояний, т.е. определяет, что произошел ввод данных.

Если код правильно проходит через все состояния, следующим этапом становится написание «начинки» кода, то есть именно того, что производит выходной сигнал. Помните, что каждый переход имеет входной сигнал (событие, которое вызвало его) и выходной сигнал (аппаратное устройство ввода-вывода, как в нашем примере). Зачастую это полезно зафиксировать в виде таблицы перехода состояний.

В таблице перехода состояний одна строка приходится на один переход состояния.

При кодировании конечного автомата старайтесь сохранить его силу – ярко выраженное соответствие между требованиями заказчика и кодом. Вероятно, придется скрыть подробности касательно оборудования в другом уровне функций, например, для того, чтобы код конечного автомата максимально походил на таблицу перехода состояний и диаграмму перехода состояний. Подобная симметрия помогает предотвратить ошибки и объясняет то, почему конечные автоматы являются такой важной частью арсенала программиста встраиваемых систем. Конечно, вы могли бы добиться того же эффекта путем установки флажков и бесконечного множества вложенных операторов if, однако при этом будет очень сложно отслеживать код и сравнивать его с пожеланиями заказчика.

Фрагмент кода в листинге 2 расширяет функцию RaisingGear(). Обратите внимание, что код для функции RaisingGear() стремится к зеркальному отображению 2-х рядов таблицы переходов для состояния Raising Gear.

void RaisingGear(void )

/*После того, как все переключатели подняты, переходим в состояние «шасси поднято»*/

if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {

pump_motor = OFF;

gear_lights = EXTINGUISH;

curr_state = GEAR_UP;

/*Если пилот передумал, начать втягивание шасси*/

if (gear_lever == DOWN) {

pump_direction = DOWN;

curr_state = GEAR_LOWERING;

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

В качестве тренировки вы можете расширить конечный автомат, который мы только что рассмотрели, добавив таймаут к циклу втягивания или выдвижения шасси, т.к. инженер-механик не хочет, чтобы гидравлический насос работал дольше 60 секунд. Если цикл заканчивается, пилот должен быть предупрежден переключением зеленой и красной лампочки, и он должен иметь возможность снова переместить рычаг, чтобы повторить попытку. Также вы можете спросить гипотетического инженера-механика, как сказывается на насосе изменение направления на противоположное во время его работы, потому что это происходит в 2-ух случаях, когда пилот передумывает. Конечно, механик скажет, что негативно. Тогда как бы вы изменили конечный автомат, чтобы быстро остановить насос при изменении направления?

Тестирование конечного автомата

Прелесть кодирования алгоритмов в виде конечных автоматов состоит в том, что план проведения теста почти автоматически пишется сам. Все, что вам нужно сделать – это пройти через каждый переход состояния. Я обычно делаю это с маркером в руках, вычеркивая стрелки на диаграмме перехода состояний по мере того, как они успешно проходят тест. Это хороший способ избежать «скрытых состояний» - в тестах они упускаются чаще, чем конкретные состояния.

Это требует значительного терпения и большого количества кофе, так как даже конечный автомат средних размеров может иметь до 100 различных переходов. Кстати, количество переходов – это отличный способ измерить сложность системы. Последнее определяется требованиями заказчика, а конечный автомат делает очевидными объемы тестирования. При менее организованном подходе объем требуемого тестирования может оказаться таким же внушительным, но вы об этом просто не узнаете.

Очень удобно использовать в коде операторы печати, выводящие текущее состояние, значения входных и выходных сигналов. Это позволяет вам с легкостью наблюдать то, что выражает «Золотое Правило Тестирования Программ»: проверяйте, что программа выполняет задуманное, а также то, что она не делает ничего лишнего. Другими словами, получаете ли вы только те выходные сигналы, которые вы ожидаете, и что еще происходит помимо этого? Нет ли «затруднительных» переходов состояний, т.е. состояний, которые случайно проходят, только для одного повтора цикла? Меняются ли выходные сигналы, когда вы этого не ожидаете? В идеале выходные сигналы ваших printfs должны заметно напоминать таблицу перехода состояний.

Наконец - и это касается любого встроенного ПО, а не только ПО, основанного на конечных автоматах - будьте очень осторожны при первом запуске ПО на реальном оборудовании. Очень легко ошибиться с полярностью сигналов – «Ой, я думал, что «1» означает поднять шасси, а «0» - опустить его». Во многих случаях, мой помощник по оборудованию применял временный «куриный переключатель» для защиты ценных компонентов, пока не был уверен, что мое ПО перемещает предметы в правильном направлении.

Запуск

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

Мартин Гомез – программист Лаборатории Прикладной Физики при Университете Джона Хопкинса. Занимается разработкой ПО для обеспечения полетов исследовательских космических кораблей. Проработал в области разработки встраиваемых систем в течение 17 лет. Мартин – бакалавр наук в области аэрокосмического инжиниринга и магистр в области электроинжиниринга (университет Корнелл).

В статье рассмотрены простые конечные автоматы и их реализация на C++ с помощью switch-конструкций, таблиц времени исполнения и библиотеки Boost Statechart .

Введение

Грубо говоря, конечный автомат (Finite State Machine), глазами пользователя – это черный ящик, в который можно что-то передать и что-то оттуда получить. Это очень удобная абстракция, которая позволяет скрыть сложный алгоритм, кроме того конечные автоматы очень эффективны.

Конечные автоматы изображают в виде диаграмм состоящих из состояний и переходов. Поясню на простом примере:

Как вы наверное догадались – это диаграмма состояний лампочки. Начальное состояние обозначается черным кружком, переходы стрелками, некоторые стрелки подписаны – это события после которых автомат переходит в другое состояние. Итак, сразу из начального состояния, мы попадаем в состояние Light Off – лампа не горит. Если нажать кнопку, то автомат изменит свое состояние и перейдет по стрелке помеченной Push Button , в состояние Light On – лампа горит. Перейти из этого состояния можно опять же по стрелке, после нажатия кнопки, в состояние Light Off .

Также широко используются таблицы переходов:

Практическое применение автоматов

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

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

Для примера мы реализуем автомат для подсчета чисел и слов в тексте. Для начала договоримся, что числом будет считаться последовательность цифр от 0 до 9 произвольной длины, окруженная пробельными символами (пробел, табуляция, перевод строки). Словом будет считаться последовательность произвольной длины состоящая из букв и также окруженная пробельными символами.

Рассмотрим диаграмму:

Из начального состояния мы попадаем в состояние Start . Проверяем текущий символ, и если он является буквой, то переходим в состояние Word по стрелке помеченной как Letter . Это состояние предполагает, что в данный момент мы рассматриваем слово, анализ дальнейших символов, либо подтвердит данное предположение, либо опровергнет. Итак, рассматриваем следующий символ, если он является буквой, то состояние не изменяется (обратите внимание на круговую стрелку помеченную как Letter ). Если символ не является буквой, а соответствует пробельному символу, то это означает, что предположение было верным и мы обнаружили слово (делаем переход по стрелке Space в состояние Start ). Если символ не является, ни буквой, ни пробелом, значит мы ошиблись в предположении и последовательность которую мы рассматриваем, не является словом (переходим по стрелке Unknown в состояние Skip ).

В состоянии Skip мы находимся до тех пор, пока не будет встречен пробельный символ. После того как пробел был обнаружен мы переходим по стрелке Space в состояние Start . Это нужно, чтобы полностью пропустить строку не соответствующую нашему шаблону поиска.

После перехода в состояние Start , поиск цикл повторяется с начала. Ветвь с распознаванием чисел аналогична ветви распознавания слов.

Автомат с использованием switch-инструкций

Первое – возможные состояния:

После чего мы итерируем по строке подсовывая автомату текущий символ. Сам автомат представляет собой инструкцию switch сначала выполняющей переход в секцию текущего состояния. Внутри секции есть конструкция if-else, которая в зависимости от события (пришедшего символа) изменяет текущее состояние:

const size_t length = text.length () ; for (size_t i = 0 ; i ! = length; ++ i) { const char current = text[ i] ; switch (state) { case State_Start: if (std:: isdigit (current) ) { state = State_Number; } else if (std:: isalpha (current) ) { state = State_Word; } break ; case State_Number: if (std:: isspace (current) ) {

Здесь смотрим на диаграмму – текущее состояние Number , событие Space (встречен пробельный символ), а значит найдено число:

FoundNumber() ; state = State_Start; } else if (! std:: isdigit (current) ) { state = State_Skip; } break ; case State_Word: if (std:: isspace (current) ) { FoundWord() ; state = State_Start; } else if (! std:: isalpha (current) ) { state = State_Skip; } break ; case State_Skip: if (std:: isspace (current) ) { state = State_Start; } break ; } }

Итог:

Высокая эффективность

Простота реализации для простых алгоритмов

— Тяжело поддерживать

Интерпретация времени выполнения

Идея данного подхода проста – надо создать таблицу переходов, заполнить ее, и потом, при наступлении события, найди в таблице следующее состояние и сделать переход:

enum Events { Event_Space, Event_Digit, Event_Letter, Event_Unknown } ; void ProcessEvent(Events event) ; ... struct Transition { States BaseState_; Events Event_; States TargetState_; } ; void AddTransition(States fromState, Events event, States toState) ; ... typedef std:: vector < transition> TransitionTable; TransitionTable Transitions_; States CurrentState_;

Заполнение таблицы:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Получилось довольно наглядно. Платой за наглядность будет более медленная работа автомата, что впрочем, часто не имеет значения.

Чтобы автомат, при наступлении некоторых событий, мог оповестить некоторый код, можно добавить в структуру с информацией о переходе (Transition ) указатель на функцию (Action ), которая будет вызываться:

typedef void (DynamicMachine:: * Action) () ; struct Transition { States BaseState_; Events Event_; States TargetState_; Action Action_; } ; ... void AddTransition(States fromState, Events event, States toState, Action action) ; ... AddTransition (State_Number, Event_Space, State_Start, & DynamicMachine:: FoundNumber ) ;

Итог:

Гибкость и наглядность

Проще поддерживать

— Меньшая производительность по сравнению с switch-блоками

Интерпретация времени исполнения. Оптимизация по скорости

Можно ли объединить наглядность со скоростью? Сделать автомат настолько же эффективным, как автомат на switch-блоках вряд ли удастся, но сократить разрыв можно. Для этого надо из таблицы, построить матрицу, такую, чтобы для получения информации о переходе не выполнять поиск, а сделать выборку по номеру состояния и события:

Достигается результат, за счет расхода памяти.

Итог:

Гибкость, наглядность

Эффективен

— Расход памяти (скорее всего несущественно)

Boost Statechart

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

Итак, сначала определим события:

namespace Events { struct Digit : boost:: statechart :: event < Digit> { } ; struct Letter : boost:: statechart :: event < Letter> { } ; struct Space : boost:: statechart :: event < Space> { } ; struct Unknown : boost:: statechart :: event < Unknown> { } ; }

Саму машину (обратите внимание, что второй параметр шаблона – начальное состояние):

struct Machine : boost:: statechart :: state_machine < Machine, States:: Start > { } ;

И собственно сами состояния. Внутри состояний требуется определить тип описывающий переходы (reactions ), а если переходов несколько, то перечислить их в списке типов boost::mpl::list . Второй параметр шаблона simple_state – тип описывающий машину. Переходы описываются параметрами шаблона transition, парой Событие — Следующее состояние :

namespace States { struct Start : boost:: statechart :: simple_state < Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word > > reactions; } ; struct Number : boost:: statechart :: simple_state < Number, Machine> { typedef boost:: mpl :: list < boost:: statechart :: transition < Events:: Space , States:: Start > , boost:: statechart :: transition < Events:: Letter , States:: Skip > , boost:: statechart :: transition < Events:: Unknown , States:: Skip > > reactions; } ; struct Word : boost:: statechart :: simple_state < Word, Machine> { typedef boost:: mpl :: list < boost:: statechart :: transition < Events:: Space , States:: Start > , boost:: statechart :: transition < Events:: Digit , States:: Skip > , boost:: statechart :: transition < Events:: Unknown , States:: Skip > > reactions; } ; struct Skip : boost:: statechart :: simple_state < Skip, Machine> { typedef boost:: statechart :: transition < Events:: Space , States:: Start > reactions; } ; }

Машина построена, осталось только инициализировать ее и можно использовать:

Machine machine; machine.initiate () ; ... machine .process_event (Events:: Space () ) ;

Итог:

Гибкость, расширяемость

— Эффективность

Быстродействие

Я написал тестовую программу для проверки быстродействия построенных автоматов. Через автоматы я прогнал текст размером ~17 Мб. Вот результаты прогона:

Loading text Text length: 17605548 bytes 0.19 s Running BoostMachine Words: 998002, numbers: 6816 0.73 s Running DynamicMachine Words: 998002, numbers: 6816 0.56 s Running FastDynamicMachine Words: 998002, numbers: 6816 0.29 s Running SimpleMachine Words: 998002, numbers: 6816 0.20 s

Что осталось не рассмотренным

Неохваченными остались еще несколько реализаций конечных автоматов (рекомендую http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml и http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), генераторы строящие автоматы из описаний, библиотека Meta State Machine из Boost версии 1.44.0, а также формальные описания конечных автоматов. Со всем перечисленным любопытный читатель может ознакомиться самостоятельно.