Finite machine: theory and implementation. Types of finite state machines Practical application of state machines

Finite machine: theory and implementation. Types of finite state machines Practical application of state machines

Automata theory is a branch of discrete mathematics that studies models of discrete information converters. Such converters are both real devices (computers, living organisms) and imaginary devices (axiomatic theories, mathematical machines). Essentially, a finite state machine can be characterized as a device M , having input and output channels, and at each of the discrete moments of time, called clock moments, it is in one of the final states.

By input channel at each moment of time t =1, 2, ... to device M input signals arrive (from some finite set of signals). The law of state change at the next time is set depending on the input signal and the state of the device at the current time. The output signal depends on the state and input signal at the current time (Fig. 1).

A finite state machine is a mathematical model of real discrete information processing devices.

State machine called system A= (X , Q , Y , , ), Where X , Q , Y are arbitrary non-empty finite sets, and And - functions, of which:

    a bunch of X ={a 1 , ..., a m ) is called input alphabet , and its elements are input signals , their sequences are in in common words ;

    a bunch of Q ={q 1 , ..., q n ) is called many states automaton, and its elements - states ;

    a bunch of Y ={b 1 , ..., b p ) is called output alphabet , its elements are output signals , their sequences are exit words ;

    function : X Q Q called transition function ;

    function :X Q Y called output function .

Thus, (x , q )Q , (x , q )Y for  x X , q Q .

A finite state machine is associated with an imaginary device that works as follows. It can be in one of many states Q , perceive signals from a variety of X and issue signals from a variety of Y .

2. Methods for specifying a finite state machine

There are several equivalent ways to define abstract automata, among which three can be named: tabular , geometric And functional .

2.1. Tabular task of the machine

From the definition of an automaton it follows that it can always be specified by a table with two inputs containing T lines and P columns, where at the intersection of the column q and strings A are the function values (a i , q j ), (a i , q j ).

q

a

q 1

q j

q n

a 1

(a 1 , q 1), (a 1 , q 1)

(a 1 , q j ), (a 1 , q j )

(a 1 , q n ), (a 1 , q n )

a i

(a i , q 1), (a i , q 1)

(a i , q j ), (a i , q j )

(a i , q n ), (a i , q n )

a m

(a m , q 1), (a m , q 1)

(a m , q j ), (a m , q j )

(a m , q n ), (a m , q n )

2.2. Specifying an automaton using a Moore diagram

Another way to define a finite state machine is graphically, that is, using a graph. The automaton is depicted as a labeled directed graph G(Q , D ) with many vertices Q and many arcs D ={(q j , (a i , q j ))| q j Q , a i X ), while the arc ( q j , (a i , q j )) is marked with the pair ( a i , (a i , q j )). Thus, with this method, the states of the machine are represented by circles in which state symbols are written q j (j = 1, …, n ). From each circle it is carried out T arrows (oriented edges) one-to-one corresponding to characters of the input alphabet X ={a 1 , ..., a m ). Arrow corresponding to letter a i X and leaving the circle q j Q , is attributed to the pair ( a i , (a i , q j )), and this arrow leads to the circle corresponding (a i , q j ).

The resulting drawing is called automaton graph or, Moore diagram . For not very complex machines, this method is more visual than tabular.

A finite state machine is some abstract model containing a finite number of states of something. Used to represent and control the flow of execution of any commands. The state machine is ideal for implementing artificial intelligence in games, producing a neat solution without writing bulky and complex code. In this article we will look at the theory and also learn how to use a simple and stack-based state machine.

We have already published a series of articles on writing artificial intelligence using a finite state machine. If you haven't read this series yet, you can do so now:

What is a finite state machine?

A finite state machine (or simply FSM - Finite-state machine) is a computing model based on a hypothetical state machine. Only one state can be active at a time. Therefore, in order to perform any actions, the machine must change its state.

State machines are typically used to organize and represent the execution flow of something. This is especially useful when implementing AI in games. For example, to write the “brain” of an enemy: each state represents some kind of action (attack, dodge, etc.).

A finite state machine can be represented as a graph, the vertices of which are states, and the edges are transitions between them. Each edge has a label indicating when the transition should occur. For example, in the image above you can see that the machine will change the “wander” state to the “attack” state, provided that the player is nearby.

Planning states and their transitions

The implementation of a finite state machine begins with identifying its states and transitions between them. Imagine a state machine that describes the actions of an ant carrying leaves to an anthill:

The starting point is the "find leaf" state, which remains active until the ant finds the leaf. When this happens, the state will change to “go home”. This same state will remain active until our ant gets to the anthill. After this, the state changes again to “find leaf”.

If the “find leaf” state is active, but the mouse cursor is near the ant, then the state changes to “run away”. Once the ant is at a safe enough distance from the mouse cursor, the state will change back to “find leaf”.

Please note that when heading home or away from home, the ant will not be afraid of the mouse cursor. Why? But because there is no corresponding transition.

Implementation of a simple finite state machine

A finite state machine can be implemented using a single class. Let's call it FSM. The idea is to implement each state as a method or function. We will also use the activeState property to determine the active state.

Public class FSM ( private var activeState:Function; // pointer to the active state of the machine public function FSM() ( ) public function setState(state:Function) :void ( activeState = state; ) public function update() :void ( if ( activeState != null) ( activeState(); ) ) )

Every state is a function. Moreover, such that it will be called every time the game frame is updated. As already mentioned, activeState will store a pointer to the active state function.

The update() method of the FSM class must be called every frame of the game. And it, in turn, will call the function of the state that is currently active.

The setState() method will set the new active state. Moreover, each function that defines some state of the automaton does not necessarily belong to the FSM class - this makes our class more universal.

Using a state machine

Let's implement an ant AI. Above we have already shown a set of its states and transitions between them. Let's illustrate them again, but this time we'll focus on the code.

Our ant is represented by the Ant class, which has a brain field. This is just an instance of the FSM class.

Public class Ant ( public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) ( position = new Vector3D(posX, posY); velocity = new Vector3D( -1, -1); brain = new FSM(); // Start by finding the leaf. brain.setState(findLeaf); * Makes the ant search for leaves. ) :void ( ) /** * State "goHome". * Makes the ant go to the anthill */ public function goHome() :void ( ) /** * State "runAway". / public function runAway() :void ( ) public function update():void ( // Update the state machine. This function will call the // active state function: findLeaf(), goHome() or runAway(). brain.update( ); // Applying velocity to the ant's movement. moveBasedOnVelocity();

The Ant class also contains velocity and position properties. These variables will be used to calculate the motion using Euler's method. The update() function is called every time the game frame is updated.

Below is an implementation of each method, starting with findLeaf() - the state responsible for finding leaves.

Public function findLeaf() :void ( // Moves the ant to the leaf. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game .instance.leaf, this)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

goHome() state - used to make the ant go home.

Public function goHome() :void ( // Moves the ant to the house velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game. instance.home, this)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

And finally, the runAway() state is used when dodging away from the mouse cursor.

Public function runAway() :void ( // Moves the ant away from the cursor velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Is the cursor still nearby? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // No, it’s already far away. It’s time to go back to looking for the leaf. brain.setState(findLeaf); ) )

FSM improvement: stack based automaton

Imagine that an ant on its way home also needs to run away from the mouse cursor. This is what the FSM states will look like:

It seems like a trivial change. No, this change creates a problem for us. Imagine that the current state is “run away”. If the mouse cursor moves away from the ant, what should it do: go home or look for a leaf?

The solution to this problem is a stack-based state machine. Unlike the simple FSM we implemented above, this type of FSM uses a stack to manage states. At the top of the stack is the active state, and transitions occur when states are added/removed from the stack.

And here is a visual demonstration of the operation of a stack-based state machine:

Implementation of a stack based FSM

Such a state machine can be implemented in the same way as a simple one. The difference will be the use of an array of pointers to the required states. We no longer need the activeState property, because the top of the stack will already point to the active state.

Public class StackFSM ( private var stack:Array; public function StackFSM() ( this.stack = new Array(); ) public function update() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) public function popState() :Function ( return stack.pop(); ) public function pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ; ) ) public function getCurrentState() :Function ( return stack.length > 0 ? stack : null; ) )

Note that the setState() method has been replaced with pushState() (adding a new state to the top of the stack) and popState() (removing a state at the top of the stack).

Using Stack Based FSM

It is important to note that when using a stack-based state machine, each state is responsible for being removed from the stack when it is no longer needed. For example, the attack() state should remove itself from the stack if the enemy has already been destroyed.

Public class Ant ( (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Start by searching for the leaf brain.pushState( findLeaf); (...) ) /** * State "findLeaf". * Forces the ant to search for leaves */ public function findLeaf() :void ( // Moves the ant to the leaf. velocity = new Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // No, it’s already far away. It’s time to go back to looking for leaves. brain.popState(); ) ) (...) )

Conclusion

State machines are certainly useful for implementing artificial intelligence logic in games. They can be easily represented as a graph, allowing the developer to see all possible options.

Implementing a state machine with state functions is a simple yet powerful technique. Even more complex state weaves can be implemented using FSM.

One of the criteria for the complexity of a finite state machine is the number of its states. The smaller this number, the simpler the discrete device that implements this machine. Therefore, one of the important tasks of the theory of finite automata is the construction of an automaton with the smallest number of states.

Since in modern computers any information is represented in the form of binary codes, to build an automaton you can use elements that have only two different stable states, one of which corresponds to the number 0, and the other to the number 1.

Let's give some examples of finite state machines.

Example 1. Delay element (memory element).

Delay elements are a device that has one input and one output. Moreover, the value of the output signal at the moment of time t coincides with the signal value at the previous moment. Schematically, the delay element can be depicted as follows (Fig. 2).

Let us assume that the input and, therefore, output alphabet is X ={0, 1}, Y =(0, 1). Then Q =(0, 1). Under the state of the delay element at the time t the content of a memory element at a given moment is understood. Thus q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Let's set the delay element with a table, where A 1 =0, A 2 =1, q 1 =0, q 2 =1,

(a 1 , q 1)= (0, 0)=0, (a 1 , q 1)= (0, 0)=0;

(a 1 , q 2)= (0, 1)=0, (a 1 , q 2)= (0, 1)=1;

(a 2 , q 1)= (1, 0)=1, (a 2 , q 1)= (1, 0)=0;

(a 2 , q 2)= (1, 1)=1, (a 2 , q 2)= (1, 1)=1;

q

a

=0, =0

=0, =1

=1, =0

=1, =1

The Moore diagram is shown in Fig. 3

To represent this automaton as a system of Boolean functions, we use the automaton table and the above algorithm. In this case, there is no need to perform encoding, since the input and output alphabets and states are already encoded.

Let us pay attention to the fact that t=p=p =2. Then k =r =s =1, and therefore the delay element is given by two functions And . The truth table of these functions contains 2 k + r =2 2 =4 lines and k +r +r +s =4 columns:

x

z

Example 2. Binary sequential adder.

This sequential adder is a device that adds two numbers in the binary system. Numbers are supplied to the inputs of the adder X 1 and x 2, starting from the least significant digits. The output generates a sequence corresponding to the number entry X 1 +x 2 in the binary system (Fig. 4).

The input and output alphabets are uniquely defined: X ={00; 01; 10; 11}, Y =(0,1). The set of states is determined by the value of the carry when adding the corresponding digits of numbers X 1 and x 2. If a carry occurs when adding some bits, then we will assume that the adder has entered the state q 1 . In the absence of a carry, we will assume that the adder is in the state q 0 .

The adder is specified by a table.

q

a

q 0

q 1

q 0 , 0

q 0 , 1

q 0 , 1

q 1 , 0

q 0 , 1

q 1 , 0

q 1 , 0

q 1 , 1

The Moore diagram of a sequential adder is shown in Fig. 5.

Note that the input and output symbols are already encoded. We encode the states as follows: (q 0)=0, (q 1)=1. Therefore, the sequential adder is specified by two Boolean functions, the truth table of which is as follows:

x 1

x 2

z

Example 3. Equality comparison scheme.

An equality comparison circuit is a device that compares two numbers X 1 and x 2, given in binary number system. This device works as follows. The digits of numbers are fed to the input of the device sequentially, starting with the most significant ones. X 1 and x 2. These digits are compared. If the bits coincide at the output of the circuit, an output signal of 0 is generated, otherwise a signal of 1 appears at the output. It is clear that the appearance of 1 in the output sequence means that the numbers being compared X 1 and x 2 are different. If the output sequence is zero and its length coincides with the number of digits of the numbers being compared, then X 1 and x 2 .

For this machine X ={00, 01, 10, 11}; Y ={0,1}.

The functioning of the circuit is determined by two states. State q 0 corresponds to the equality of the currently compared digits. In this case, the machine remains in the same state. If at the next moment the compared digits are different, the machine will go into a new state q 1 and remains in it, since this means that the numbers are different. Thus, the comparison scheme can be specified by the table:

q

x

q 0

q 1

q 0 , 0

q 1 , 1

q 1 , 1

q 1 , 1

q 1 , 1

q 1 , 1

q 0 , 0

q 1 , 1

The Moore diagram of the equality comparison scheme is shown in Fig. 6.

We will encode the states as follows: (q 0)=0, (q 1)=1. The machine will be specified by two functions.

x 1

x 2

z

Example 4. Inequality comparison scheme.

An inequality comparison circuit is a device that allows you to find out whether the things being compared are equal. X 1 and x 2, and if they are not equal, find out which one is greater than the other. This device has two inputs and two outputs. Output signals y 1 (t ) And y 2 (t ) are determined according to the following rules:

y 1 (t )=y 2 (t )=0, if x 1 (t )=x 2 (t );

y 1 (t )=1, y 2 (t )=0, if x 1 (t )>x 2 (t ), that is x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1, if x 1 (t )<x 2 (t ), that is x 1 (t )=0, x 2 (t )=1.

Thus, when fed to the input of the comparison circuit for the inequality of numbers x 1 =x 1(l)… x 1 (t ) And x 2 =x 2(l)… x 2 (t )the digits of these numbers are sequentially compared, starting with the most significant ones. The output signals are formulated according to the above rules. Moreover, if the output sequence consists of zero pairs, then x 1 =x 2. If the first non-zero pair has the form , () That x 1 >x 2 (x 1 <x 2).

From the description of the circuit it follows that

X ={00, 01, 10, 11}, Y ={00, 01, 10}.

The state of the circuit is determined as follows. Let us assume that at the initial moment of time t =1 machine is in the state q 1 . If the compared digits of numbers X 1 And X 2 coincide, then the machine remains in this state. Note that a 00 signal will appear at the output. If the digit of the number X 1 will be less (greater) than the corresponding digit of the number X 2, then the machine will go into the state q 2 (q 3). In this case, signal 01 (10) will appear at the output. Subsequently, when submitting the remaining digits of numbers X 1 And X 2 to the inputs of the machine, the machine will remain in the state q 2 (q 3) and generate output symbol 10 (01). From the above it follows that the comparison scheme for inequality can be specified by the table:

q

x

q 1

q 2

q 3

q 1 , 00

q 2 , 01

q 3 , 10

q 2 , 01

q 2 , 01

q 3 , 10

q 3 , 10

q 2 , 01

q 3 , 10

q 1 , 00

q 2 , 01

q 3 , 10

The corresponding Moore diagram is shown in Fig. 7.

The input and output alphabets are already encoded here. States q 1 , q 2 and q Let's encode 3: 1 (q 1)=00, (q 2)=01, (q 3)=10.

Therefore, this circuit can be specified by a system consisting of four Boolean functions that depend on four variables. These functions are partially defined and given by a truth table

x 1

x 2

z 1

z 2

In the table, * symbols mark sets of variables x 1 , x 2 , z 1 , z 2 on which the functions 1 , 2 , 1 , 2 are not defined. Let's put function values 1 , 2 , 1 , 2 on these sets is equal to 1.

Finite state machine theory

Automata theory underlies the theory of compiler construction. A finite state machine is one of the basic concepts. By automaton we do not mean a really existing technical device, although such a device can be built, but a certain mathematical model, the properties and behavior of which can be imitated using a program on a computer. A finite automaton is the simplest model of automata theory and, as a rule, serves as a control device for all other types of automata. The finite state machine has a number of properties:

· A state machine can solve a number of lightweight compilation problems. The lexical block is almost always built on the basis of a finite state machine.

· The operation of the finite state machine is characterized by high performance.

· State machine modeling requires a fixed amount of memory, which simplifies memory management.

· there are a number of theorems and algorithms that allow you to construct and simplify finite state machines.

There are several different definitions of a finite state machine in the literature. However, what they have in common is that a finite state machine models a computing device with a fixed amount of memory that reads sequences of input symbols belonging to some input set. The fundamental differences in definitions are related to what the machine does at the output. The output of the machine can be an indication of whether a given input chain is “acceptable” or not. “Acceptable” is a correctly constructed or syntactically correct chain. For example, a chain that is supposed to represent a numeric constant is considered incorrectly constructed if it contains two decimal points.

Definition: A finite state machine is a formal system that is defined using the following objects:

· finite set of input symbols;

· finite set of states;

· a transition function that assigns each pair (current state, input symbol) a new state;

· initial state;

· a subset of states identified as permissive or final.

Example. Let's analyze the operation of a controller that checks whether the number of ones is even or odd in an arbitrary chain consisting of zeros and ones. Let us assume that the corresponding finite automaton must “accept” all chains containing an odd number of ones and “reject” chains with an even number. Let's call this machine a “parity controller”. We believe that symbols other than 0 and 1 cannot be submitted to the input of the machine. So, the input alphabet of the controller is the set (0, 1) . We believe that at a particular moment in time the finite automaton deals with only one input symbol, and stores information about the previous symbols of the input chain using a finite set of states. We will consider the set (even, odd) as a set of states; one of these states must be chosen as the initial one. Let it be the state (even), since at the first step the number of ones read is zero, and zero is an even number. When reading the next input symbol, the state of the machine either changes or remains the same, and its new state depends on the input symbol and the current state. This change of state is called a transition.



The operation of the machine can be described mathematically by a transition function of the form d(Scurrent, x) = Snew. Otherwise it can be written as follows:

d(even, 0) = even. d(even, 1) = odd.

d(odd, 0) = odd. d(odd, 1) = even.

The controller has a single accepting state, ODD, and EVEN is a “rejecting” state. Let us reflect the sequence of transitions of the machine when chain 1101 is supplied to its input.

EVEN ® ODD ® EVEN ® EVEN ® ODD

The transition table of such an automaton has the form:

even even odd
odd odd even

Definition. A finite state machine is a formal system

S = ( A, Q, d, l, V ),

whose objects are the following:

* A is a finite set of input symbols (set

terminals);

* Q - finite set of internal states of the automaton

(set of non-terminals);

* V - finite set of output symbols (output alphabet);

* d - transition function, which is characterized by A ´ Q ® Q;

* l - output function that determines the display of the view.

Automata theory

Definition of a machine and its variety. Tables and graphs of transitions and outputs. Sub-automatic machines. Reduced automaton theorem

Operations with machines

Converting a Mealy machine into a Moore machine and a Moore machine into a Mealy machine. Automata equivalence. Distinction of states of automata. Minimization of automata. Synthesis of automata. Recognition machines

An automatic machine is a system of mechanisms and devices in which the processes of receiving, converting, and transferring energy, materials, and information are fully automated. The term “automatic machine” is used in two aspects:

1) technical,

2) mathematical.

In the mathematical approach, an automaton is understood as a mathematical model of a technical device that must have inputs, internal states and outputs. There should be no information regarding the details of the structure of the device.

In the technical approach, a machine is understood to be a very real device, for example, a telephone booth, a vending machine, etc. In this case, naturally, the details of the internal structure of the device are known.

A special and important case of an automaton is a digital automaton (DA), in which the processes of receiving, converting, storing and issuing digital information are fully automated.

From the point of view of DA signals, it is useful to define a system that can receive input signals, under their influence, transition from one state to another, maintain it until the next input signal arrives, and produce output signals.

A DA is considered finite if the sets of input signals X, states S, and output signals Y are finite. A finite state machine can be associated with a device such as a computer. The computer processes incoming input data into output data (result), but this result corresponds not only to the input data, but also to the current state of the computer, i.e. the data that is stored in computer memory, for example, the results of previous calculations, calculation programs.

The work of the target audience is carried out in automatic time, determined by the number of periods of receipt of input signals.

An abstract automaton is a mathematical model of a discrete device that has one input channel, which receives sequences of symbols of a language, one output channel, from which sequences of symbols of some other language are taken, and is in some state at each moment of discrete time. Graphically, an abstract automaton is presented in Fig.

Words of the input language can be represented by symbols of the set X=(x 1 ,x 2 ,...x n ), which is called input alphabet, and the words of the output language are symbols of the set Y=(y 1 ,y 2 ,...y p ), which is called output alphabet. The set of states of the automaton S=(s 1 ,s 2 ,...s m ) is called alphabet of states.


Concept machine state is used to describe systems whose output signals depend not only on the input signals at a given time, but also on some previous history, i.e. signals that were previously received at the system inputs. Therefore, digital automata refer to sequential circuits, which, as already noted, have memory. The concept of state of an automaton corresponds to some memory of the past, so the introduction of this concept allows time to be eliminated as an explicit variable and outputs to be expressed as a function of states and inputs.

The operation of an abstract automaton should be considered in relation to specific time intervals, because each discrete interval t will correspond to its output signal y(t). Consequently, the operation of the machine is considered through discrete time intervals of finite duration. In the abstract theory of digital automata, it is believed that input signals act on a synchronous automaton at the start of each i- that interval (quantum) of time allocated by the corresponding synchronization pulse (cycle), and the change in the internal states of the machine occurs in the time intervals between adjacent synchronization pulses, when there is no influence of input signals.

The concept of “state” is used to establish the functional dependence of the symbols and/or words of the output language generated by the machine on the symbols and/or words of the input language when the machine implements a given algorithm. For each state of the automaton sОS and for each symbol xОX at the moment of discrete time [t], the symbol yОY is generated at the output of the device. This dependence is determined by the output function of the automaton j. For each current state of the automaton sОS and for each symbol xОX at the moment of discrete time [t], the automaton goes to the next state sОS. This dependence is determined by the transition function of the automaton y. The operation of the automaton consists of generating two sequences: a sequence of the next states of the automaton (s 1[ s 2 s 3 ...) and a sequence of output symbols (y 1 y 2 y 3 ...), which for the sequence of symbols (x 1 x 2 x 3...) unfold at moments of discrete time t = 1,2,3,.... In rectangular brackets indicate moments of discrete time, which are otherwise called clock cycles, in parentheses - sequences of characters of the alphabets X, Y and S.

So, the mathematical model of a finite automaton is a three-basic algebra, the carriers of which are three sets X, Y and S, and the operations are two functions j and y.