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

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

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

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

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

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

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

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

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

stateflow all in one

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

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

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

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

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

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

      Переход к шагу 2.

  1. После активации состояния проверяются возможные переходы из него:

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

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

    1. 3. Если условия изменятся, то реализуется backtracking[1], то есть конечный автомат вернется к предыдущему состоянию и предпримет повторную попытку перехода.

      Переход к шагу 3.

  1. После выполнения перехода машина состояний возвращается к состоянию, из которого начался переход, и выполняет действия секции exit (если они заданы). Это завершает текущий переход, и автомат переходит к следующему состоянию. Переход к шагу 4.

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

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

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

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

В машине состояний группы операторов 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 добавляет возможность реагировать на события, активируя действия, только если эти события происходят при активном состоянии.

Логика работы на переходах с индикаторами изменений

Индикаторы изменений (hasChanged, hasChangedFrom и hasChangedTo) — это условия, которые определяют, когда можно выполнить переход из одного состояния в другое. Они также применяются для любых синтаксически верных логических выражений, например:

haschanged state synth

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

  • hasChanged(variable) проверяет, произошло ли изменение значения входной переменной по сравнению с предыдущим шагом модели. Если значение изменилось, то условие считается выполненным, и конечный автомат может инициировать переход;

  • hasChangedFrom(variable, oldValue) позволяет задать более конкретное условие, проверяя, изменилось ли значение с исходного значения. Переход осуществляется только в том случае, если параметр изменился именно с указанного значения на любое другое;

  • hasChangedTo(variable, newValue) проверяет, стало ли значение параметра равным определенному целевому значению. Переход выполняется, если параметр изменился на указанное значение.

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

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

sf loop 1 1

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

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

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

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

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

Узлы

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

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

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

Переходы

condition action stateflow

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

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

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

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

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

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

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

Случаи использования условий на переходах:

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

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

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

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

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

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

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

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

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

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

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

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

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

  2. Состояния

  3. Узлы

  4. Переходы

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

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