Engee documentation

Logic of finite automata

Page in progress.

See also:

Chart
State machine hierarchy
Transition graphs

State Machines - is an abstract model of computation that sequentially transitions between different states based on input data or events. A finite automaton incorporates two approaches to model building - a state machine and a transition graph.

State machine logic

State machines - is a representation of an event-driven system that transitions from one mode of operation to another when the condition that determines the change is true. State machines use the full available functionality of the Chart block to build finite automaton models, namely:

An example of a finite automaton with a state machine:

stateflow all in one

The execution algorithm consists of the following steps:

General logic of the state machine operation

  1. The operation of the state machine starts before any state is activated:

    1. 1. If there is a default transition (or several such transitions) in the state machine, the actions associated with these transitions are executed first, given their priorities and conditions;

    1. 2. If there are multiple transitions by default, the transitions are analysed in order of priority until a transition with a fulfilled or missing condition is found, after which the corresponding state is activated;

    1. 3. If there are no transitions by default and there is a single state, it is activated automatically.

      Transition to step 2.

  1. In the next machine step, after the state is activated, possible transitions from the active state are checked. Such transitions can be zero, one or several.

    1. 1. If there are no transitions from the current active state, the automaton remains in the same current state and the during and on sections (if set) of this state are executed. The exit section of such a state is never executed.

    1. 2. If the transition from the current state is the only one, its condition is checked. If the condition is not fulfilled, the automaton remains in the same current state, and the during and on sections (if set) of this state are executed. If the condition is true, then firstly, the transition action (if given) is executed. Second:

      1. 2. 1. If the transition leads to another state, the exit section of the current state and the entry section of the other state (if specified) are executed. The other state becomes active instead of the current state (hierarchical states are not considered here).

      1. 2. 2. If the transition leads to the same state (here we consider only external transitions), the exit and entry sections of the current state are executed and it remains active.

      1. 2. 3. If the transition leads to a dead-end node, the current state remains active and its during and on sections (if specified) are executed.

    1. 3. If there are several transitions leaving the current state, the automaton tries to go through them one by one in the order of set priorities until it finds a transition whose condition is fulfilled or absent (composite transitions are not considered here - see the next point). If no such transition is found, the automaton remains in the current state and the during and on sections (if set) of this state are executed. If a transition is found, then see paragraphs 2.2.1, 2.2.2 and 2.2.3.

  1. If any of the transitions (clauses 2.2 and 2.3) is compound (consists of two or more segments) and has forks, the backtrackingfootnote mechanism may be implemented:[Backtracking is a problem-solving method based on an attempt to sequentially search through all possible solutions in order to find the correct one. When a programme reaches a solution node (for example, in a transition graph, it can be an output node) and all possible variants of further actions turn out to be wrong (for example, all transitions from the node have false conditions), it returns (backtracks) to the previous solution node and tries another (alternative) variant.If the condition of the next transition is not fulfilled, the automaton returns to the nearest passed fork, where alternative branches remain untested, and makes a new attempt, but along an alternative path. If there are no forks with alternative paths left, the current state remains active and its sections during and on (if set) are executed.

Operator groups

In the state machine operator groups entry, during and exit initiate the execution of actions when states change and while in a state. The execution logic of these operators is closely related to transitions, states, and activation order. Let’s take a closer look at how each group of operators works and how they interact with each other:

  1. Check conditions for transitions - at each step, the state machine checks whether there is an active transition from the current state. A transition can be conditioned by change indicators conditions (hasChanged, etc.) or by temporal logic (after, etc.) that indicate when a transition can be made;

  2. *Execute the transition if the condition is met:

    • If the transition conditions are met, the finite automaton deactivates the current state;

    • exit - executed before the current state is terminated, if the exit operator group is specified. It terminates all actions associated with that state;

    • It then transitions to a new state, where the entry operator group for that state is executed.

  3. *If the transition does not occur:

    • If the transition conditions are not met, the finite automaton remains in the current state;

    • during: is executed if the state is active and actions for during are specified. This continues at each step as long as the automaton remains in that state and the transition conditions are not met;

    • on - executed when a certain condition occurs, if the current state is active and a group of on operators is associated with this condition.

Priority of execution of operator groups

  1. Transition Condition - checked first to determine if a transition will be made;

  2. Transition Actions - executed after the condition is checked, if the transition is confirmed;

  3. exit - completes execution of the current state before the transition;

  4. on - executed if the state is active and the specified event has occurred;

  5. entry - executed when a new state is activated, preparing it for action execution;

  6. during - executed at each step of the automaton while the current state remains active.

Then the logic of finite automaton with transitions and groups of operators is as follows:

  • At each step, the finite automaton checks the conditions of transitions. If a transition is possible, then exit actions are executed for the current state and then entry for the new state;

  • If no transition is possible, then during actions are performed for the current state;

  • on adds the ability to react to events, activating actions only if those events occur when the state is active.

Transition graph logic

Transition graphs - is a graphical construct representing the flow of operations or logic execution in a system. Unlike state machines, transition graphs are constructed using nodes, transitions and transitions by default, not using states. An example of a finite automaton with a transition graph:

sf loop 1 1

The logic of transition graphs consists of sequentially analysing nodes and transitions, starting with a transition by default. The algorithm can be divided into the following points:

  1. Unlike a state machine, a transition graph is checked completely at each step. A transition is executed if the condition is true or, in the absence of the condition, it is executed by default. If a transition is possible (the condition is true or it is not), the graph performs the actions associated with the transition. Transition to step 2.

  2. When a transition is executed, if the condition is true or absent, the actions defined at that transition are executed. After that, the transition to the next node specified in the graph is executed. Execution of the actions completes the second step and moves to step 3.

  3. If the automaton has arrived at a node, the following actions are performed depending on the three possible outcomes:

    1. 1. The node is deadlocked. If backtracking is possible, it is executed. Otherwise, the automaton step is terminated.

    1. 2. There is one transition coming from the node. The automaton tries to perform this transition. If the condition is met, the automaton executes the transition action and moves to the node to which the transition leads. If the condition is not met, the automaton tries to perform backtracking. If backtracking is possible, backtracking is performed. Otherwise, the automaton step is terminated.

    1. 3. There are several transitions coming from a node. If the automaton is in this node for the first time (within the current step), it tries to execute the transition with the first sequence number. In this case, the number of the transition that the automaton tried to execute is memorised. If the path starting from this transition leads to backtracking, and the automaton returns to the current fork, it will try to execute the next transition in order (with number "2", then "3", etc.) until it exhausts all available transitions or executes one of them successfully.

  4. If the transition from a node is completed, the automaton moves to the next node and continues execution from point 1. If the transition from a node is not executed and backtracking is possible, then backtracking is executed. If backtracking is not possible, the automaton step is terminated. The whole execution logic is based solely on transitions between nodes, as well as memorising and sequentially checking the sequence numbers of transitions in the branch nodes.

Nodes

Node are key elements of transition graphs, serving as conjugate points of transitions. They define the points through which transitions pass, organising an ordered sequence of steps in the model.

Transitions By default

A Default transition is a special type of transition, it has no initial node or state and is executed before they are activated. The system automatically adds a By default transition for the first state and adds a node for the transition. By default transition is not needed if there is only one state in the system.

Transitions

condition action stateflow

transition are connections between nodes that specify the logic for moving from one node to another. Each transition may have a condition that is checked to determine if the transition should be made. Transitions can be conditional (only executed if a certain condition is true) or unconditional (always executed if active). If there are multiple transitions from a state or node, the programme assigns them explicit priorities, displayed numerically (1,2,3, etc.). During the simulation, the transitions are checked in this order and the first available transition with a true condition is executed.

Typical cases of transition logic:

  • Simple transitions between nodes, performed when conditions related to variables, parameters or calculation results are met;

  • Transitions depending on change indicators (hasChanged, hasChangedFrom, hasChangedTo), temporal logic operators, etc., which are executed when the values of certain parameters change;

  • Backtracking logic, where transitions can return execution to the previous node to check for alternative paths if the condition of the current transition is not met.

Conditions on transitions

Conditions on transitions [] specify logical expressions that define when a transition should occur. These conditions can include comparing values, checking logical expressions, or usage of logical operators such as hasChanged. If the condition is true, the transition is made and execution continues on the next node.

Examples of usage of conditions on transitions:

  • A condition can check ranges of values, e.g., the transition is only executed when a certain level of parameters is reached;

  • Logical expressions can include multiple checks, e.g., a set of conditions (A > 5 || B < 10);

  • Change indicators are used to determine if the system state has changed at a particular point in time.

Actions on transitions

Actions on transitions {} define which Julia operators will be executed on a transition. Actions on transitions allow you to control the change of the data state and ensure that the necessary logic is implemented depending on the selected route (priority of transitions).

Operators of temporal logic

Operators of temporal logic transitions allow to take into account temporal aspects or conditions related to the frequency of occurrence of events. The logical operators after, at, and every (etc.), set conditions for transitions based on time, repetition, or frequency of events. Can be used in a state machine within states with a group of on operators and at transitions.

Examples of applications of temporal logic:

  • Usage of the after operator to specify a transition that is executed after a given time interval or number of state machine steps after activation of the state associated with this operator;

  • Setting a transition using the at operator that is executed only at a given step since the activation of the state associated with this operator;

  • Implementing repetitive actions by usage of the every operator to set the periodicity of execution.

Memory nodes

Memory node stateflow history junction allows a finite automaton to remember the last active child state and restore it when the parent state is reactivated. A memory node is used in situations where it is necessary to preserve the context of the automaton and continue execution from the same place, even after exiting and re-entering a state. The logic of the memory node is based on memorising the current child state and activating it when certain conditions are met, e.g. after the during and on groups of the parent state are executed.

Examples of memory node application:

  • Restoring the last active child state when the parent state is reactivated;

  • Implementing complex scenarios where it is necessary to temporarily exit a state and return to it with the context intact;

  • Management of transitions between child states with regard to the memorised state.

  1. State machines

  2. Condition

  3. Node

  4. transition

  5. Operators of temporal logic