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

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

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

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

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

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

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

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

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

stateflow all in one

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

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

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

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

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

  3. После выполнения действий exit (если они заданы) текущего состояния, происходит переход в следующее состояние или узел. Теперь машина состояний переходит к анализу нового состояния. В новом состоянии первым шагом выполняется группа операторов entry (если они указаны). После этого проверяются условия возможных переходов из нового состояния, и процесс повторяется. Если условия в новом состоянии ложные, то выполняется возврат к предыдущему состоянию. Переход к шагу 4.

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

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

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

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

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

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

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

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

    • Если в новом состоянии есть оператор during, то он начнет выполняться на последующих шагах.

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

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

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

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

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

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

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

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

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

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

  6. during — выполняется циклически, если автомат остается в текущем состоянии.

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

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

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

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

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

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

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

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

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

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

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

sf loop 1 1

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

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

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

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

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

Узлы

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

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

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

Переходы

condition action stateflow

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

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

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

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

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

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

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

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

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

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

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

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

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

Темпоральная логика

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

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

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

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

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

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

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

  2. Состояния

  3. Узлы

  4. Переходы

  5. Темпоральная логика

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