Methods for describing finite state machines. Methods for specifying digital automata Finite state machine and methods for specifying it

Two classes of languages ​​can be distinguished to describe the functioning of digital machines: elementary languages ​​and standard or automaton languages.

Beginning languages ​​specify the transition function and output function implicitly. The behavior of the automaton is described in terms of input and output sequences implemented by the operator, or sequences of control signals acting on the control automaton.

To describe the functioning of abstract target audiences on elementary language can be used:

Event algebra regular expression language;

Predicate Calculus Language;

Language of logical circuits of algorithms (LSA);

Language of graph diagrams of algorithms (GSA).

The GSA language together with the LSA language is called by one common term: the language of operator diagrams of algorithms (OSA). In practice, the GSA language is most often used.

3.3.1 Setting digital machines on standard ones
languages

Standard or automatic languages specify the transition functions of the outputs in explicit form. These include tables, graphs, transition and output matrices and their analytical interpretation. In order to define an automaton, it is necessary to describe all components of the vector
S=(A, Z, W, d, l, a 1).

With the tabular method of specifying A Mealy machine is described using two tables: a transition table and an output table. The transition table defines the function d(Table 3.4.), function output table - l(Table 3.5.). Each column of tables 3.4 and 3.5 is assigned one state from the set A, each line – one input signal from the set Z. At the intersection of a column a m and strings z f Table 3.4 records the status
a s, to which the machine should go from the state a m, under the influence of the input signal z f, i.e. a s = d(a m , z f). At the intersection of a column a m and strings z f the output signal is recorded in table 3.5 w g, issued by the machine in the state a m when a signal arrives at its input z f, i.e.
w g = l(a m , z f).

Table 3.4 Table 3.5

Mili machine transition table		Table of outputs of the Mili machine
	a 1	a 2	a 3	a 4			a 1	a 2	a 3	a 4
z 1	a 2	a 2	a 1	a 1		z 1	w 1	w 1	w 2	w 4
z 2	a 4	a 3	a 4	a 3		z 2	w 5	w 3	w 4	w 5

For the specified tables A ={ a 1 , a 2 , a 3 , a 4 } ; Z={ z 1 , z 2 };
W={w 1 ,w 2 ,w 3 ,w 4 ,w 5 }.

A Mealy machine can also be specified by one combined table of transitions and outputs (Table 3.6), in which each element a s/w g, written at the intersection of the column a m and strings z f, is defined as follows:

a s = d(a m , z f);w g = l(a m , z f).

The Moore automaton is specified by one marked transition table (Table 3.7), in which each column is assigned not only states a m, but also the output signal w g, corresponding to this state, where w g = l(a m). For table 3.7 A={a 4 , a 2 , a 3 , a 4 }; Z={z 1 , z 2 };
W={w 1 ,w 2 ,w 3 }.

One of the advantages of this method of specifying is that any table of transitions and outputs specifies a finite machine. In this case, two conditions must be satisfied:

Condition unambiguity(determinism), which means that for any pair a m z f a single transition state is specified a s and the only output signal w g, issued at the transition.

Condition full certainty, which means that for all possible pairs a m z f the status and output signal are always indicated.

Table 3.6 Table 3.7

Combined table of transitions and outputs of the Mili machine		Marked table of transitions and outputs of the Moore machine
	a 1	a 2	a 3	a 4			w 3	w 2	w 3	w 1
z 1	a 2 /w 1	a 2 /w 1	a 1 /w 2	a 1 /w 4			a 1	a 2	a 3	a 4
z 2	a 4 /w 5	a 3 /w 3	a 4 /w 4	a 3 /w 5		z 1	a 1	a 3	a 1	a 4
						z 2	a 2	a 4	a 4	a 1

The machine is called incompletely defined or partial, if either function d is not defined on all pairs ( a m z f)О A x Z, or function l is not defined on all specified pairs in the case of a Mealy automaton and on the set of not all internal states for a Moore automaton. For partial Mealy and Moore automata in the tables considered, a dash is placed in place of undefined states and output signals.

Automaton graph is a directed graph, the vertices of which correspond to states, and the arcs correspond to transitions between them. Arc from the vertex a m to the top a s, specifies a transition in the automaton from the state a m in a state a s. At the beginning of this arc the input signal is recorded z f О Z, causing this transition: a s = d(a m , z f). For the graph of the Mealy machine, the output signal is w g О W, formed at the transition, is written at the end of the arc, and for the Moore machine near the vertex , marked by status a m, in which it is formed. If the transition in the automaton from the state a m in a state a s produced under the influence of several input signals, then the graph arc directed from a m V a s, all these input and corresponding output signals are assigned. The graphs of Mealy and Moore automata, constructed according to Tables 3.6 and 3.7, are shown in Fig. 3.7, respectively. a, b.

In relation to the graph, the conditions of uniqueness and complete certainty will be as follows:

There are no two edges with the same input labels leaving the same vertex;

For every vertex a m and for any input signal z f there is such an edge marked with the symbol z f, which comes out a m.

Fig.3.7. Automata graphs: a– Miles; b– Mura

When specifying graphs with a large number of states and transitions, clarity is lost, so it turns out to be preferable to specify this graph in the form of a list - a table of transitions.

Direct jump table– a table that sequentially lists all transitions, first from the first state, then from the second, etc. Table 3.8 is a direct table of transitions of the Mealy machine, built according to the graph shown in Fig. 3.7.a.

In some cases it turns out to be convenient to use reverse a transition table in which the columns are designated in exactly the same way, but first all transitions to the first state are recorded, then to the second, etc. Table 3.9 is the inverse table of transitions of the Mealy machine, built according to the graph shown in Fig. 3.7, a.

Like a graph, transition tables must satisfy the conditions of uniqueness and completeness of transitions.

Table 3.8 Direct transition table of the Mealy machine		Table 3.9 Reverse table of transitions of the Mealy machine
a m(t)	z f(t)	a s(t+ 1)	w g(t)		a m(t)	z f(t)	a s(t+ 1)	w g(t)
a 1	z 1	a 2	w 1	a 3	z 1	a 1	w 2
	z 2	a 4	w 5	a 4	z 1	w 4
a 2	z 1	a 2	w 1	a 1	z 1	a 2	w 1
	z 2	a 3	w 3	a 2	z 1	w 1
a 3	z 1	a 1	w 2	a 2	z 2	a 3	w 3
	z 2	a 4	w 4	a 4	z 2	w 5
a 4	z 1	a 1	w 4	a 1	z 2	a 4	w 5
	z 2	a 3	w 5	a 3	z 2	w 4

The direct transition table of the Moore automaton is constructed in the same way as for the Mealy automaton. The only difference is that the output signal w g(t) is attributed to the state of the machine a m(t) (Table 3.10), or the output signal w g(t a s(t+ 1) (Table 3.11).

The inverse transition table of the Moore automaton is constructed in the same way as for the Mealy automaton. The only difference is that the output signal w g(t+1) is assigned to the state of the machine a s(t+ 1) (Table 3.12).

In some cases, to specify the machine, they use transition and output matrices, which are a table with two inputs. The rows and columns of the table are marked with states. If there is a transition from a m Under the influence z f V a s with issuance w g, then at the intersection of the line a m and column a s couple is recorded z f w g. It is clear that not every matrix defines an automaton. As a graph and table of transitions and outputs, it must satisfy the conditions of uniqueness and completeness of transitions.

Table 3.10 Direct transition table of the Moore machine Option 1		Table 3.11 Direct transition table of the Moore machine Option 2
a m(t)	w g(t)	z f(t)	a s(t+ 1)		a m(t)	z f(t)	a s(t+ 1)	w g(t+1)
a 1	w 3	z 1	a 1	a 1	z 1	a 1	w 3
		z 2	a 2		z 2	a 2	w 2
a 2	w 2	z 1	a 3	a 2	z 1	a 3	w 3
		z 2	a 4		z 2	a 4	w 1
a 3	w 3	z 1	a 1	a 3	z 1	a 1	w 3
		z 2	a 4		z 2	a 4	w 1
a 4	w 1	z 1	a 4	a 4	z 1	a 4	w 1
		z 2	a 1		z 2	a 1	w 3

Table 3.12 Reverse transition table of the Moore machine Option 2
a m(t)	z f(t)	a s(t+ 1)	w g(t+1)
a 1	z 1	a 1	w 3
a 3	z 1
a 4	z 2
a 1	z 2	a 2	w 2
a 2	z 1	a 3	w 3
a 2	z 2	a 4	w 1
a 3	z 2
a 4	z 1

Systems of canonical equations (SCE) and systems of output functions (SVF) are an analytical interpretation of transition and output tables or automata graphs. SKU - determines the functions of the transitions of the target audience, and SVF - determines the functions of the outputs of the target audience.

Each state of the target audience is interpreted as an event corresponding to a set of transitions to this state:

To shorten the notation of SKU and SVF, in the future, wherever possible, we will omit the signs of conjunction and tense t on the right side of equations like (3.10).

For the Mili machine specified in Table 3.8 or Table. 3.9 we write SKU and SVF (3.811 and 3.12. respectively):

a 1 (t+1) = z 1 a 3 Ú z 1 a 4 ; a 2 (t+1) = z 1 a 1 Ú z 1 a 2 ; a 3 (t+1) = z 2 a 2 Ú z 2 a 4 ; a 4 (t+1) = z 2 a 1 Ú z 2 a 3 .

(3.11)

w 1 (t) = z 1 a 1 Ú z 1 a 2 ; w 2 (t) = z 1 a 3 ; w 3 (t) = z 2 a 2 ; w 4 (t) = z 1 a 4 Ú z 2 a 3; w 5 (t) = z 2 a 1 Ú z 2 a 4.

(3.12)

Let us write down the SKU and SVF for the Moore machine given in Table. 3.10 - 3.12, (3.13 and 3.14 respectively).

Baranov Viktor Pavlovich. Discrete Math. Section 6. Finite automata and formal languages.

Lecture 31. Definition and methods of specifying a finite state machine. Synthesis task. Elementary automata

Lecture 30. DEFINITION AND METHODS OF SPECIFICATION OF A FINITE MACHINE.

SYNTHESIS PROBLEM. ELEMENTARY MACHINES

Lecture outline:

1. Definition of a finite state machine.

2. Methods for specifying a finite state machine.

1. Automata synthesis problem.
2. Elementary automata.
3. The problem of completeness of an automaton basis.
4. Canonical method for synthesizing an automaton.

1. State machine definition

SFEs do not take into account the fact that real devices operate over time. Compared to SFE, a finite state machine is a more accurate model of a discrete information converter. At the same time, the concept of a finite automaton, like any model, is associated with a number of simplifying assumptions.

Firstly, it is assumed that the input and output of the machine at each moment of time can be in only one of a finite number of different states. If a real converter has a continuous input signal, then to describe it using a finite state machine it is necessary to quantize this signal. In the formal definition of an automaton, a finite set of input and output states of the automaton is called the input and output alphabet, respectively, and individual states are called the letters of these alphabets.

Secondly, it is assumed that time changes discretely. The input and output states correspond to a discrete time sequence. Since a moment in time is uniquely determined by its index, for the sake of simplicity we will assume that time takes the values ​​1, 2, ..., ... The time interval is called a tick.

The operation of the machine is presented as follows.

The input of the machine receives signals from the input alphabet, which leads to the appearance of signals at the output from the input alphabet. The dependence of the output sequence on the input depends on the internal structure of the machine. Note that, unlike SFEs, which do not have memory, the automaton is a device with memory, i.e., the output of the automaton is determined not only by the input, but also by the history. Taking into account the history is carried out by the dependence of the output signal not only on the input, but also on the current state, which we denote.

Let us give a formal definition of an automaton.

A finite state machine is a quintuple of objects.

a finite set called the input alphabet; one of the possible input states;

a finite set called the output alphabet; the elements of this set determine the possible output states;

a finite set called the alphabet of internal states;

function of machine transitions: ; this function assigns a state to each “input-state” pair;

function of machine outputs: ; this function assigns an output value to each input-state pair.

The law of operation of the automaton: the automaton changes its states in accordance with the function and produces output signals in accordance with the function:

1. Methods for specifying a finite state machine

1. Tabular method of assignment. Since for functions both the domains of definition and values ​​belong to a finite set, they are specified using tables.

Example 1. We define the automaton as follows: , .We define the function using the transition table, and the function using the output table.

Table 1. Transition table Table 2. Output table

	State

	State

If the sequence of signals at the input of the machine is known, then the output sequence is uniquely determined by the tables of transitions and outputs.

2. Graphic method of assignment. A transition-output diagram is used. It is a oriented multigraph in which each internal state of the automaton corresponds to a vertex. The transitions of the automaton from state to state are depicted by arrows, on each of which the input symbol causing this transition and the output symbol produced by the automaton are written.

Fig.1 Transition-output diagram

Example 2. It is required to build an automaton that would work as follows: at each clock cycle, the next binary digits of the terms are received at the input of the automaton, the automaton produces the corresponding binary digit of their sum. For two-digit terms we have: , .

The machine is in state 1 if a carry occurs when adding previous bits, and in state 0 otherwise. The transition-output diagram is shown in Fig. 2.

1. Automata synthesis problem

By analogy with the problem of synthesis of SFE, one can pose a synthesis problem for automata. There is an unlimited set of basic machines. It is required to assemble an automatic machine with a predetermined functioning. In this case, the task of synthesis faces certain problems.

Let's assume that you need to connect the output of the machine to the input of the machine. This is possible under the condition that otherwise the second machine will not understand the signals coming from the first. This leads to a confusing situation where some connections are not possible.

To overcome this obstacle, the concept of a structural automaton is introduced, in which all alphabets (input, output and internal states) are encoded in binary words.

Let be a finite set of elements, and be a set of binary words of length, where. We will call an arbitrary injective mapping the encoding of a set by binary words.

Let's encode alphabets for an arbitrary automaton:

Let us denote the encoded input, output and state of the machine at a moment in time, respectively. Then the operating law will be presented in the form

The resulting automaton after coding is called structural. We will assume that a structural automaton has binary inputs, binary outputs, and the internal state of the automaton is specified by a binary word of length. In Fig. Figure 3 shows an abstract automaton and its corresponding structural automaton.

The transition to a structural automaton provides two important advantages for synthesis.

1. Compatibility of inputs and outputs, since binary information is transmitted through them. We will not give a general definition of a circuit of structural automata; it is similar to SFE.

2. Let’s write relations (2) in “coordinates”:

From (3) it follows that the law of functioning of a structural automaton is given by a system of Boolean functions.

1. Elementary automata

Let us identify the simplest structural automata and give them a name.

Let us first note that a functional element that has only one state can be considered as an automaton without memory.

Let's move on to automata with two states. Let the machine have one binary input and one binary output coinciding with the internal state: :

To specify the machine shown in Fig. 4, it is enough to set only the transition table:

Table 3

	State

Instead of asterisks, you need to put 0 and 1. This can be done in 16 ways, however, not all of them are acceptable. Suppose, for example, that in the first column of Table 3 both elements are zeros. Such an automaton, once in state 0, will no longer exit it, that is, it will work as a functional element. An analysis of similar situations shows that in order to obtain an automaton that is not reducible to an automaton without memory, it is necessary to require that each column of Table 3 contain both a zero and a one. There are only four such tables.

Table 4 Table 5

	State
					State

Table 6 Table 7

	State

	State

We have only two simplest automata, since 7 is obtained from 4, and 6 from 5 by inverting internal states.

The machine specified by Table 4 is called a delay or -trigger:

that is, this machine delays the signal by one clock cycle.

The machine specified by Table 5 is called a trigger with a counting input or -trigger. The state of the machine is reversed if a 1 is received at the input, and remains unchanged if a 0 is received at the input:

Let the -trigger be in state 0 at the initial moment of time. If at some point in time the -trigger is in state 0, then this means that an even number of ones arrived at the input of the machine. If the state is 1, then is odd. Thus, the flip-flop counts the number of ones at the input, but since it has only two states, it counts up to two.

When physically implementing triggers, two outputs are used: direct and inverse (Fig. 5). If we swap them, then the -trigger will produce an automaton specified by table 7, and the -trigger will produce an automaton specified by table 6.

1. The problem of completeness of an automaton basis

A set of structural automata is called complete (or automata basis) if any predetermined structural automaton can be constructed from them.

The efforts of mathematicians to obtain an analogue of Post's theorem for automata were unsuccessful. In 1964 M.I. Briefly proved the non-existence of an algorithm for determining the completeness of a system. In this case, variants of the completeness theorem with additional assumptions about the system are of interest. Let's look at the most popular of them.

Theorem. A system of automata containing a complete set of FE and -trigger (or -trigger) is complete.

Proof. Let us consider an arbitrary automaton specified by relations (2) and describe its circuit from the indicated automata, called the canonical structure (Fig. 6).

The scheme consists of two parts.

The left half is called the storage part. It consists of triggers, the set of states of which forms the state of the machine: if at the moment of time

then this means that the machine is in the state.

The right half is called the combinational part and represents the SFE. Inputs of this circuit:

1. binary word input signal of the machine;
2. binary word current internal state of the machine.

1. binary word output signal of the machine, which is implemented according to formulas (3);
2. a binary word that arrives at the inputs of flip-flops in the storage part and controls the memory of the machine.

Let us show that memory control signals are Boolean functions of the same variables as the output of the machine, and, therefore, they can be implemented by a complete FE system.

At each moment of time, memory control signals must transfer the machine from state to state. To do this, you need to change the state of each trigger

The -flip-flops or -flip-flops used in the canonical circuit have the following property: for any pair of states there is an input signal that transfers the automaton from state to state. Let's denote this signal by. For an -flip-flop, since the state into which the -flip-flop is set is equal to the input signal. For a trigger: at the input, 0 must be applied so that the state does not change; at 1 so that the trigger “flips over”.

So, or in vector form

Let us express it from the law of operation of the automaton (2). Then

The theorem has been proven.

1. Canonical method for synthesizing an automaton

Let's look at this method using a specific example.

Example. On the conveyor, along which two types of parts move, there is an automatic machine installed, the task of which is to sort the parts so that after passing by the machine they form groups. The machine pushes the unsuitable part off the conveyor. It is required to build a circuit of such an automaton using a trigger and the elements “AND”, “OR”, “NOT”.

The synthesis of the automaton is divided into the following stages.

1. Construction of an abstract automaton.

Input alphabet . The output alphabet is , where C is the collision of the part, P is its omission. The internal states of the automaton reflect its memory of which part of the group it has already formed: . As the group is formed, the machine moves cyclically through these states, without changing state when an unsuitable part arrives. The transition-output diagram is shown in Fig. 7.

2. Coding alphabets.

One of the possible encoding options is shown in the following tables.

Input Output Status

3. Construction of the canonical structure of the automaton.

The canonical structure of the developed automaton is shown in Fig. 8.

Let us find the dependences of the SFE outputs on the variables, first in tabular form (Table 8), based on which we will then construct formulas

Table 8

These functions are called partially defined because they are not defined when. To represent these functions by formulas, they are further defined in such a way as to obtain a simpler form of formulas.

4. Representation of automaton output functions and memory management functions by formulas.

Using methods for minimizing Boolean functions, we build the most economical representation of functions using formulas in the basis:

5. Implementation of SFE and final scheme machine (Fig. 9).

DEFINITION AND METHODS OF SPECIFICATION OF A FINITE MACHINE. SYNTHESIS PROBLEM. ELEMENTARY MACHINES

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

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

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

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

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

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

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

function  : X  Q Q called transition function ;

function  :X  Q Y called output function .

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

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

2. Methods for specifying a finite state machine

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

2.1. Tabular task of the machine

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

q a	q 1		q j		q n
a 1	(a 1 , q 1),  (a 1 , q 1)		(a 1 , q j ),  (a 1 , q j )		(a 1 , q n ),  (a 1 , q n )
a i	(a i , q 1),  (a i , q 1)		(a i , q j ),  (a i , q j )		(a i , q n ),  (a i , q n )
a m	(a m , q 1),  (a m , q 1)		(a m , q j ),  (a m , q j )		(a m , q n ),  (a m , q n )

2.2. Specifying an automaton using a Moore diagram

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

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

LECTURE PLAN

1. Table method

2. Graphical method of specifying the machine

To define a finite automaton S, it is necessary to describe all elements of the set S = (A, X, Y, d, l), i.e. it is necessary to describe the input, output and state alphabet, as well as transition functions d and exits l. In this case, among the set A = (a 0 ,a 1 ,…, a n ) it is necessary to select the initial state a0, in which the automaton is at time t = 0. There are several ways to specify the operation of the machine, but the most commonly used are tabular and graphical.

1. Tabular method

With this method, the Mealy machine is described by two tables: a transition table and an output table.

Transition table

x j\a j
	d(a 0 ,x 1)		d(a n ,x 1)
x m	d(a 0 ,x m)		d(a n , x m)

Output table

x j\a j
	l(a 0 ,x 1)		l(a n ,x 1)
x m	l(a 0 ,x m)		l(a n , x m )

The rows of these tables correspond to input signals x (t), and the columns correspond to states. At the intersection of column a i and row x j in the transition table, the state a s = d[ a i ,x j ], to which the automaton will move from state a i under the influence of signal x j ; and in the output table - the output signal corresponding to this transition y g = l[a i,x j].

Combined table of transitions and outputs of the Mili machine:

x j\a i
	d(a 0 ,x 1)/ l(a 0 ,x 1)		d(a n ,x 1)/ l(a n ,x 1)
x m	d(a 0 ,x m)/ l(a 0 ,x m)		d(a n ,x m )/l(a n , x m )

Setting the transition and output tables completely describes the operation of the finite state machine, since not only the transition and output functions themselves are specified, but also all three alphabets: input, output and state alphabet.

To specify a Moore automaton, one table is required, since in this automaton the output signal is uniquely determined by the state of the automaton.

Marked Moore machine transition table:

y g	l(a 0)		l(a n)
x j\a c
	d(a 0 ,x 1)		d(a n ,x 1)
x m	d(a 0 ,x m)		d(a n , x m )

Automatic Miles

x j\a i
	a 1 /y 1	a 2 /y 3	A 3 /y 2	a 0 /y 1
	a 0 /y 2	a 0 /y 1	A 3 /y 1	a 2 /y 3

Moore machine

x j\x j

In this table, each column is assigned, in addition to the state a i, also an output signal y (t) = l(a(t)), corresponding to this state. The transition table of a Moore machine is called marked because each state is marked by an output signal.

Here are examples of tabular assignments of Mealy and Moore automata:

Using these tables you can find the machine's reaction to any input word. For example.

For Mili machine: For Moore machine:

x 1 x 2 x 2 x 2 x 1…x 1 x 2 x 2 x 2 x 1 …

a 0 a 1 a 0 a 0 a 0 a 1 a 0 a 2 a 4 a 1 a 4

y 1 y 1 y 2 y 2 y 1 y 2 y 1 y 2 y 1 y 2

2. Graphical method of specifying an automaton (specifying an automaton using a graph)

This method is based on the use of directed connected graphs. The vertices of the graphs correspond to the states of the automaton, and the arcs correspond to transitions between them. Two vertices of the graph a i and a s are connected by an arc directed from a i to a s if the automaton has a transition from a i to a s, i.e. a s = d(a i, x j). In a Mealy machine, an arc is marked by an input signal x j that caused the transition, and an output signal y g that occurs during the transition. The state is written inside the circle indicating the vertex of the graph. For example, for the Mealy automaton given above, the graph has the form a), and for the Moore automaton it has the form b).

Elements of automata theory

Plan:

1. The concept of a machine, the principle of operation of the machine

2. Methods for specifying finite state machines

3. General problems of automata theory

Theoretical information

Man has always strived to make his work easier by making some mechanical devices work for himself without his own intervention. At first these were fairy tales, then they began to turn into everyday things. Car, TV, washing machines, entire industries operate without human intervention. Moreover, in most cases human intervention is not required, and in some cases, such intervention can lead to negative phenomena. The concept of “machine gun”, as a device that performs a certain type of action, has long been interpreted by people in exactly this way.

The concept of a machine, the principle of operation of the machine

Concept machine is considered in two aspects:

1. Automatic device, performing some functions without direct human participation. An automatic machine is a real device, understandable why and how it works, at least for those people who designed and manufactured it. A car, a tractor, an airplane, a traffic light, a TV, a telephone - all these are automatic machines. In this aspect, a computer should be understood as an automaton that works according to a program compiled by a person.

2. Automaton – mathematical concept, denoting a mathematical model of real technical devices. An automatic machine is an abstract device; it is not clear why and how it works and, in general, why it can work. In this aspect, the machine is a “black box” that is theoretically capable of carrying out certain actions. From the point of view of mathematics, it is absolutely unimportant what, how and why produces certain actions.

Any automaton must have a certain number of inputs, a certain number of outputs and a certain number of internal states.

Algebraic automata theory is a branch of theoretical cybernetics that studies discrete automata from an abstract algebraic point of view.

The general theory of automata contains various subsections. Depending on the subject of study, it is divided into abstract automata theory and structural automata theory.

Abstract automata theory studies the transitions made by an automaton influenced by input signals, as well as output signals as a result of these transitions.

Subject of study structural theory of automata is the structure of the automaton, as well as the structure of input and output signals, for example, methods of encoding input and output signals, etc.

Definition of finite state machines

Machine- an abstract model of a device operating in discrete time, which processes a finite sequence of input signals and turns them into a finite sequence of output signals (reactions).

During the operation of a finite state machine, a finite number of its internal states are successively changed, and the state of the machine at a certain point in time is uniquely determined by the input and output signals. Such machines represent the basis of all modern computer technology and all kinds of discrete automatic monitoring and control systems.

The concept of an automaton is so abstract that it is difficult to say when a person ever managed without any automatons. Any device fits the definition of an assault rifle, including those that primitive people used to hunt or throw stones to protect their home from the enemy.

Algorithm– understandable and an exact formal instruction to the performer, unambiguously defining the content and sequence of operations that translate a given set of input data into the desired result

It is believed that the first software device created by man was a watch. Clock mechanisms, using a spring that drives gears and cam mechanisms, gears and levers, carry out a number of specific actions. An example of such a clock mechanism is the famous clock at the Central Puppet Theater in Moscow, where it operates twelve fairy-tale heroes located on the dial.

Let us point out several interesting historical facts related to automata as mechanical devices.

1. The German philosopher and alchemist Albert the Great, from 1216 to 1246, created an “iron” servant - an automaton, who performed the duties of a gatekeeper in the house.

2. Astronomer Johann Müller (Regiamontan) (1436-1476) created a mechanical eagle, which, with the tilt of its head and the movement of its wings, greeted the entry into Nuremberg of the Holy Roman Emperor Maximilian II.

3. Mechanic Jacques de Vacanson (1709-1782) - author of the world's first automatic loom. He created the image of a mechanical duck, an exact copy of its living double - it swam, cleaned its feathers, swallowed grains from the palm of its hand. His mechanical flutist, who performed eleven pieces of music, amazed people who lived in those distant years.

4. Russian inventor of the 19th century. A. M. Gamuletsky created an entire mechanical cabinet, which contained many machines he designed. Here, among other things, there was a talking head of a sorcerer and a cupid playing a harp, which captured the imagination of contemporaries.

5. The first primitive adding machine was designed in 1641 by Blaise Pascal. The impetus for the discovery was the torment of his father, the tax inspector, inspector who worked day and night with large calculations. By inventing an adding machine, the eighteen-year-old son saved his father from complex calculations, and gave the world the first calculator that added and subtracted numbers.

6. The first chess machine was built in 1890 by the Spanish engineer Torres Quevedo. Such a machine could only be played in a rook endgame (king and rook against the king).

7. The first computer with automatic control created by Charles Bubbage in 1822. He designed adding machine, which had storage and arithmetic devices. These devices became prototypes of similar devices for modern computers.

Types of machines.

The automaton can be interpreted as a device that performs the processes of receiving, converting and transmitting energy, materials or information in accordance with the program embedded in them, but without direct human participation.

Any machine has its own base sets, which include: input alphabet, output alphabet, set of states of the machine.

Characteristic feature finite state machine is the presence memory, which determines the state of the machine depending on time. The external manifestation of the various states of the machine is its reaction to the same type of influence (signals).

In the operation of finite state machines, an important concept is time.

Machines can be classified according to various criteria.

1. By type of activity - Automata are divided into: information, control and computing.

TOinformation machines include a variety of reference tables, information boards at stadiums, and alarm devices.

TO control machines It is customary to refer to devices for controlling a certain process, including specifically: an elevator, a conveyor, a machine tool, a barrier.

TO computers include microcalculators, computer processors and other devices that perform calculations.

However, strictly speaking, many automata are such complex systems that they are simultaneously computational, control, and information automata.

2. Finite state machines – from the point of view of computer science, these are automata that are discrete information converters. These include converters that contain a finite set of input and finite output signals, as well as a finite set of internal states

3. Digital machines- machines that convert digital information. In such an automaton, input signals are given in the form of a finite set of instantaneous symbols: their duration is so short that it can be neglected. In a fixed time, the input symbols are converted, and the output undergoes an abrupt transition from one state to another state.

4. Abstract automata - displaying a set of words of the input alphabet Xin set of words of the output alphabet Y.

There is an abstract automaton:

~ Mathematical model,

~ Algorithm actions of some transformation of code sequences,

~ Law transforming the input alphabet into the output one.

5. Synchronous and asynchronous machines. Depending on whether the input signal and the state change signal are received simultaneously or sequentially, the machines are divided into synchronous and asynchronous machines.

In synchronous machines The duration of the input signals and the transition times are coordinated with each other. They are used in computer systems, automated control systems, etc.

In asynchronous machines The duration of the input signals and the timing of the transitions are not consistent with each other. They depend on external sources - various events, and sampling interval is variable (for example, in combination locks). In asynchronous machines, the next change in the values ​​of the input signals can occur only if the transition process caused by the previous change in these signals has ended.

6. Automata are divided into finite and infinite automata. If the classification is based on Memory, then the difference lies in whether the machine has final or infinite number of internal states.

Under the endless An automaton is usually understood as a certain mathematical idealization of the idea of ​​an automaton, which has an infinite number of states. The memory of such an automaton can potentially increase indefinitely. For example, the famous abstract automata of Post and Turing are infinite automata, but the computer itself or its individual parts are finite automata.

7. Automata are divided into deterministic and probabilistic automata. If the classification is based on random selection mechanism, Then a distinction is made between deterministic and probabilistic (stochastic) automata.

In deterministic automata behavior and structure at each moment in time are uniquely determined by the current input information and the state of the machine itself at the previous moment in time.

In probabilistic automata, this dependence is also associated with some random choice.

Probabilistic An automaton is a discrete information converter, the functioning of which at each moment of time depends only on memory states and is described by statistical laws.

8. Universal automatic machine. In automata theory it has been proven that to perform various transformations of information it is enough to construct universal an automatic machine with the help of a program and appropriate coding, capable of solving any problem.

The mathematical model of a digital automaton with one input is specified by five objects:

X- finite set of input symbols, input alphabet:

X= (x 1 (t), x 2 (t), ..., x n (t));

Y- finite set of output symbols, output alphabet:

Y=(y 1 (t), y 2 (t), ..., y n (t));

Q~ finite set of automaton states:

Q= (q 0 (t), q 1 (t), q 2 (t), ..., q n (t)), q 0- initial state;

δ(q, X) - function of transition of the machine from one state to another: ( Q X X)®Q;

λ(q, X) ~ machine output function: ( Q x X) ® Y.

Thus, the state machine C= (X, Q, Y, δ, λ.) is determined by recurrence relations

q(0) = q 0 , q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

t is a discretized moment in time or is it an image of a monotonic function t:. T® N, and T - ordinary continuous time, N is the set of natural numbers.

All working hours T is divided into a finite number of intervals, at the boundary of which the state of the machine changes. In this case, t(Г 0) - shows the number of changes that occurred before the moment of time Г 0.

An example of sampling is ordinary cinema: time is divided into intervals of 1/24 sec. The human eye perceives the succession of discrete frames as continuous movement.

9. Synchronous automata are divided into Mealy automata and Moore automata. Depending on the way to organize the output function synchronous machines are divided into Mili machines ( type I automata) and Moore automata (type II automata).

In Mili machines- output signal y(t) x(t) and condition q(t- 1) the machine at the previous point in time (t- 1). The mathematical model of such automata is the system of equations:

q(t) = δ (q(t-1), x(t)) and y(t) = λ (q(t-1), x(t)),

In Moore's machines output signal y(t) uniquely determined by the input signal x(t) and condition q(t) at a given time t. The mathematical model of such machines is the system:

q(t) = δ (q(t-1), x(t)) and y(t) = λ (q(t)),

In such machines, the output function depends only on the states of the machine at a given time and does not depend on the input signal. Thus, the input string of such an automaton is read once from left to right, scanning the characters one by one. At a certain point in time, the finite state machine is in a certain internal state, which changes after reading the next character. The new state can be characterized by the read symbol and the current state.

10. Combination machines– there are automata in which the output symbol does not depend on its state and is determined only by the current input symbols, i.e. in this automaton all states are equivalent. In such an automaton, the transition function is degenerate; it is fundamentally unimportant and remains unchanged during operation. Therefore, a minimal combinational automaton has only one state.

11 Logical automata - there are automata whose input alphabet consists of 2 t binary length sets T, and the output is from 2 n binary sets of length P. For logical combinational automata, the output function has the form of a system P logical functions from T variables.