Первоисточник: http://en.wikipedia.org/wiki/Finite_state_machine

Статья посвящена конечным управляющим автоматам, их классификации. В ней рассматриваются два класса управляющих автомата: автомат Мура и автомат Мили.

Перевод на русский язык выполнил: Малюк Е.В.

Конечный управляющий автомат

Конечный управляющий автомат (FSM) (множ.: автоматы) – модель сформированного поведения конечного количества состояний, переходов между этими состояниями, и действиями.

Рис. 1. Конечный управляющий автомат

 

Понятия и словарь

 

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

Действие входа,

которое выполняется при входе в состояние

Действие выхода,

которое выполняется при выходе из состояния

Действие ввода,

которое выполняется в зависимости от данного состояния и входного условия

Действие перехода,

которое выполняется при выполнении определенного перехода.

FSM может быть представлен с помощью управляющей диаграммы (или управляющей диаграммы переходов), как на рисунке 1. Кроме этого, используются несколько управляющих таблиц перехода. Наиболее общее представление показано ниже: комбинация текущего состояния (B) и условие (Y) показывает следующее состояние (C). Полная информация действий может добавляться только используя сноски. Определение FSM включает полную информацию о действиях, которые возможно используют управляющие таблицы.

 

Управляющая таблица переходов
Текущее состояние/ условие перехода	Состояние A	Состояние B	Состояние C
Условие X	...	...	...
Условие Y	...	Состояние C	...
Условие Z	...	...	...

 

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

 

Классификация

 

Выделяют две разные группы: Акцептор/Распознаватель и Преобразователи.

 

Преобразователи

 

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

Рис. 2. Преобразователь FSM : пример модели автомата Мура

 

Автомат Мура: FSM использует действия только входа, то есть выход зависит только от состояния. Преимущество модели Мура в упрощенном поведении. Пример на рисунке 2 показывает дверь элеватора модели Мура FSM. Управляющий автомат признает две команды: "command_open" и "command_close" с управляющими изменениями триггера. Входа (E:) в состоянии "Открытие" начинает с двигателя, открывающего дверь, вход в состояние "Закрытие" начинает с двигателя в другом направлении, закрывающего дверь. Состояния "Открытие" и "Закрытие" не выполняются любыми действиями. Они сигнализируют во внешний мир (напр., в другим управляющим автоматам) ситуацию: "дверь открыта" или "дверь закрыта".

Рис. 3. Преобразователь FSM : пример модели автомата Мили

Автомат Мили: FSM использует только входные действия, то есть выход зависит от ввода и состояния. Использование автомата Мили улучшает уменьшение количества состояний. Пример на рисунке 3 показывает автомат Мили, осуществляющий то же поведение как в примере Мура (поведение зависит от осуществленной модели выполнения FSM и будет работать напр. для виртуального FSM, но не для управляющего события FSM). Есть два входных действия (I:): "стартовый двигатель, чтобы закрывать дверь, если command_close активна" и "стартовый двигатель в другом направлении, чтобы открывать дверь, если command_open активна".

На практике часто используются смешанные модели.

Больше подробностей о различиях и использовании моделей Мура и Мили, включая выполняемый пример, можно найти во внешнем техническом примечании "Модель Мура или Мили?"

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

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