Finite state machines. Finite state machines: converters and recognizers How to program a finite machine

Twitter

Lecture 5.

Deterministic Finite State Machines

Discrete-deterministic models ( F-scheme)

Basic relationships. Let us consider the features of the discrete-deterministic approach using the example of using automata theory as a mathematical apparatus. The system is represented in the form of an automaton as a device with input and output signals, processing discrete information and changing its internal states only at acceptable times. State machine is an automaton whose sets of internal states, input and output signals are finite sets.

Abstractly, a finite automata can be represented as a mathematical circuit ( F-diagram), characterized by six elements: a finite set X input signals (input alphabet); finite set Y output signals (output alphabet); finite set Z internal states (internal alphabet or alphabet of states); initial state z 0 , z 0 Î Z; transition function j( z, x); output function y( z, x). Automaton specified F-scheme: F = á Z, X, Y, y, j, z 0 ñ, operates in discrete time, the moments of which are clock cycles, each of which corresponds to constant values of the input and output signals and internal states. Let us denote the state, as well as the input and output signals corresponding to t-th beat at t= 0, 1, 2, …, through z(t), x(t), y(t). Moreover, according to the condition z(0) = z 0 , a z(t)Î Z, x(t)Î X, y(t)Î Y.

Example. The simplest automaton of lion behavior.

Input alphabet: "antelope", "hunter".

Internal states: “full”, “hungry”.

Output alphabet: "eat", "sleep", "run away"

Transition table:

An abstract state machine has one input and one output channel. At every moment t= 0, 1, 2, … discrete time F- the machine is in a certain state z(t) from many Z states of the machine, and at the initial moment of time t= 0 it is always in the initial state z(0) = z 0 . In the moment t, being able z(t), the machine is capable of receiving a signal on the input channel x(t)Î X and output a signal on the output channel y(t) = y[ z(t), x(t)], passing into state z( t+1) = j[ z(t), x(t)], z(t)Î Z, y(t)Î Y. An abstract finite machine implements some mapping of a set of words of the input alphabet X for many words of the output alphabet Y. In other words, if the input of a finite state machine set to the initial state z 0 , supply letters of the input alphabet in some sequence x(0), x(1), x(2), ..., i.e. input word, then the letters of the output alphabet will appear sequentially at the output of the machine y(0), y(1), y(2), ..., forming the output word.

Thus, the operation of the finite state machine occurs according to the following scheme: in each t th cycle to the input of the machine, which is in the state z(t), some signal is given x(t), to which it reacts with a transition ( t+1)-th cycle to a new state z(t+1) and producing some output signal. The above can be described by the following equations: for F-automaton of the first kind, also called Automatic Miles,

z(t+1) = j[ z(t), x(t)], t= 0, 1, 2, …; (2.15)

y(t) = y[ z(t), x(t)], t= 0, 1, 2, …; (2.16)

For F-automatic machine of the second type

z(t+1) = j[ z(t), x(t)], t= 0, 1, 2, …; (2.17)

y(t) = y[ z(t), x(t – 1)], t= 1, 2, 3,…. (2.18)

Automaton of the second kind, for which

y(t) = y[ z(t)], t= 0, 1, 2, …, (2.19)

those. the output function does not depend on the input variable x(t), called Moore machine gun.

Thus, equations (2.15)-(2.19), completely defining
F-automaton are a special case of equations (2.3) and (2.4), when
system S– deterministic and its only input receives a discrete signal X.

Based on the number of states, finite state machines are distinguished between finite state machines with and without memory. Automata with memory have more than one state, while automata without memory (combination or logical circuits) have only one state. Moreover, according to (2.16), the operation of the combinational circuit is that it assigns each input signal x(t) defined output signal y(t), i.e. implements a logical function of the form

y(t) = y[ x(t)], t= 0, 1, 2, … .

This function is called Boolean if the alphabet X And Y, to which the signal values belong x And y, consist of two letters.

Based on the nature of discrete time counting, finite state machines are divided into synchronous and asynchronous. In synchronous F In automatic machines, the moments of time at which the machine “reads” the input signals are determined by forced synchronizing signals. After the next synchronizing signal, taking into account the “read” and in accordance with equations (2.15)-(2.19), a transition to a new state occurs and a signal is issued at the output, after which the machine can perceive the next value of the input signal. Thus, the response of the machine to each value of the input signal ends in one clock cycle, the duration of which is determined by the interval between adjacent synchronizing signals. Asynchronous F-the machine reads the input signal continuously and therefore reacts to a sufficiently long input signal of constant value x, it can, as follows from (2.15)-(2.19), change its state several times, producing the corresponding number of output signals, until it becomes stable, which can no longer be changed by a given input signal.

Possible applications F-scheme. To set the end F-automaton, it is necessary to describe all elements of the set F= <Z, X, Y, y, j, z 0 >, i.e. input, internal and output alphabets, as well as functions of transitions and outputs, and among the many states it is necessary to select the state z 0 in which the machine is in the state t= 0. There are several ways to specify work F-automata, but the most commonly used are tabular, graphical and matrix ones.

In the tabular method, tables of transitions and outputs are specified, the rows of which correspond to the input signals of the machine, and the columns - its states. The first column on the left corresponds to the initial state z 0 . At intersection i th line and k the th column of the transition table contains the corresponding value j( z k, x i) transition functions, and in the output table - the corresponding value y( zk,x i) output functions. For F-Moore's automaton both tables can be combined.

Description of work F-A Mealy automaton with tables of transitions j and outputs y is illustrated in Table. 2.1, and the description F-Moore automaton – transition table (Table 2.2).

Table 2.1



Transitions
	j( z 0 , x 1)	j( z 1 , x 1)	j( z k,x 1)
	j( z 0 , x 2)	j( z 1 , x 2)	j( z k,x 2)

	j( z 0 , x i)	j( z 1 , x i)	j( z k,x i)
Exits
	y( z 0 , x 1)	y( z 1 , x 1)	y( z k, x 1)
	y( z 0 , x 2)	y( z 1 , x 2)	y( z k, x 2)

	y( z 0 , x i)	y( z 1 , x i)	y( z k, x i)

Table 2.2




j( z 0 , x 1)	j( z 1 , x 1)	j( z k, x 1)
j( z 0 , x 2)	j( z 1 , x 2)	j( z k, x 2)

j( z 0 , x i)	j( z 1 , x i)	j( z k, x i)

Examples of the tabular method of assignment F-automatic Mili F 1 are given in table. 2.3, and for F-Moore machine gun F 2 – in table. 2.4.

Table 2.3



Transitions


Exits

Table 2.4

When specifying a finite automaton graphically, the concept of a directed graph is used. The graph of an automaton is a set of vertices corresponding to various states of the automaton and connecting the vertices of the graph arcs corresponding to certain transitions of the automaton. If the input signal x k causes a state transition z i in a state z j, then on the automaton graph there is an arc connecting the vertex z i with top z j, denoted x k. In order to specify the output function, the arcs of the graph must be marked with the corresponding output signals. For Mili machines this marking is done as follows: if the input signal x k affects the state z i, then we get an arc emanating from z i and marked x k; this arc is additionally marked with an output signal y= y( z i, x k). For a Moore machine, a similar graph layout is as follows: if the input signal x k, acting on some state of the automaton, causes a transition to the state z j, then the arc directed to z i and marked x k, additionally celebrated as a day off
signal y= y( z j, x k).

In Fig. 2.4. A, b are given previously specified tables F-Mili machines F 1 and Moore F 2 respectively.

Rice. 2.4. Graphs of automata a – Mealy and b – Moore

With a matrix specification of a finite automaton, the connection matrix of the automaton is square WITH=||Withij||, rows correspond to initial states, and columns correspond to transition states. Element Withij = x k/y s, standing at the intersection
i th line and j the th column, in the case of the Mili machine corresponds to the input signal x k, causing a transition from the state z i in a state z j, and the output signal y s, issued during this transition. For machine Mili F 1, discussed above, the connection matrix has the form:

x 2 /y 1 – x 1 /y 1

C 1 = x 1 /y 1 – x 2 /y 2 .

x 1 /y 2 x 2 /y 1 –

For F-Moore automaton element Withij equal to the set of input signals at the transition ( z i ,z j), and the output is described by the vector of outputs

= y( z k) ,

i-th component of which is the output signal indicating the state z i.

For the above F-Moore machine gun F2 connection matrices and output vector have the form:

– x 1 – x 2 –at 1

– x 2 – – x 1 at 1

C 2 = – x 2 – – x 1 ; = y 3

x 2 – x 1 – –at 2

x 2 – x 1 – –at 3

For deterministic automata, the condition of unambiguous transitions is satisfied: an automaton that is in a certain state cannot transition to more than one state under the influence of any input signal. In relation to the graphical method of assignment F-of an automaton, this means that in the graph of an automaton, two or more edges marked by the same input signal cannot exit from any vertex. And in the matrix of connections of the machine WITH In each line, any input signal should not appear more than once.

Thus, the concept in the discrete-deterministic approach to studying the properties of objects using models is a mathematical abstraction, convenient for describing a wide class of processes of functioning of real objects in automated control systems. By using F- of an automaton, it is possible to describe objects that are characterized by the presence of discrete states, and the discrete nature of work in time - these are computer elements and nodes, control, regulation and control devices, time and spatial switching systems in information exchange technology, etc.

Example of modeling using finite state machines

An example of constructing a finite state machine (processor)

for recognizing and processing the recording of real numbers

At the input of the machine: a character string representing an unsigned real number.

At the output of the machine: a pair of integers: mantissa and exponent, or an error message if the number is written incorrectly.

Example.

1. 38.71 E - 42 → (3871, -44);

2. .9 E 21 → (9, 20);

3. 4.5.6 .9→ Error;

4. 3. E 4 → (3, 4);

5. 12 → (12, 0);

6. 1.2 → (12, -1).

In this example, we will show a sample for solving the problem of constructing a finite recognition machine and a processing processor. Let's break this process down into several stages.

1.Write down one or more examples characteristic chains based on which:

a) determine the input alphabet;

b) sign under the symbols of the state chains, simulating the operation of the machine;

c) write down verbal descriptions of states.

a) Input alphabetA=(ts E. + -); (where c is the number 0..9)

b) Examples.

Input chain: 3 8 . 7 1 E – 4 2

Machine states: Ø 1 1 2 3 3 4 5 6 6

Input chain: . 9 E 2 1.

Machine states: Ø7 3 4 6 6.

c) Ø initial state; waiting for the mantissa digit or dot.

1 – the digit of the first part of the mantissa is read; waiting for another number or dot, or symbol E.

2 – point read; waiting for a fractional digit or symbol E.

3 – the digit of the fractional part of the mantissa is read; waiting for another number or symbol E.

4 – symbol E read; waiting for +, -, or exponent digits.

5 – the order sign is read; waiting for the order number.

6 – the order number is read; waiting for another number.

7 – the dot is read as the 1st character of the input chain; waiting for the required digit of the fractional part of the mantissa.

Er- error status.

2. Construct a circuit and transition table of a finite state machine.

All transitions not marked with arrows lead to the Er error state.

					Admissibility








Er

Here, all empty cells correspond to a transition to the Er error state.

3.Bring the resulting automaton to its minimal form.

There are special mathematical methods that allow optimizing finite state machines, that is, finding redundant states of the machine. There are algorithms for reducing the automaton to a minimal form. From the results of applying such an algorithm, the equivalence of states 2 ~ 3 follows.

It is easy to verify that all states are reachable by looking at the transition diagram of the machine. Thus, to obtain a minimal reduced automaton, factorization should be carried out by combining states 2 and 3.

For convenience of further description, we rename the states as follows:

Below is the new diagram and state machine transition table.

New transition table:








Er

Processor procedure call table:

	2 a		7 a
	2 b	4 a	3 a
	3 b	4 b
	6 a			5 a
	6 b
	6 c
	3 c
Er

4. Build a processor that processes the end-of-line character.

(In the table, all empty cells correspond to a call to the “NO” procedure, which rejects the input chain). The Yes procedure ends the operation of the machine, accepting the input chain and producing the result of its processing.

5. Supplement processor transitions with procedure names.

For convenience, in this case, the name of the procedure is formed from the number of the state into which the machine goes, supplemented by a serial letter of the Latin alphabet (see also the diagram in the figure).

Note: if the processor must issue an error message, then you should enter designations for the procedures for processing each type of error, filling in all the empty cells of the table with them.

6. Enter the necessary registers - variables needed by the machine to obtain the result.

Number – register of the significant part of a number (integer).

Order– order register (integer).

Counter– register of the counter of digits after (integer).

Sign- (±1) – order sign.

7. Describe the procedures called in accordance with the table and processing the values of processor registers.

2a: Number:= c

2c: Number := 10 * Number+ c

3a: Counter := 0

3c: Counter := Counter + 1

Number := 10 * Number+ c

3s: Number:= c; Counter =: 1

4a: Counter =: 0

5a: Sign:= (+1 if a=’+’ or -1 if a=’-‘) (here a is the input symbol.)

6a: Sign := +1

Order:= c

6c: Order:= c

6s: Order := 10 * Order+ c

Yes 1: Order := 0

Yes2: Order:= -Counter

Yes3: Order := Sign * Order - Counter

Here the symbol Æ denotes the absence of any action - an empty procedure. In cases where an integer register is assigned a character (for example: Counter=ts), we mean the implicit conversion of a digit symbol into the number it denotes.

7.Check the operation of the machine (procedure) on one or more chains so that each transition of the machine is carried out at least once.

As examples, consider the operation of the machine in processing the following three input chains. The expected value of the Number and Order registers at the processor output is indicated in parentheses.

a) 67.89E-12┤ (6789, -14)

b) 2E3┤ (2,3)

c) .89┤ (3,-1)

Input symbol	Transition to state, procedure	Register values
Input symbol	Transition to state, procedure	Number	Order	Counter	Sign
	1 (initial)
		6
		67
		67		0
		*678*		1
		*6789*		2

					-1


		*6789*	*-14*
	1 (initial)
		2
				0
			3		+1
		2	3
	1 (initial)

		8		1
		89
		89	-2

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 the 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.

The result of the machine's operation is determined by its final state.

There are various options for specifying a finite state machine. For example, a state machine can be specified using five parameters: , where:

The machine starts working in state q 0, reading one character at a time from the input string. The read symbol transfers the machine to a new state from Q in accordance with the transition function. If, upon completion of reading the input word (chain of symbols), the automaton is in one of the accepting states, then the word is “accepted” by the automaton. In this case, it is said to belong to the language of the given automaton. Otherwise the word is "rejected".

State machines are widely used in practice, such as in parsers, lexical analyzers, and model-based software testing.

Other ways of describing

State diagram ( or sometimes transition graph) - graphical representation of a set of states and transition functions. It is a loaded unidirectional graph, the vertices of which are the states of the spacecraft, the edges are transitions from one state to another, and the symbols at which this transition occurs. If the transition from state q1 to q2 can be carried out upon the appearance of one of several symbols, then all of them must be inscribed above the arc of the diagram (branch of the graph).
Transition table- tabular representation of the function δ. Typically, in such a table, each row corresponds to one state, and each column corresponds to one valid input character. In the cell at the intersection of the row and column, the action that the machine must perform is written if, in a situation where it was in a given state, it received a given symbol at the input.

Determinism

Finite machines are divided into deterministic and non-deterministic.

Deterministic finite state machine

A deterministic finite automaton (DFA) is an automaton in which for each sequence of input symbols there is only one state into which the automaton can go from the current one.
A non-deterministic finite automaton (NFA) is a generalization of a deterministic one. Non-determinism of automata is achieved in two ways:

There are transitions marked with an empty chain ε	Several transitions, marked with the same symbol, emerge from one state

If we consider the case when the machine is specified as follows: , where:

Then the third sign of nondeterminism appears - the presence of several initial (starting) states of the automaton.

There is a theorem that states that “Any non-deterministic finite automaton can be converted into a deterministic one so that their languages coincide” (such automata are called equivalent). However, since the number of states in an equivalent DFA in the worst case grows exponentially with the number of states of the original DFA, in practice such determinization is not always possible. In addition, finite state machines with outputs are generally not determinizable.

Due to the last two remarks, despite the greater complexity of non-deterministic finite automata, NFAs are predominantly used for tasks related to text processing.

Automata and regular languages

For an automaton, one can define a language (a set of words) in the alphabet Σ that it is- these are the names of words, when entered, the machine goes from the initial state to one of the states of the set F.

Specialized programming languages

Sequential Function Chart (SFC) language is a graphical programming language widely used for programming industrial logic controllers (PLCs).

In SFC, a program is described as a schematic sequence of steps connected by transitions.

Model development using finite state machines

Finite machines make it possible to build models of parallel processing systems; however, in order to change the number of parallel processes in such a model, it is necessary to make significant changes to the model itself. In addition, an attempt to develop a complex model on a finite state machine will lead to a rapid increase in the number of states of the machine, which will ultimately make the development of such a model an extremely tedious task. As noted above, the last problem can be solved by using a non-deterministic automaton.

Notes

Links

Theory of automata / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Probability theory. Math statistics. Theoretical cybernetics. - M.: VINITI, 1976. - T. 13. - P. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Application of finite state machines to solve automation problems
An example of a finite state machine implementation in Python for the Django framework

Wikimedia Foundation. 2010.

Keynes, John Maynard
State diagram (automaton theory)

See what a “Finite State Machine” is in other dictionaries:

state machine- CA Computational model describing an automaton with a finite number of states. CAs are widely used in programming, for example, in lexical analyzers of compilers. finite state machine Sequence specification... ...

State machine- mathematical model of a device with finite memory. A state machine processes a plurality of discrete input signals into a plurality of output signals. There are synchronous and asynchronous finite state machines. In English: Finite state machine See... Financial Dictionary

state machine- baigtinis automatas statusas T sritis automatika atitikmenys: engl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. finite state machine, m pranc. auto final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas

FINITE STATE MACHINE- an automaton, which has many states, as well as many input and output signals, are finite. K. a. may be a technical model. devices (computer, relay device) or biol. systems (idealized animal nervous system). Important... ... Big Encyclopedic Polytechnic Dictionary

modular state machine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. English-Russian dictionary of electrical engineering and power engineering, Moscow, 1999] Topics of electrical engineering, basic concepts EN finite modular automaton ... Technical Translator's Guide

accessibility state machine- (ITU T Y.1711). Topics: telecommunications, basic concepts EN availability state machineASM... Technical Translator's Guide

State machine with memory- A finite state machine with memory is a mathematical model of a device whose behavior depends on both input conditions and the previous state. To describe a finite automaton with memory, the languages of operator schemes, regular... ... Wikipedia are used

deterministic finite state machine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. English-Russian dictionary of electrical engineering and power engineering, Moscow, 1999] Topics of electrical engineering, basic concepts EN finite deterministic automaton ... Technical Translator's Guide

Moore machine- (automaton of the second kind) in the theory of calculations, a finite automaton, the output value of the signal in which depends only on the current state of the given automaton, and does not directly depend, unlike the Mealy automaton, on the input values. Moore's automaton is named... Wikipedia

In this article, the term “finite 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 between input and output signals, as well as input signals and subsequent states. An intelligent reader will immediately note that the finite 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 signal, as opposed to a Moore machine where the outputs are functions of the state only. In both cases, the subsequent state is a function of the current state and the input signal.

Let's look at 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 appearance of a slash does not produce an output signal, but causes the machine to go into the second state. If in the second state the machine does not find a slash, it returns to the first, since it requires the presence of 2 slashes in a row. If the second slash is found, the machine issues a “ready” signal.

Find out what the customer needs.

Create a State Transition Diagram

Encode the "skeleton" of a state machine without detailing the branch operations.

Make sure the transitions are functioning correctly.

Be specific about transition details.

Take the test.

State machine example

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

First, let's look at the equipment. The aircraft's landing gear consists of a nose gear, a main left landing gear, and a 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 direction valve - "down" or "up" - to allow pressure to raise or lower the landing gear. Each of the chassis supports has a limit switch: one of them closes if the chassis is raised, the other - if it is locked in the down position. To determine whether the aircraft is on the ground, a limit switch on the nose gear strut closes when the aircraft's weight 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 (go position).

Now let's move on to developing a finite state machine. The first and most difficult step is to understand the customer’s real expectations. One of the advantages of a finite 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 similar to this: do not 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 the rest of the cases? Is it enough to retract the landing gear the moment the plane takes off from the ground? What if the plane bounces on a bump on the runway? What if the pilot moves the gear stick into the up position while parking and, as a result, starts to take off? Should the landing gear be raised in this case?

One of the advantages 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 walk through the entire process with him. The following designation for state transition is accepted: “the event that caused the transition”/“the output signal as a result of the transition.” If we had only developed what the customer initially asked for (“do not retract the landing gear if the plane is on the ground”), then we would have received the machine shown in Figure 2.

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

Computers work very quickly compared to mechanical equipment

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 thing, otherwise you wouldn’t be needed!

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

A state machine based on what the customer actually requires is shown in Figure 3. Here we want to prevent the aircraft's landing gear from retracting until it is definitely in the air. To do this, after opening the landing switch, the machine waits for several seconds. We also want to respond to the rising edge of the pilot's lever rather than level, which will avoid problems if someone moves the lever while the plane is in park. Retracting or extending the landing gear takes a few seconds, and we must be prepared for the situation that the pilot will change his mind during this operation and move 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 is in the air for 2 seconds.

Implementation of a finite state machine

Listing 1 is my implementation of the state machine shown in Figure 3. Let's discuss some 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 called in certain states*/

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

State_Type curr_state;

InitializeLdgGearSM();

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

Current state, called once per iteration */

while (1) {

state_table();

DecrementTimer();

void InitializeLdgGearSM( void )

curr_state = GEAR_DOWN;

/*Stopping equipment, turning off lights, etc.*/

void GearDown( void )

/* Go to the waiting state if the plane

Not on the ground and received a command to raise the landing gear*/

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 changed his decision, go to the “landing gear lower” state*/

if(gear_lever == DOWN) (

curr_state = LOWERING_GEAR;

void GearUp( void )

/*if the pilot moved the lever to the “down” position,

We go to the “landing gear lowering” state*/

if(gear_lever == DOWN) (

curr_state = LOWERING_GEAR;

void WtgForTakeoff( void )

/* Wait before raising the landing gear.*/

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 state for each of the 20-30 states). This can also lead to errors if you change the code at the final stages of testing. You may have never forgotten a break statement at the end of a case, but such cases have happened to me. The code for one state will never end up in the code for another if you have a separate function for each state.

To avoid using a switch statement, I use an array of pointers to state functions, and declare the variable used as an 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. These variables are assumed to be "magic addresses" associated with the hardware through invisible means.

The other obvious thing is that code doesn't really matter at this point. He simply moves 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 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 data entry has occurred.

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

In the state transition table, there is one row per state transition.

When coding a state machine, try to preserve its strength—a clear 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 as much like a state transition table and a state transition diagram as possible. This symmetry helps prevent errors and explains why state machines are such an important part of an embedded systems programmer's arsenal. Of course, you could achieve the same effect with checkboxes and an infinite number of nested if statements, but this would make it very difficult to track the code and compare it to the customer's wishes.

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

void RaisingGear( void )

/*After all the switches are raised, we go to the “chassis raised” 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 retracting the landing gear*/

if(gear_lever == DOWN) (

pump_direction = DOWN;

curr_state = GEAR_LOWERING;

Remember to avoid latent conditions. A hidden state occurs when, out of laziness, you try to add a conditional substate instead of adding a specific state. For example, if your code processes the same input signal in different ways (i.e. triggers different state transitions) depending on the mode, then it is a hidden state. In this case, I would wonder if this state should be split into two? Using hidden states negates the benefit of using a state machine.

As a practice, you can extend the state machine we just looked at by adding a timeout to the landing gear retract or extend cycle, because... The mechanical engineer doesn't want the hydraulic pump to run longer than 60 seconds. If the cycle ends, the pilot must be alerted by a green and red light toggling, and must be able to move the lever again to try again. You might also want to ask a hypothetical mechanical engineer what the effect of reversing a pump's direction while it's running is on the pump, because it happens in two cases when the pilot changes his mind. Of course, the mechanic will say it’s negative. Then how would you modify the state machine to quickly stop the pump when changing direction?

State machine testing

The beauty of coding algorithms as 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, since even a medium-sized state machine can have up to 100 different transitions. By the way, the number of transitions is a great way to measure the complexity of a system. The latter is determined by the customer's requirements, and the state machine makes the scope of testing obvious. With a less organized approach, the amount of testing required may be just as impressive, but you simply won't know it.

It is very convenient to use print statements in your code that display the current state and the values of input and output signals. This allows you to easily observe what the Golden Rule of Software Testing expresses: check that the program does what it is intended to do, and also that it does not do anything unnecessary. In other words, are you getting only the outputs you expect, and what else is going on beyond that? Are there any “difficult” state transitions, i.e. states that randomly pass for only one repeat of the loop? Do the outputs change when you don't expect them to? Ideally, the output of your printfs should noticeably 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 signal polarity wrong - "Oh, I thought 1 meant landing gear up and 0 meant landing gear down." In many cases, my hardware assistant would use 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 the customer's requirements are met, I can launch a state machine of similar complexity in a couple of days. Almost always the machines do what I want. The most difficult thing is, of course, to understand exactly what the customer wants and to 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 software development to support flights of research spacecraft. Worked in the field of embedded systems development for 17 years. Martin holds a Bachelor of Science in Aerospace Engineering and a Master of Science in Electrical Engineering from Cornell University.

The result of the machine's operation is determined by its final state.

There are various options for specifying a finite state machine. For example, a state machine can be specified using five parameters: , where:

State machines are widely used in practice, such as in parsers, lexical analyzers, and model-based software testing.

Other ways of describing

State diagram ( or sometimes transition graph) - graphical representation of a set of states and transition functions. It is a loaded unidirectional graph, the vertices of which are the states of the spacecraft, the edges are transitions from one state to another, and the symbols at which this transition occurs. If the transition from state q1 to q2 can be carried out upon the appearance of one of several symbols, then all of them must be inscribed above the arc of the diagram (branch of the graph).
Transition table- tabular representation of the function δ. Typically, in such a table, each row corresponds to one state, and each column corresponds to one valid input character. In the cell at the intersection of the row and column, the action that the machine must perform is written if, in a situation where it was in a given state, it received a given symbol at the input.

Determinism

Finite machines are divided into deterministic and non-deterministic.

Deterministic finite state machine

A deterministic finite automaton (DFA) is an automaton in which for each sequence of input symbols there is only one state into which the automaton can go from the current one.
A non-deterministic finite automaton (NFA) is a generalization of a deterministic one. Non-determinism of automata is achieved in two ways:

There are transitions marked with an empty chain ε	Several transitions, marked with the same symbol, emerge from one state

If we consider the case when the machine is specified as follows: , where:

Then the third sign of nondeterminism appears - the presence of several initial (starting) states of the automaton.

Due to the last two remarks, despite the greater complexity of non-deterministic finite automata, NFAs are predominantly used for tasks related to text processing.

Automata and regular languages

Specialized programming languages

Sequential Function Chart (SFC) language is a graphical programming language widely used for programming industrial logic controllers (PLCs).

In SFC, a program is described as a schematic sequence of steps connected by transitions.

Model development using finite state machines

Notes

Links

Theory of automata / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Probability theory. Math statistics. Theoretical cybernetics. - M.: VINITI, 1976. - T. 13. - P. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Application of finite state machines to solve automation problems
An example of a finite state machine implementation in Python for the Django framework

Wikimedia Foundation. 2010.

Keynes, John Maynard
State diagram (automaton theory)

See what a “Finite State Machine” is in other dictionaries:

accessibility state machine- (ITU T Y.1711). Topics: telecommunications, basic concepts EN availability state machineASM... Technical Translator's Guide

Finite state machines. Finite state machines: converters and recognizers How to program a finite machine

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

see also

Links

See what a “Finite State Machine” is in other dictionaries:

State machine example

State machine testing

Launch

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

see also

Links

See what a “Finite State Machine” is in other dictionaries:

Popular articles

Latest articles

Sections

Pages

Special projects

Contacts