Документация Engee

Логика работы конечных автоматов

Страница в процессе разработки.

Смотрите также:

Chart
Иерархия машины состояний
Графы переходов

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

Логика машины состояний

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

Пример конечного автомата с машиной состояний:

stateflow all in one

Алгоритм выполнения состоит из следующих этапов:

Общая логика работы машины состояний

  1. Работа машины состояний начинается до активации какого-либо состояния:

    1. 1. Если в машине состояний есть переход по умолчанию (или несколько таких переходов), то сначала выполняются действия, связанные с этими переходами, с учетом их приоритетов и условий;

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

    1. 3. Если же переходов по умолчанию нет и есть единственное состояние, то оно активируется автоматически.

      Переход к пункту 2.

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

    1. 1. Если переходы из текущего активного состояния отсутствуют, то автомат остается в том же текущем состоянии, и выполняются секции during и on (если заданы) этого состояния. Секция exit такого состояния не выполняется никогда.

    1. 2. Если переход из текущего состояния единственный, то проверяется его условие. Если условие не выполнилось, то автомат остается в том же текущем состоянии, и выполняются секции during и on (если заданы) этого состояния. Если же условие имеет значение "истина", то, во-первых, выполняется действие перехода (если задано). Во-вторых:

      1. 2. 1. Если переход ведет в другое состояние, выполняются секция exit текущего состояния и секция entry другого состояния (если заданы). Другое состояние становится активным вместо текущего (здесь не рассматриваются иерархические состояния).

      1. 2. 2. Если переход ведет в то же самое состояние (здесь мы рассматриваем только внешние переходы), выполняются секции exit и entry текущего состояния, и оно остается активным.

      1. 2. 3. Если переход ведет в тупиковый узел, то текущее состояние остается активным, и выполняются его секции during и on (если заданы).

    1. 3. Если из текущего состояния выходят несколько переходов, то автомат поочередно пытается пройти по ним в порядке установленных приоритетов, пока не встретится переход, условие которого выполняется или отсутствует (здесь не рассматриваются составные переходы — см. следующий пункт). Если не нашлось ни одного такого перехода, то автомат остается в текущем состоянии, и выполняются секции during и on (если заданы) этого состояния. Если же переход найден, то см. пункты 2.2.1, 2.2.2 и 2.2.3.

  1. Если какой-либо из переходов (п.п. 2.2 и 2.3) — составной (состоит из двух или более сегментов) и имеет развилки, может реализоваться механизм backtracking[1]: перемещаясь по переходам сообразно их приоритетам и условиям, то автомат запоминает пройденные развилки, и, если условие очередного перехода не выполняется, то автомат возвращается к ближайшей пройденной развилке, где остались не протестированными альтернативные ветви, и предпринимает новую попытку, но уже по альтернативному пути. Если развилок с альтернативными путями не осталось, то текущее состояние остаётся активным, и выполняются его секции during и on (если заданы).

Группы операторов

В машине состояний группы операторов entry, during и exit инициируют выполнение действий при изменении состояний и во время нахождения в состоянии. Логика выполнения этих операторов тесно связана с переходами, состояниями и порядком активации. Рассмотрим подробнее, как работает каждая группа операторов и каким образом они взаимодействуют между собой:

  1. Проверка условий переходов — на каждом шаге машина состояний проверяет, есть ли активный переход из текущего состояния. Переход может быть обусловлен условиями индикаторов изменений (hasChanged и т.д.) или темпоральной логикой (after и др.), которые указывают, когда можно совершить переход;

  2. Выполнение перехода, если условие выполнено:

    • Если условия перехода выполняются, то конечный автомат деактивирует текущее состояния;

    • exit — выполняется перед завершением текущего состояния, если группа операторов exit указана. Она завершает все действия, связанные с этим состоянием;

    • Затем происходит переход в новое состояние, где выполняется группа операторов entry для этого состояния.

  3. Если переход не происходит:

    • Если условия перехода не выполнены, то конечный автомат остается в текущем состоянии;

    • during — выполняется, если состояние активно и указаны действия для during. Это продолжается на каждом шаге, пока автомат остается в этом состоянии и условия перехода не выполняются;

    • on — выполняется при возникновении определенного условия, если текущее состояние активно и группа операторов on связана с этим условием.

Приоритет выполнения групп операторов

  1. Условие перехода — проверяется первым, чтобы определить, будет ли совершен переход;

  2. Действия на переходе — выполняются после проверки условия, если переход подтвержден;

  3. exit — завершается выполнение текущего состояния перед переходом;

  4. on — выполняется, если состояние активно и наступило указанное событие;

  5. entry — выполняется при активации нового состояния, подготавливая его к выполнению действий;

  6. during — выполняется на каждом шаге автомата, пока текущее состояние остается активным.

Тогда логика работы конечного автомата с переходами и группами операторов следующая:

  • На каждом шаге конечный автомат проверяет условия переходов. Если переход возможен, то выполняются действия exit для текущего состояния, а затем entry для нового;

  • Если переход не происходит, то выполняются действия during для текущего состояния;

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

Логика графов переходов

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

sf loop 1 1

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

  1. В отличие от машины состояний, граф переходов проверяется полностью на каждом шаге. Переход выполняется, если условие истинно, или, при отсутствии условия, выполняется по умолчанию. Если переход возможен (условие истинно или его нет), то граф выполняет действия, связанные с переходом. Переход к пункту 2.

  2. При выполнении перехода, если условие истинно или отсутствует, то выполняются действия, определенные на этом переходе. После этого выполняется переход к следующему узлу, указанному в графе. Выполнение действий завершает второй шаг и переводит к пункту 3.

  3. Если автомат пришел в узел, то выполняются следующие действия в зависимости от трех возможных исходов:

    1. 1. Узел тупиковый. Если возможен backtracking, то он выполняется. В противном случае шаг автомата завершается.

    1. 2. Из узла исходит один переход. Автомат пытается выполнить этот переход. Если условие выполняется, то автомат выполняет действие перехода и переходит к узлу, к которому ведет этот переход. Если условие не выполняется, то автомат пытается выполнить backtracking. Если backtracking возможен, то выполняется backtracking. В противном случае шаг автомата завершается.

    1. 3. Из узла исходит несколько переходов. Если автомат находится в этом узле впервые (в рамках текущего шага), то он пытается выполнить переход первым порядковым номером. При этом запоминается номер перехода, который пытался выполнить автомат. Если путь, начинающийся с данного перехода, приводит к backtracking, и автомат возвращается в текущую развилку, то он попытается выполнить следующий по порядку переход (с номером "2", затем "3" и т.д.), пока не исчерпает все доступные переходы или не выполнит один из них успешно.

  4. Если переход из узла выполнен, то автомат перемещается к следующему узлу и продолжает выполнение с пункта 1. Если переход из узла не выполнен, и возможен backtracking, то выполняется backtracking. Если backtracking невозможен, то шаг автомата завершается. Вся логика выполнения основана исключительно на переходах между узлами, а также запоминании и последовательной проверке порядковых номеров переходов в узлах-развилках.

Узлы

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

Переходы по умолчанию

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

Переходы

condition action stateflow

Переходы представляют собой соединения между узлами, которые задают логику перехода от одного узла к другому. Каждый переход может иметь условие, которое проверяется для определения, следует ли совершить переход. Переходы могут быть условными (выполняются только при истинности определенного условия) или безусловными (выполняются всегда, если они активны). Если из состояния или узла исходит несколько переходов, то программа назначает им явные приоритеты, отображаемые численно (1,2,3 и т.д.). Во время симуляции переходы проверяются в этом порядке, и выполняется первый доступный переход с истинным условием.

Типичные случаи логики переходов:

  • Простые переходы между узлами, осуществляемые при выполнении условий, связанных с переменными, параметрами или результатами вычислений;

  • Переходы, зависящие от индикаторов изменений (hasChanged, hasChangedFrom, hasChangedTo), операторов темпоральной логики и т.д., которые выполняются при изменении значений определенных параметров;

  • Логика backtracking, где переходы могут возвращать выполнение к предыдущему узлу для проверки альтернативных путей, если условие текущего перехода не выполняется.

Условия на переходах

Условия на переходах [] задают логические выражения, которые определяют, когда должен произойти переход. Эти условия могут включать сравнение значений, проверки логических выражений или использование логических операторов, таких как hasChanged. Если условие истинно, то переход осуществляется, и выполнение продолжается на следующем узле.

Примеры использования условий на переходах:

  • Условие может проверять диапазоны значений, например, переход осуществляется только при достижении определенного уровня параметра;

  • Логические выражения могут включать несколько проверок, например, совокупность условий (A > 5 || B < 10);

  • Индикаторы изменений используются для определения, изменилось ли состояние системы в определенный момент.

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

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

Операторы темпоральной логики

Операторы темпоральной логики переходов позволяет учитывать временные аспекты или условия, связанные с частотой наступления событий. Логические операторы after, at, и every (и др.), задают условия для переходов, основанных на времени, повторении или частоте событий. Могут использоваться в машине состояний внутри состояний с группой операторов on и на переходах.

Примеры применения темпоральной логики:

  • Использование оператора after для задания перехода, который выполняется после заданного промежутка времени или количества шагов машины состояний после активации состояния, ассоциированного с данным оператором;

  • Установка перехода с помощью оператора at, который выполняется только на заданном шаге с момента активации состояния, ассоциированного с данным оператором;

  • Реализация повторяющихся действий с использованием оператора every, чтобы задавать периодичность выполнения.

Полезные ссылки

  1. Машины состояний

  2. Состояния

  3. Узлы

  4. Переходы

  5. Операторы темпоральной логики

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