Basic concepts of the theory of abstract automata. An abstract digital automaton is called initial if the initial state ao is distinguished on the set of its states A

Topic 5.1. Processing information using finite state machines

Chapter 5. Fundamentals of the theory of finite state machines

Summary on the topic

Review questions

1. What route is this?

2. In what case is a route called cyclic?

3.What is a circuit?

4. In what case is a chain a simple chain?

5. Give the definition of an Euler cycle?

6.What is the difference between the Euler and Hamilton cycles?

7.When is a graph called a tree?

8.What are the coherent components of a forest?

9.A vertex is called a terminal vertex if?

This topic discusses such concepts as route, cycle, chain, contour, and so on in relation to graphs. Euler and Hamiltonian cycles are given. A separate graph structure is shown, which is defined as a tree. The collection of these structures is characterized as a forest.

Target: consider the basics of finite state machine theory.

Tasks:

1. Consider the concept of an abstract automaton.

2. Identify ways to specify automata.

3. Consider the relationship between the Mil and Moore automata.

Machine- a discrete information converter capable of transitioning from state to state under the influence of input signals and generating output signals.

An abstract automaton is defined using the following five sets:

A = (X, Y, S, d, l),

Where X = (X 1, X 2 ... X M)– the input alphabet of the machine or a set of input symbols;

Y = (Y 1, Y 2 ... Y N)– the output alphabet of the machine or a set of output symbols;

S = (S 0 , S 1 . . . S K-1 )- alphabet or set internal states machine;

S 0– initial state of the machine (at the moment of time t = 0).

d– transition function;

l- function of machine outputs.

The machine is called finite state machine , if the sets X, Y, S finite (or countable).

The machine operates at discrete moments of time t = 0, 1, 2 ...n(Fig. 5.1) .

Rice. 5.1. State machine

At each moment of time, the automaton is in one of the many states S.

Transitions function d t the next state of the machine depending on the current state and the input signal or symbol of the input alphabet. In other words, the function d Each “state – input signal” pair is associated with the next state.

d: S´X ® S; d- is a mapping of the Cartesian product S´X V S.

The transition function can be written as follows: S t+1 = d(S t , X t).

Output function l determines at every moment of time t machine output signal.

There are two models of slot machines – the Mealy slot machine and the Moore slot machine. They differ in the function of the outputs, which is defined as follows:

Y t = l (S t , X t)- for the Mili machine, or l: S´X®Y.

Y t = l (S t)- for the Moore machine.

In the Mili machine, the output signal at the moment of time t depends on the input signal at the moment of time t, and from the current state.

In a Moore machine, the output signal clearly does not depend on the input signal and is determined only by the current state.

Machine status is the machine’s memory of past input influences.

Automata are also called sequential machines (Sequential Machines), since the input sequence is converted into a state sequence and an output sequence.

We can say that an abstract automaton has 1 input and 1 output. Sequences of letters of the input alphabet are received at the input of the machine, and output sequences are formed at the output.

Word or chain is a finite sequence of symbols (letters) of the input alphabet. The following conditions must be met (automation conditions):

1. The lengths of the input and output words are the same;

2. Identical initial segments of input words correspond to identical initial segments of output words.

Having one input, one output and at each moment of time being in one state out of many possible ones. The input to this device is symbols of one alphabet, and at the output it produces symbols (in the general case) of another alphabet.

Formally, an abstract automaton is defined as five

$\backslash boldsymbol(A\; =\; (S,\; X,\; Y,\; \backslash delta,\; \backslash lambda))$

Limiting the number of parameters of an abstract automaton defined the concept of a finite automaton.

The functioning of the automaton consists of generating two sequences: a sequence of the next states of the automaton $\backslash boldsymbol(s\_1s\_2s\_3...)$ and sequences of output symbols $\backslash boldsymbol(y\_1y\_2y\_3...)$, which for a sequence of characters $\backslash boldsymbol(x\_1x\_2x\_3...)$ unfold at discrete time moments t = 1, 2, 3, ... Discrete time moments are called clock cycles.

The functioning of the automaton at discrete moments of time t can be described by a system of recurrent relations: $\backslash boldsymbol(s(t+1)=\backslash delta(s(t),x(t));)$

$\backslash boldsymbol(y(t)=\backslash lambda(s(t),x(t)).)$

To clarify the properties abstract automata classification introduced.

Abstract automata form a fundamental class of discrete models, both as a model in their own right, and as a fundamental component of Turing machines, store-memory automata, finite state machines, and other information transformers.

Write a review about the article "Abstract automaton"

An excerpt characterizing the Abstract Automaton

Kutuzov, accompanied by his adjutants, rode at a pace behind the carabinieri.
Having traveled half a mile at the tail of the column, he stopped at a lonely abandoned house (probably a former inn) near the fork of two roads. Both roads went downhill, and troops marched along both.
The fog began to disperse, and vaguely, about two miles away, enemy troops were already visible on opposite hills. To the left below the shooting became louder. Kutuzov stopped talking with the Austrian general. Prince Andrei, standing somewhat behind, peered at them and, wanting to ask the adjutant for a telescope, turned to him.
“Look, look,” said this adjutant, looking not at the distant army, but down the mountain in front of him. - These are the French!
Two generals and adjutants began to grab the pipe, snatching it from one another. All the faces suddenly changed, and everyone expressed horror. The French were supposed to be two miles away from us, but they appeared suddenly, unexpectedly in front of us.
- Is this the enemy?... No!... Yes, look, he... probably... What is this? – voices were heard.
Prince Andrey with the naked eye I saw below to the right a dense column of French rising towards the Absheronians, no further than five hundred steps from the place where Kutuzov stood.
“Here it is, the decisive moment has come! The matter has reached me,” thought Prince Andrei, and, hitting his horse, he rode up to Kutuzov. “We must stop the Absheronians,” he shouted, “Your Excellency!” But at that very moment everything was covered with smoke, close shooting was heard, and a naively frightened voice two steps from Prince Andrei shouted: “Well, brothers, it’s a Sabbath!” And it was as if this voice was a command. At this voice, everything started to run.
Mixed, ever-increasing crowds fled back to the place where five minutes ago the troops had passed by the emperors. Not only was it difficult to stop this crowd, but it was impossible not to move back along with the crowd.
Bolkonsky only tried to keep up with her and looked around, perplexed and unable to understand what was happening in front of him. Nesvitsky with an embittered look, red and not like himself, shouted to Kutuzov that if he did not leave now, he would probably be captured. Kutuzov stood in the same place and, without answering, took out a handkerchief. Blood was flowing from his cheek. Prince Andrei pushed his way up to him.
-Are you injured? – he asked, barely keeping his lower jaw from trembling.
– The wounds are not here, but where! - said Kutuzov, pressing a handkerchief to his wounded cheek and pointing at the fleeing people. - Stop them! - he shouted and at the same time, probably making sure that it was impossible to stop them, he hit the horse and rode to the right.

6 Basic concepts and definitions of the theory of abstract automata (lecture No. 9)
Digital (discrete) automatic machine (DA) is a device that receives, stores and/or converts discrete information according to a certain algorithm. Examples of target audiences include living organisms, processors, Appliances calculators are real devices, and there are also abstract ones, for example, models of algorithms. TA belong to serial devices. This class of devices is determined by the fact that the value of the outputs depends not only on the input values, but also on the current state of the device. Those. the concept is introduced - state. In order to store data about the state in which the device is located, storage elements - triggers - are used in the target audience.
6.1 Mathematical model of a digital machine
A digital machine is a device characterized by a set of internal states into which it will fall under the influence of commands from a program embedded in it. The transition of an automaton from one state to another occurs at a certain point in time.

Mathematical model of target audience (and in the general case of any discrete device) is the so-called abstract automaton, defined as a 6-component tuple: S=(A,X,Y,,,a 1) which has:

1. 
   A=(a 1 , a 2 , ... ,a m ) – the alphabet of states – a set of states in which the designed digital automaton can be located. Number of states plays important role when implementing target audience. The more states, the more storage elements (triggers) are required to build the target audience.
2. 
   X=(x 1 , x 2 , ... ,x f ) – alphabet of input values ​​– a set of values ​​that can be input to the target audience. For example, if the machine has a two-digit binary input, then the elements of the alphabet can be 00, 01, 10 and 11.
3. 
   Y=(y 1, y 2, ..., y g) – alphabet of output values ​​– a set of values ​​that can be set at the output of the target audience.
4. 
   : AXA – transition function a(t+1)= (x(t),a(t)). The transition function determines which state a(t+1) the machine will move under the influence of the input signal x(t), if in this moment time the machine is in the state a(t).
5. 
    : AZW – output function y(t)=  (a(t), x(t)). The outputs function determines what output value y(t) will be set at the output of the machine depending on the input value x(t) and current state a(t) .
6. 
   a i  A - the initial state of the machine - the state into which the DA is installed after power is applied or after a reset

Figure 6.1 – Abstract automaton

An abstract automaton (Figure 6.1) has one input and one output. The automaton operates in discrete time, taking non-negative integer values ​​t = 0,1,2,... At each moment t of discrete time, the automaton is in some state a(t) from the set of states of the automaton, and at the initial moment t = 0 it is always is in the initial state a(0)=a1. At moment t, being in state a(t), the automaton is capable of receiving a letter of the input alphabet X(t) as input  Z. In accordance with the output function, it will produce at the same time t the letter of the output alphabet y(t)=(a(t), z(t)) and, in accordance with the transition function, will move to the next state a(t+1 )=, a(t)  A, y(t)  Y.

The meaning of the concept of an abstract automaton is that it implements some mapping from the set of words of the input alphabet X to the set of words of the output alphabet Y. That is, if the input of the automaton, set to the initial state a1, is supplied letter by letter with a certain sequence of letters of the input alphabet x(0), x(1),... - the input word, then the letters of the output alphabet y(0) will appear sequentially at the output of the automaton ), y(1),... is the output word. That. output word = (input word), where  is the mapping performed by the abstract automaton.

At the level abstract theory the concept of “operation of an automaton” is understood as the transformation of input words into output words. We can say that in an abstract automaton we abstract from its structure - the contents of the rectangle (Figure 6.1), considering it as a “black box”, i.e. We focus on the behavior of the machine relative to the external environment.

The concept of state in the definition of an automaton was introduced due to the fact that there is often a need to describe the behavior of systems whose outputs depend not only on the state of the inputs to this moment time, but also from some prehistory, i.e. from signals that arrived at the system inputs earlier. States correspond precisely to some memory of the past, allowing time to be eliminated as an explicit variable and the output signal to be expressed as a function of the state and input at a given time.

6.2 Classification of digital machines

The abstract automata discussed above can be divided into:

1. 
   fully defined and partial;
2. 
   deterministic and probabilistic;
3. 
   synchronous and asynchronous;

Partial is an abstract automaton whose transition function or output function, or both of these functions are not defined for all pairs (a i, z j).

TO deterministic These include automata for which the condition of unambiguous transitions is satisfied: an automaton located in a certain state a i cannot transition to more than one state under the influence of any input signal z j.

Otherwise it will be probabilistic automaton , in which, for a given state a i and a given input signal z j, a transition with a given probability to various states is possible.

For determining synchronous and asynchronous the concept of automata is introduced steady state . A state a s of an automaton is called stable if for any state a i and input signal z j such that (a i , z j) = a s we have (a s , z j) = a s , i.e. a state is stable if, having entered this state under the influence of some signal zj, the automaton leaves it only under the influence of another signal zk, different from zj.

An automaton in which all states are stable - asynchronous .

The machine is called synchronous , if it is not asynchronous.

The abstract automaton is called final , if the sets A = (a 1 , a 2 , ..., a m ) are finite, Z = (z 1 , z 2 , ..., z f ), W = (w 1 , w 2 , ..., w g ). The machine name is initial , if the initial state a 1 is selected in it.
6.3 Types of digital machines
In practice, two classes of machines are most widely used - Mealy and Moore machines.

The law of operation of the Mealy machine is given by the equations:

In addition to Mealy and Moore automata, it is sometimes convenient to use a combined model of automaton, the so-called C-automaton.

An abstract C-automaton can be represented as a device with one input, which receives signals from the input alphabet X, and two outputs, at which signals from the alphabets Y and U appear. The difference between a C-automaton and the Mealy and Moore models is that it simultaneously implements two output functions  1 and  2, each of which is characteristic of these models separately. The operating law of the C-machine can be described by the following equations:
a(t+1) =(a(t), z(t)); w(t) = 1 (a(t), z(t)); u(t) =  2 (a(t)); t = 0, 1, 2, ...
The output signal U h = 2 (a m) is issued all the time while the machine is in the state a m. The output signal Wg= 1 (a m , z f) is issued during the action of the input signal Z f when the machine is in the state a m.
7 Methods of describing and specifying automata (lecture No. 10)
In order to define an automaton, it is necessary to describe all components of the tuple S=(A, X, Y, , , a 1). The sets A, X, Y are described and specified by a simple listing of their elements. Among the diversity in various ways tasks of functions  and  (and therefore the entire machine as a whole) are most widely used in tabular and graphic form.
7.1 Tabular method of describing digital machines

In the tabular method of describing digital machines, two types of tables are used - a transition table and an output table.

Transition table displays the transitions function. The rows of the table correspond to the states of the machine, i.e. There are as many rows in the table as there are states of the machine. The columns of the table correspond to input values ​​that can be supplied to the inputs of the target audience, i.e. as many columns as there are elements in the input alphabet. At the intersection of the i-column and j-row in the table cell, the state to which the target audience will go under the influence of the input signal x i (to which the i-th column corresponds) from state a j (to which corresponds to jth line). The transition table is shown in Figure 6.2

Output table For Moore machine gun consists of one column. The rows of the table correspond to the states of the machine, i.e. There are as many rows in the table as there are states of the machine. An example of a table is shown in Figure 6.4

y 2

Figure 6.7 – Graphical representation of the Moore machine

Figure 6.8 – Graphical representation of the Mili machine

• 
  definition of input, output and alphabet of states, functions of transitions and outputs;
• 
  specifying automaton graphs and tables of transitions and outputs;
• 
  minimizing the number of states

8.1 Structure of a digital machine

The internal structure of a digital machine can be depicted as shown in Figure 8.1.

Figure 8.1 – Block diagram of a digital machine.

A memory block is a set of flip-flops that store the bits of an encoded state number. The number of triggers depends on the number of states in which the machine can be. And it is calculated as:

N=log 2 M
where M is the number of states, and N is the number of triggers
Combination circuit No. 2 implements the function of the machine’s outputs and at its output the machine’s output values ​​are set in accordance with the current state of the machine and the input values.

8.2 Minimizing the number of states of a digital machine
Often, when performing abstract synthesis, redundant states are introduced whose equivalence is not obvious. An excessive number of states can lead to the use of unnecessary triggers, which will complicate CS1 and CS2. Therefore, it is very important to minimize the number of states before its structural synthesis.

The minimization algorithm is based on partitioning the entire set of states into pairwise disjoint classes of equivalent states and replacing the entire equivalence class with a single state. The resulting minimized automaton will contain as many states into as many equivalence classes as the original set of states was divided into.

Definition Two states a s and a m are equivalent if
 (a s , E) = (a m , E), where - transition function, E – input word of arbitrary length.

In other words, states are equivalent if the same sequence of states is produced in response to the same input words, regardless of which of the two states a s or a m the machine was located at the initial moment of time. If two states are equivalent, then one state can be replaced by another.

In addition to equivalent states, there is the concept of k-equivalent states: 1-equivalent, 2-equivalent, etc.

Definition Two states a s and a m arek - equivalent if
 (a s , Ek) =  (a m , Ek), Where - transition function, Ek– input word lengthk .
Minimization algorithm:

1. 
   The partitions P 1, P 2, ... P K, P K+1 states of the automaton are found sequentially until at some K+1 step P K.+1 becomes equal to P K. In this case, the resulting k-equivalent partition will be represent completely equivalent classes.
2. 
   In each equivalence class, one state is selected, which form a new set of states of the minimized automaton.
3. 
   To redefine the functions of transitions and outputs, the rows that correspond to states that are not included in the new set of states of the minimized automaton are crossed out, and in the remaining rows of the transition table, all states are replaced with their equivalent states that are included in the new set.
4. 
   If a set consists of one state, then it has no equivalent states. If all states are included in separate sets from one state, then the automaton cannot be minimized.
5. 
   Partitioning into sets begins with the 0-equivalent class. IN in this case states with identical output signals fall into the same sets.

According to the method of forming the output function, three types of abstract automata are distinguished: Mealy automaton, Moore automaton, C-automaton. The Mealy machine is characterized by a system of equations:

y (t) =(a (t), x (t));

a (t+1) = δ (a (t), x (t)). (1-1)

Moore's automaton - system of equations:

a (t+1) = δ (a (t), x (t)). (1-2)

C-automatic - system of equations:

y 1 (t) =(a (t),x (t));

Y 2 (t) = 2 (a (t));

a (t+1) =δ (a (t),x (t)).

An arbitrary abstract Mealy or Moore automaton (Fig. 1.1.) has one input and one output channel. An arbitrary abstract C-automaton has one input and two output channels (Fig. 1.2.).

Figure 1.1 - Abstract automaton

Figure 1.2 Abstract C-automaton

If the input of an abstract Mealy or Moore automaton, set to the initial state a o, is supplied letter by letter with a certain sequence of letters of the input alphabet x (0), x (1),. is the input word, then at the output of the machine the letters of the output alphabet y (0), y (1), will appear sequentially. - exit word. For the case of a C-automaton, two sequences will appear at its outputs: y 1 (0), y 1 (1),. and y 2 (0), y 2 (1),. In an abstract C automaton, the output signal y 2 (t) = (a (t)) is issued all the time while the automaton is in state a (t). The output signal y 1 (t) =λ 1 (a (t),x (t)) is issued during the action of the input signal x (t) when the C-automaton is in state a (t).

Thus, at the level of abstract theory, the functioning of a digital machine is understood as the transformation of input words into output words.

There are fully defined and partial automata.

A fully defined abstract digital automaton is one whose transition function or output function, or both of these functions, are defined for all pairs of transitions (x i ,a j).

An abstract digital automaton is called partial if its transition function or output function, or both of these functions are not defined for all pairs of transitions (x i,a j).

An abstract digital automaton is called initial if the initial state a o is distinguished on the set of its states A.

1.3 Methods for specifying abstract automata

To set state machine S, it is necessary to describe all elements of the set: S=( X,A,Y,,,a o ). There are several ways to specify the operation of the machine, but the most commonly used are tabular (matrix), graphical, and analytical.

In the tabular method, the machine is specified by two tables: a transition table and an output table, or a connection matrix. The transition table of an arbitrary fully defined automaton is constructed as follows: the rows of the table are marked with the letters of the input alphabet of the automaton, and the columns of the table are marked with the letters of the alphabet of states of the automaton; In the transition table cell located on At the intersection of the row marked by the input signal x i and the column marked by the state a j, the state a k is set, which is the result of the transition of the machine from the state a j under the influence of the input signal x i, which is determined by the expression a k = (a j, x j).

Table 1.1 Automaton transition table

An example of filling out the transition table of some abstract fully defined automaton with an input alphabet X = (x 1, x 2) - and an alphabet of states A = (a 1, a 2, a 3) is presented in Table 1.2.

Table 1.2

If the abstract automaton is partial, then in the cell of its transition table located at the intersection of the row marked by the input signal and the column marked by the corresponding state (provided that the transition to this state under the influence of this input signal is not defined), a dash is placed, and any input word leading to the specified transition is illegal.

Filling the remaining cells is similar to the case of a fully defined automaton. The type of transition table does not depend on the type of machine being specified (Mili, Moore, S-automaton). The tables of outputs of the Mealy, Moore, and S-automata have differences.

The output table of a fully defined Mealy automaton is constructed as follows: the identification of columns and rows, as well as the table format, correspond to the transition table of the fully defined automaton. In the cell of the output table located at the intersection of the row marked by the input signal X j and the column marked by the state a k, the output signal Y m is placed, which the machine produces while in the state a k in the presence of the input signal Xj, which is determined by the expression Ym = (a k, x j).

Table 1.3 Table of outputs of the abstract Mealy automaton.

An example of filling the output table of some abstract fully defined automaton with input alphabet X=(x 1 , x 2 ), state alphabet A=(a 1 , a 2 , a 3 ) and output alphabet Y=(y 1 , y 2 , y 3 ) - presented in Table 1.4.

Table 1.4

Obviously, an abstract fully defined C-automaton is given by two output tables, the first of which is the output table of the Mealy automaton, and the second is the Moore automaton. If the machine is partial, then in some cells of its table there may be a dash, which means the absence of an output signal.

In practice, the transition and output tables are often combined into one table, called the marked transition table of the machine. Examples of marked transition tables are presented in Table 1.6. - 1.8 (General view of the marked transition table - table 1.6., marked transition table of the Mealy automaton - table 1.7., marked transition table of the Moore automaton - table 1.8.).

In addition to the transition and output tables discussed above, an arbitrary abstract automaton can be specified by a connection matrix.

The connection matrix is ​​square and contains as many columns (rows) as the number of different states the alphabet of states of a given automaton contains. Each column (row) of the connection matrix is ​​marked with a state letter of the machine. In the cell located at the intersection of the column marked with the letter a j and the row marked with the letter a s of the automaton, an input signal (or a disjunction of input signals) is placed under the influence of which this transition is carried out.

For an abstract Mealy automaton, the output signal that the automaton produces as a result of this transition is also placed in the cell next to the state (Table 1.9.) For the Moore automaton, the output signal is entered in the line next to the state (these states correspond to the initial states of the automaton).

Table 1.6

Table 1.7

Table 1.9.

In the graphical method of specifying, abstract automata are represented by directed graphs. The graph of an automaton is a directed connected graph whose vertices correspond to the states of the automaton, and the arcs between them correspond to transitions between states. Two vertices a k and a s are connected by an arc if the automaton has a transition from state a k to state a s. For a Mealy machine, the input and output signals are placed on the arc corresponding to a given transition (Fig. 1.3.); for a Moore machine, the input signal is placed on the arc, and the output signal is placed next to the vertex corresponding to the state (Fig. 1.4.).

Here we consider only deterministic automata for which 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 specifying an automaton, this means that in the graph of the automaton, two or more arcs marked by the same input signal cannot emerge from any vertex.

Figure 1.3-Graph of the Mealy machine Figure 1.4-Graph of the Moore machine

In the analytical method of specifying, abstract automata are defined by four objects:

S=( X, A, Y, F), where F specifies for each state a j of the automaton the mapping (XxA) - > (AxY). In other words, with the analytical method of specifying for each state of the automaton a j, a mapping F ai is indicated, which is the set of all triplets a p, x m, y k, and such that under the influence of the input signal x m the automaton goes from the state A j V state a p, while producing an output signal y k.

In relation to the general definition of an abstract automaton, the latter is equivalent to describing the functions δ and λ in accordance with the expression: a p = δ (a i, x m), y к = λ (a i, x m).

The mapping F ai is written as follows:

F ai (a p (X m /y k),a i (X f /y z) ...).

For an abstract Mealy automaton (Table 1.7.), the analytical task has the following form:

S=( X,A,Y,F), X=(x 1 ,x 2 ), A=(a 1 , a 2 , a 3 ), Y=(y 1 , y 2 , y 3 ),

F a1 =(a 2 (x 1 /y 2), a 1 (x 2 /y 3) ),

F a 2 = (a 3 (x 1 /y 3), a 1 (x 2 /y 1) ),

F a 3 = (a 1 (x 1 /y 3), a 2 (x 2 /y 2) ).

It should be noted that the function F ai is always written for the initial state.

Let us define synchronous and asynchronous automata. State a s of an automaton S is called a stable state if for any input signal x j X such that a s = δ (a i X m) a s = δ (a s , x m) holds.

An automaton S is called asynchronous if each of its states a s A is stable. An automaton S is called synchronous if it is not asynchronous.

It should be noted that automata built in practice are always asynchronous and the stability of their states is always ensured in one way or another, for example, by introducing synchronization signals. However, at the level of abstract automata theory, when an automaton is just a mathematical model that does not reflect many specific features of its implementation, it often turns out to be more convenient to operate with synchronous automata.