Automata theory

Definition of an automaton and its varieties. Tables and graphs of transitions and exits. Subautomatons. Reduced automaton theorem

Operations with machines

Convert a Mealy Machine to a Moore Machine and a Moore Machine to a Mealy Machine. Equivalence of automata. Distinguishability of states of automata. Minimization of automata. Synthesis of automata. Recognizing automata

Automatic - a system of mechanisms, devices, in which the processes of obtaining, converting, transferring energy, materials, information are fully automated. The term "automatic" 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, an automaton is understood to be a very real device, for example, a telephone booth, a vending machine, etc. In this case, of course, 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 signals, it is useful to define CA as a system that can receive input signals, under their influence, move from one state to another, save it until the next input signal arrives, and issue output signals.

The CA is considered finite if the sets of input signals X, states S and output signals Y are finite. A finite automaton can be associated with a device such as a computer. The computer processes the 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. those data that are stored in the computer's memory, for example, the results of previous calculations, calculation programs.

The work of the CA 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 any language, one output channel, from which sequences of symbols of any other language are taken, and which is in any state at each moment of discrete time. Graphically, the abstract automaton is shown in fig.

The 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 state alphabet.

concept state of the machine is used to describe systems whose output signals depend not only on input signals at a given time, but also on some prehistory, i.e. signals that came to the inputs of the system earlier. Consequently, digital automata belong to sequential circuits, which, as already noted, have memory. The concept of the state of an automaton corresponds to some memory of the past, so the introduction of this concept allows eliminating time as an explicit variable and expressing output signals as a function of states and input signals.

The operation of an abstract automaton should be considered in relation to specific time intervals, since each discrete interval t will match its output y(t). Consequently, the functioning of the automaton is considered through discrete time intervals of finite duration. In the abstract theory of digital automata, it is considered that the input signals act on the synchronous automaton at the start of each i-th interval (quantum) of time allocated by the corresponding clock pulse (cycle), and the change in the internal states of the automaton occurs in the time intervals between adjacent clock 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 automaton on the symbols and/or words of the input language when the automaton implements the 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 switches to the next state sОS. This dependence is determined by the transition function of the automaton y. The functioning of the automaton consists in generating two sequences: a sequence of successive 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 cycles, in parentheses - sequences of symbols 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.

In this article, the term “state machine” refers to an algorithm that can be in one of a small number of states. "State" is a certain condition that defines a given relationship of input and output signals, as well as input signals and subsequent states. The smart reader will immediately note that the state machines described in this article are Mealy machines. A Mealy machine is a finite state machine where the outputs are functions of the current state and the input, in contrast to the Moore machine where the outputs are only functions of the state. In both cases, the subsequent state is a function of the current state and the input signal.

Consider an example of a simple finite state machine. Imagine that in a text string you need to recognize the character sequence "//". Figure 1 shows how this is done using a state machine. The first occurrence of the slash does not produce an output signal, but it causes the automaton to enter the second state. If the automaton does not find a slash in the second state, it returns to the first one, since it needs 2 slashes in a row. If the second slash is found, the automaton issues a “ready” signal.

Find out what the customer needs.

Draw a State Transition Diagram

Code the "skeleton" of the state machine without detailing the transition operations.

Make sure the transitions are working properly.

Specify the details of the transitions.

Take a test.

State machine example

Let's consider a more interesting example of a finite state machine - a program that controls the retraction and extension of the aircraft landing gear. Although in most aircraft this procedure is performed using an electro-hydraulic control mechanism (simply because there is no computer on board), in some cases, such as unmanned aerial vehicles, it is worth using software control.

First, let's deal with the equipment. The landing gear of the aircraft consists of the front landing gear, the main left landing gear and the main right landing gear. They are driven by a hydraulic mechanism. An electrically driven hydraulic pump supplies pressure to the power actuator. Using the software, the pump is turned on or off. The computer adjusts the position of the directional valve - "down" or "up" to allow pressure to raise or lower the chassis. Each of the landing gear legs has a limit switch: one of them is closed if the landing gear is raised, the other - if it is fixed in the "down" position. To determine if the aircraft is on the ground, the limit switch on the nose gear stay closes if the weight of the aircraft is on the nose gear. The pilot's controls consist of an upper/lower landing gear arm and three lights (one for each leg) that can be turned off, green (down position) or red (transition position).

And now let's move on to the development of a finite state machine. The first and most difficult step is to understand the real expectations of the customer. One of the advantages of a state machine is that it forces the programmer to think through all possible cases and, as a result, receive all the required information from the customer. Why do I consider this the most difficult stage? And how many times have you been given a task description like this: don't retract the landing gear if the plane is on the ground.

Of course, this is important, but the customer believes that this is where it all ends. What about other cases? Is it enough to retract the landing gear at the moment when the plane takes off from the ground? What if the plane bounces over a bump on the runway? What if the pilot moves the gearshift lever to the "up" position during parking and, as a result, begins to take off? Should the chassis rise in this case?

One of the benefits of thinking in terms of a state machine is that you can quickly draw a state transition diagram on a projection board, right in front of the customer, and go through the process with them. The following designation of the state transition is accepted: “the event that caused the transition” / “output signal as a result of the transition”. If we had developed only what the customer originally asked for (“do not retract the landing gear if the aircraft is on the ground”), then we would have received the machine shown in Figure 2.

When drawing up a state transition diagram (or any other algorithm), keep the following in mind:

Computers are very fast compared to mechanical hardware.

The mechanical engineer who explains what needs to be done may not know as much about computers and algorithms as you do. And this is also a positive point, otherwise, you would not be needed!

How will your program behave if a mechanical or electrical part breaks?

A state machine based on what the customer really wants is shown in Figure 3. Here we want to prevent the aircraft landing gear from retracting until it is definitely in the air. To do this, after opening the landing switch, the machine waits for a few seconds. We also want to respond to the rising edge of the pilot's lever rather than the level, which will avoid problems if someone moves the lever while the plane is parked. Retracting or extending the landing gear takes a few seconds, and we must be prepared for the situation that the pilot, during this operation, changes his mind and moves the lever in the opposite direction. Also note that if the plane lands again while we are in the "Waiting for takeoff" state, the timer will restart and the landing gear will only retract if the plane has been in the air for 2 seconds.

State Machine Implementation

Listing 1 is my implementation of the state machine shown in Figure 3. Let's discuss some of the details of the code.

/*listing 1*/

typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) State_Type;

/*This array contains pointers to functions to be called in certain states*/

void(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InitializeLdgGearSM();

/* The heart of the automaton is this endless loop. Function corresponding

Current state, called once per iteration */

while (1) {

state_table();

DecrementTimer();

void InitializeLdgGearSM( void )

curr_state = GEAR_DOWN;

/*Stop hardware, turn off lights, etc.*/

void GearDown( void )

/* Go to the waiting state if the plane

Not on the ground and a command was received to raise the chassis * /

if((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

void RaisingGear( void )

if((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*If the pilot has changed his mind, go to the landing gear down state*/

if(gear_lever == DOWN) (

curr_state = LOWERING_GEAR;

void GearUp( void )

/*if the pilot moved the lever to the "down" position,

Go to the state of "lowering the landing gear" */

if(gear_lever == DOWN) (

curr_state = LOWERING_GEAR;

void WtgForTakeoff( void )

/* Wait before raising the chassis. */

if(timer<= 0.0) {

curr_state = RAISING_GEAR;

/*If we touched again or the pilot changed his mind, start all over again*/

if((squat_switch == DOWN) || (gear_lever == DOWN)) (

curr_state = GEAR_DOWN;

/* Don't want to require that he toggle the lever again

This was just a bounce.*/

prev_gear_lever = DOWN;

void LoweringGear( void )

if(gear_lever == UP) (

curr_state = RAISING_GEAR;

if((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

First, you may notice that the functionality of each state is implemented by a separate C function. Of course, it would be possible to implement an automaton using a switch statement with a separate case for each state, but this can lead to a very long function (10-20 lines of code per 1 state for each of the 20-30 states). It can also lead to errors if you change the code at the final stages of testing. You may have never forgotten the break statement at the end of a case, but I have had such cases. The code of one state will never get into the code of another if you have a separate function for each state.

To avoid using a switch statement, I use an array of pointers to the state functions, and declare the variable used as the index of the array to be of type enum.

For simplicity, the I/O hardware responsible for reading the state of switches, turning pumps on and off, etc., is represented as simple variables. It is assumed that these variables are "magic addresses" associated with the equipment by invisible means.

Another obvious thing is that at this point the code does not play a special role. It just goes from one state to another. This is an important intermediate step and should not be ignored. By the way, it would be nice to add print statements enclosed between conditional compilation directives (#ifdef DEBUG .. #endif) that would print the current state and values ​​of the input signals.

The key to success lies in the code that causes the state transition, i.e. determines that input has occurred.

If the code correctly passes through all states, the next step is to write the "stuffing" of the code, that is, exactly what produces the output signal. Remember that each transition has an input signal (the event that triggered it) and an output signal (hardware I/O device, as in our example). It is often useful to capture this in the form of a state transition table.

The state transition table has one row per state transition.

When coding a state machine, try to keep it strong - a strong correspondence between the customer's requirements and the code. It may be necessary to hide hardware details in another function layer, for example, to make the state machine code look like a state transition table and a state transition diagram as closely as possible. This symmetry helps prevent errors and explains why state machines are such an important part of the embedded programmer's arsenal. Of course, you could achieve the same effect with checkboxes and an infinite number of nested if statements, but it would be very difficult to track the code and compare it with the wishes of the customer.

The code snippet in Listing 2 extends the RaisingGear() function. Note that the code for the RaisingGear() function tends to mirror the 2 rows of the transition table for the Raising Gear state.

void RaisingGear( void )

/*After all the switches are up, go to the "chassis up" state*/

if((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor=OFF;

gear_lights = EXTINGUISH;

curr_state = GEAR_UP;

/*If the pilot changes his mind, start landing gear retraction*/

if(gear_lever == DOWN) (

pump_direction = DOWN;

curr_state = GEAR_LOWERING;

Remember to avoid hidden states. Hidden state appears when, out of laziness, you try to add a conditional substate instead of adding a concrete state. For example, if your code processes the same input in different ways (i.e. initiates different state transitions) depending on the mode, then it is a hidden state. In this case, I would wonder if this state should not be split into two? The use of hidden states negates all the benefits of using a state machine.

As a practice, you can extend the state machine we just looked at by adding a timeout to the retract or extend cycle of the chassis, as the mechanical engineer does not want the hydraulic pump to run longer than 60 seconds. If the cycle ends, the pilot must be alerted by the switching of the green and red lights and must be able to move the lever again to try again. You can also ask a hypothetical mechanical engineer how the pump is affected by reversing direction while it is running, because it happens 2 times the pilot changes his mind. Of course, the mechanic will say that it is negative. Then how would you change the state machine to stop the pump quickly when changing direction?

State Machine Testing

The beauty of coding algorithms as finite state machines is that the test plan almost automatically writes itself. All you have to do is go through each state transition. I usually do this with a marker in hand, crossing out the arrows on the state transition diagram as they pass the test. This is a good way to avoid "hidden states" - they are missed more often in tests than specific states.

This requires considerable patience and a lot of coffee, as even a medium sized state machine can have up to 100 different transitions. By the way, the number of hops is a great way to measure the complexity of a system. The latter is determined by the requirements of the customer, and the state machine makes the scope of testing obvious. With a less organized approach, the amount of testing required can be just as impressive, but you just don't know about it.

It is very convenient to use print statements in the code that display the current state, the values ​​of input and output signals. This allows you to easily observe what the "Golden Rule of Software Testing" expresses: test that the program does what it is intended to do, and also that it does nothing extra. In other words, are you only getting the outputs you expect, and what else is going on besides that? Are there any "hard" state transitions, i.e. states that randomly go through, just for one iteration of the loop? Do the outputs change when you don't expect them to? Ideally, the output of your printfs should closely resemble a state transition table.

Finally - and this applies to any embedded software, not just state machine based software - be very careful the first time you run the software on real hardware. It's very easy to get the polarity wrong - "Oops, I thought '1' meant to raise the chassis and '0' meant to lower it." In many cases, my hardware assistant used a temporary "chicken switch" to protect valuable components until he was sure that my software was moving things in the right direction.

launch

When all customer requirements are met, I can launch a state machine of this complexity in a couple of days. Almost always automata do what I want. The most difficult thing is, of course, to understand exactly what the customer wants and make sure that the customer himself knows what he wants. The latter takes much longer!

Martin Gomez is a programmer at the Applied Physics Laboratory at Johns Hopkins University. Engaged in the development of software for the flight of research spacecraft. He has worked in the field of embedded systems development for 17 years. Martin holds a Bachelor of Science in Aerospace Engineering and an MS in Electrical Engineering from Cornell University.

One of the criteria for the complexity of a finite automaton is the number of its states. The smaller this number, the simpler the discrete device that implements this automaton. Therefore, one of the important problems in 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, then 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.

Here are some examples of finite automata.

Example 1. Delay element (memory element).

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

Assume that the input and hence the 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 the memory element at the moment is understood. In this way q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Let's set the delay element by the table, where but 1 =0, but 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 by a system of Boolean functions, we use the automaton table and the above algorithm. In this case, encoding is not necessary, since the input and output alphabets and states are already encoded.

Let's pay attention to the fact that m=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 rows 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 fed to the inputs of the adder X 1 and x 2, starting with the least significant digits. At the output, a sequence is formed corresponding to the number entry X 1 +x 2 in the binary system of calculation (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 transfer when adding the corresponding bits of numbers X 1 and x 2. If during the addition of some digits a carry is formed, then we will assume that the adder has passed into the state q one . If there is no carry, we will assume that the adder is in the state q 0 .

The adder is given 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. five.

Note that the input and output characters are already encoded. We encode the states as follows:  (q 0)=0,  (q 1)=1. Therefore, the sequential adder is given 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 the binary system. This device works as follows. At the input of the device sequentially, starting from the highest, the digits of numbers are fed X 1 and x 2. These ranks are compared. If the bits match, the output signal 0 is generated at the output of the circuit, otherwise the signal 1 appears at the output. It is clear that the appearance of 1 in the output sequence means that the compared numbers X 1 and x 2 different. If the output sequence is zero and its length matches the number of digits of the compared numbers, 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 bits. In this case, the machine remains in the same state. If at the next moment the compared digits are different, then the automaton will go to a new state q 1 and remains in it, since it 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 comparison scheme for equality is shown in fig. 6.

We will encode the states as follows:  (q 0)=0,  (q 1)=1. The automaton will be given two functions.

x 1	x 2	z

Example 4. Inequality comparison scheme.

The inequality comparison circuit is a device that allows you to find out whether the compared 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 ), i.e x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1 if x 1 (t )<x 2 (t ), i.e x 1 (t )=0, x 2 (t )=1.

Thus, when applying to the input of the comparison circuit for 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 highest 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 one is different from zero, the pair has the form , () then 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 schema state is defined as follows. We assume that at the initial time t =1 the machine is in the state q 1 . If the compared digits of numbers X 1 And X 2 match, then the machine remains in this state. Note that the signal 00 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, a signal 01 (10) will appear at the output. In the future, when submitting the remaining digits of numbers X 1 And X 2 to the inputs of the automaton, the automaton will remain in the state q 2 (q 3) and generate output symbol 10 (01). It follows from the above 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 3 encode:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Therefore, this scheme can be defined by a system consisting of four Boolean functions that depend on four variables. These functions are partially defined and given by the 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 equal to 1.

Today we will talk about machine guns, but by no means those that are held in the hands of the soldiers of the Russian army. We will talk about such an interesting style of programming microcontrollers as automatic programming. More precisely, this is not even a programming style, but a whole concept, thanks to which a microcontroller programmer can make his life much easier. Due to which many tasks presented to the programmer are solved much easier and simpler, relieving the programmer from a headache. By the way, automatic programming is often called SWITCH technology.

I want to note that the stimulus for writing this post was series of articles about SWITCH technology Vladimir Tatarchevskiy. The series of articles is called "Application of SWITCH technology in the development of application software for microcontrollers" So in this article I will try for the most part to give an example of a working code and its description.

By the way, I have planned a series of articles on programming, in which I will consider in detail the programming techniques for ABP microcontrollers, do not miss…. Well let's go!

The program sequentially executes the commands laid down by the programmer. For an ordinary computer program, it is completely normal when the program has completed and stopped its execution, while displaying the results of its work on the monitor.

A microcontroller program cannot simply end its execution. Imagine that you have turned on the player or tape recorder. You have pressed the power button, selected the desired song, and enjoy the music. However, when the music stopped wagging your eardrum, the player freezes and does not react in any way to pressing the buttons, and even more so to your dancing with a tambourine.

And what is this? Everything is fine - the controller, the one in the depths of your player, just finished executing its program. Here you can see how uncomfortable it turns out.

So from here we conclude that the program for the microcontroller simply should not stop. In essence, it should be an infinite loop - only in this case our player would work correctly. Next, I will show you what are the designs of program code for microcontrollers, these are not even designs, but some programming styles.

Programming styles.

“Programming styles” sounds kind of incomprehensible, but oh well. What do I want to say with this? Let's imagine that a person has never done programming before, that is, in general, a complete dummy.

This person has read many books on programming, learned all the basic constructs of the language.He collected information bit by bit, since now access to information is unlimited. All this is good, but what will his first programs look like? It seems to me that he will not philosophize, but will follow the path from simple to complex.

So these styles are steps leading from a simple level to a more complex one, but at the same time more effective.

At first, I did not think about any design features of the program. I just formed the logic of the program - I drew a flowchart and wrote the code. From what constantly came across a rake. But this was the first time when I didn’t take a steam bath and used the “simple looping” style, then I began to use interrupts, then there were automata and off we went ...

1. Simple looping. The program in this case loops without any intricacies, and this has its pros and cons. Plus only in the simplicity of the approach, you do not need to invent cunning designs, you write as you think (gradually digging your own grave).

Void main(void) ( initial_AL(); //initialization of the periphery while(1) ( Leds_BLINK(); //function of the LED flasher signal_on(); //function of turning on the signal signal_off(); //function of turning off the signal l=button( ); // variable responsible for pressing the buttons switch(l) // Depending on the value of the variable, one or another action is performed ( case 1: ( Deistvie1 (); // Instead of a function, there can be a conditional operator Deistvie2 (); // or else several branches switch case Deistvie3(); Deistvie4(); Deistvie5(); ); case 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ); . . . . . . . . ) ) )

The work point of the program moves in order. In this case, all actions, conditions and cycles are sequentially executed. The code starts to slow down, you have to insert a lot of extra conditions, thereby complicating perception.

All this greatly confuses the program, making a tangle of conditions out of the code. As a result, this code cannot be added or taken away, it becomes like a monolithic piece. Of course, when the volume is not large, the code can be modified, but the further the more difficult.

With this approach, I wrote several programs, they were not large and quite working, but the visibility left much to be desired. To add some new condition, I had to shovel the whole code, because everything was tied up. This gave rise to many errors and headaches. The compiler swore as soon as it could, debugging such a program turned into hell.

2. Cycle + interrupts.

You can partially resolve the infinite braking cycle using interrupts. Interrupts help to break out of a vicious circle, help not to miss an important event, add additional functionality (interrupts from timers, external interrupts).

Let's say you can hang up the processing of buttons, or tracking an important event on an interrupt. As a result, the program becomes more visual but no less confusing.

Unfortunately, the interrupt will not save you from the mess that the program turns into. It will not be possible to divide into parts what is a single whole.

3. Automatic programming.

So we get to the main topic of this article. Programming in finite state machines saves the program from the shortcomings inherent in the first two examples. The program becomes simpler, it is easy to modify.

A program written in automaton style is similar to a switch that, depending on the conditions, switches to one state or another. The number of states is initially known to the programmer.

Roughly, it's like a light switch. There are two states on and off, and two conditions on and off. Well, first things first.

Implementation of multitasking in switch technology.

The microcontroller is able to control the load, blink LEDs, track keystrokes and much more. But how to do all this at the same time? There are many solutions to this issue. The simplest of these I already mentioned is the use of interrupts.

During the program, when an interrupt occurs, the controller is distracted from the execution of the program code and briefly executes another piece of the program for which the interrupt is responsible. The interrupt will work, then the working point of the program will continue from the place from which the controller was interrupted by the interrupt (the word itself indicates that the controller is interrupted).

Another way to implement multitasking is through the use of operating systems. Yes, small OSes have already begun to appear, which can be used on a low-power controller. But often this method turns out to be somewhat redundant. After all, why waste controller resources with unnecessary work when it is quite possible to get by with little bloodshed.

In programs written using switch technology, such an “illusion” of multitasking is obtained thanks to the messaging system. I wrote "illusion" because it really is, because the program physically cannot execute different parts of the code at the same time. I will talk about the messaging system a little further.

Messaging system.

You can destroy numerous processes and create the illusion of multitasking using the messaging system.

Let's say we need a program in which the LED is switched. Here we have two machines, let's call them LEDON - the machine responsible for turning on the LED and the LEDOFF machine - the machine responsible for turning off the LED.

Each of the automata has two states, that is, the automaton can be in an active state or an inactive state, like a knife switch is either on or off.

When one machine is activated, the LED lights up, when the other machine is activated, the LED goes out. Consider a small example:

Int main(void) ( INIT_PEREF(); //initialization of peripherals (LEDs) InitGTimers(); //initialization of timers InitMessages(); //initialization of the message processing mechanism InitLEDON(); //initialization of the LEDON automaton InitLEDOFF(); // initialization of the LEDOFF automaton SendMessage(MSG_LEDON_ACTIVATE); //activate the LEDON automaton sei(); //Enable interrupts //Program main loop while(1) ( ProcessLEDON(); //iteration of the LEDON automaton ProcessLEDOFF(); //iteration of the LEDOFF automaton ProcessMessages (); //message processing ); )

In lines 3-7, various initializations occur, so we are not particularly interested in this now. But then the following happens: before starting the main loop (while (1)), we send a message to the automaton

SendMessage(MSG_LEDON_ACTIVATE)

responsible for lighting the LED. Without this small step, our hurdy-gurdy will not work. Next, the main infinite while loop does the bulk of the work.

Small digression:

The message has three states. Namely, the message state can be inactive, set but inactive, and active.

It turns out that the message was initially inactive, when we sent the message, it received the status "installed but inactive". And this gives us the following. When the program is executed sequentially, the LEDON automaton does not receive a message. An idle iteration of the LEDON automaton occurs, in which the message simply cannot be received. Since the message has a status of "installed but inactive", the program continues its execution.

After all automata are idle, the queue reaches the ProcessMessages() function. This function is always placed at the end of the loop, after all automaton iterations have been completed. The ProcessMessages() function simply changes the message from the "set but inactive" state to the "active" state.

When the infinite loop completes the second round, the picture is already completely different. The iteration of the ProcessLEDON automaton will no longer be idle. The machine will be able to receive the message, switch to the lit state and also send the message in turn. It will be addressed to the LEDOFF automaton and the life cycle of the message will be repeated.

I want to note that messages that have the "active" state are destroyed when they meet with the ProcessMessages function. Therefore, a message can only be received by one automaton. There is another type of messages - these are broadcast messages, but I will not consider them, they are also well covered in Tatarchevskiy's articles.

Timers

With proper messaging, we can control the order in which state machines work, but we can't do without messages alone.

You may have noticed that the previous example code snippet will not work as intended. The machines will exchange messages, the LEDs will switch, but we will not see this. We will see only a dimly lit LED.

This is because we did not think over the competent processing of delays. After all, it is not enough for us to alternately turn on and off the LEDs, the LED must linger in each state, for example, for a second.

The algorithm will be as follows:

You can click to enlarge

I forgot to add on this block diagram that when the timer ticks, of course, an action is performed - lighting the LED or turning it off.

1. We enter the state by receiving a message.

2. We check the timer/counter readings, if it ticks, then we perform the action, otherwise we just send a message to ourselves.

3. We send a message to the next automaton.

4. Exit

In the next entry, everything is repeated.

SWITCH technology program. Three steps.

And let's write a program in finite automata and for this we will need to do just three simple steps. The program will be simple, but it is worth starting with simple things. A program with a switching LED is suitable for us. This is a very good example, so let's not invent anything new.

I will write the program in the C language, but this does not mean at all that in finite automata you need to write only in C, it is quite possible to use any other programming language.

The program will be modular and therefore will be divided into several files. Our modules will be:

• The program's main loop module contains the files leds_blink.c, HAL.c, HAL.h
• Timer module contains files timers.c, timers.h
• Message processing module contains files messages.c, messages.h
  
• Machine module 1 contains ledon.c, ledon.h files
• Machine module 2 contains ledoff.c files, ledoff .h

Step 1.

We create a project and immediately connect the files of our static modules to it: timers.c, timers.h, messages.c, messages.h.

The file leds_blink.c of the module of the main cycle of the program.

#include "hal.h" #include "messages.h" //message processing module #include "timers.h" //timers module //Timer interrupts //############# ################################################### ############################# ISR(TIMER0_OVF_vect) // Interrupt vector transition (T0 counter timer overflow) ( ProcessTimers(); //Timer interrupt handler) //######################################## ################################################### int main(void) ( INIT_PEREF(); //initialization of the periphery (LEDs) InitGTimers(); //initialization of the timers InitMessages(); //initialization of the message processing mechanism InitLEDON(); //initialization of the LEDON automaton InitLEDOFF(); StartGTimer( TIMER_SEK); //Start the timer SendMessage(MSG_LEDON_ACTIVATE); //activate the FSM1 automaton sei(); //Enable interrupts //Program main loop while(1) ( ProcessLEDON(); //iterate the LEDON automaton ProcessLEDOFF(); ProcessMessages( ); //message processing ); )

In the first lines, the remaining modules are connected to the main program. Here we see that the timer module and the message processing module are connected. Next in the program is the overflow interrupt vector.

From the line int main (void) we can say the main program begins. And it begins with the initialization of everything and everything. Here we initialize the periphery, that is, we set the initial values ​​​​to the input / output ports of the comparator and all other contents of the controller. All this is done by the INIT_PEREF function, we run it here, although its main body is in the hal.c file.

Next, we see the initialization of timers, the message processing module, and the initialization of automata. Here, these functions are also simply launched, although the functions themselves are written in the files of their modules. See how convenient. The main text of the program remains easy to read and is not cluttered with redundant code that breaks your leg.

The main initializations are over, now we need to start the main loop. To do this, we send the start message, and besides, we start our watch - we start the timer.

StartGTimer(TIMER_SEK); //Start timer SendMessage(MSG_LEDON_ACTIVATE); //activate FSM1 machine

And the main loop, as I said, looks very simple. We write down the functions of all automata, we just write them in a column, without following the order. These functions are automaton handlers and are located in automaton modules. The function of the message processing module completes this automaton pyramid. Of course, I already told this earlier when I dealt with the messaging system. Now you can see how two more files of the module of the main program loop look like

Hal.h is the header file of the program's main loop module.

#ifndef HAL_h #define HAL_h #include #include //Standard library including interrupts #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

As you can see, this file does not inherently contain a single line of executable code - these are all macro substitutions and library connections. Having this file just makes life very good, it improves visibility.

But the Hal.c file is already an executable file, and as I already mentioned, it contains various peripheral initializations.

#include "hal.h" void INIT_PEREF(void) ( //Initialize I/O ports //############################ ################################################### ##### Komparator = ViklKomparator; //comparator initialization - turn off DDRD = 1<

Well, I showed the module of the main cycle of the program, now we have to take the last step, we need to write the modules of the automata themselves.

Step 3

It remains for us to write the modules of finite automata, in our case, the LEDON automaton and the LEDOFF automaton. To begin with, I will give the text of the program for the machine that lights the LED, the ledon.c file.

//file ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //state variable void InitLEDON(void) ( ledon_state=0; //here you can initialize other automaton variables if they exist ) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //inactive state if(GetMessage (MSG_LEDON_ACTIVATE)) //if there is a message, it will be accepted ( //and the timer will be checked if(GetGTimer(TIMER_SEK)==one_sek) //if the timer has set 1s, then execute ( StopGTimer(TIMER_SEK); PORTD = 1<

Here, in the first lines, as always, libraries are connected and variables are declared. Next, we have already gone the functions with which we have already met. This is the initialization function of the InitLEDON automaton and the function of the ProcessLEDON automaton handler itself.

In the body of the handler, the functions from the timer module and the message module are already being processed. And the logic of the automaton itself is based on the switch-case design. And here you can see that the automaton handler can also be complicated by adding a few case switches.

The header file for the automaton would be even simpler:

//fsm1 file #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Here we connect the link file hal.h and also specify the prototypes of the functions.

The file responsible for turning off the LED will look almost the same only in mirror image, so I won’t display it here - reluctance 🙂

You can download all project files here at this link ====>>> LINK.

Here are just three steps and our program has acquired a finished look, which means that my mission for today is over and it's time to wrap up. It seems to me that the information given in this article will be very useful for you. But it will bring real benefit only when you put this knowledge into practice.

By the way, I have planned a number of interesting projects that will be especially interesting, so be sure to subscribe for new articles . I also plan to send out additional materials, so many people already subscribe through the main page of the site. You can subscribe here too.

Well, now I really have everything, so I wish you good luck, good mood and see you again.

N/A Vladimir Vasiliev

A 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, getting a neat solution without writing cumbersome and complex code. In this article, we will cover 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 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 computational model based on a hypothetical state machine. Only one state can be active at a time. Therefore, to perform any action, the machine must change its state.

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

A finite automaton can be represented as a graph, the vertices of which are the states, and the edges are the 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 automaton will change the state from "wander" to the state "attack", provided that the player is nearby.

Scheduling 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 into 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". The same state will remain active until our ant gets to the anthill. After that, the state changes back to "find leaf".

If the "find leaf" state is active, but the mouse cursor is next to the ant, then the state changes to "run away". As soon as 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 out of the house, the ant will not be afraid of the mouse cursor. Why? And because there is no corresponding transition.

Implementing a simple state machine

A 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 automaton 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 game frame. And he, 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 have to belong to the FSM class - this makes our class more universal.

Using a state machine

Let's implement 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 looking for a leaf. brain. setState(findLeaf); ) /** * State "findLeaf". * Makes the ant look for leaves. */ public function findLeaf( ) :void ( ) /** * The "goHome" state * Causes the ant to go into the anthill */ public function goHome() :void ( ) /** * The "runAway" state * Causes the ant to run away from the mouse cursor * / 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( ); // Apply velocity to the ant's movement. moveBasedOnVelocity(); ) (...) )

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

Below is the implementation of each of the methods, 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); } }

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

Public function goHome() :void ( // Moves the ant to the home 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 - used when dodging 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 around? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // No, it's already far away. It's time to go back to finding leaves. brain.setState(findLeaf); ) )

FSM Improvement: Stack Based Automaton

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

Seems like a trivial change. No, such a 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 kind 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 state machine based on the stack:

Implementation of a stack-based FSM

Such a finite 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 will 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 new state to the top of the stack) and popState() (removing state from the top of the stack).

Using the stack-based FSM

It is important to note that when using a stack-based state machine, each state is responsible for removing itself from the stack when not needed. For example, the attack() state should itself 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 looking for a leaf brain.pushState( findLeaf); (...) ) /** * State "findLeaf". * Makes the ant look 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 return to the search for leaves. brain.popState(); ) ) (...) )

Output

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

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