Definition and methods of specifying finite automata. Definition of State Machines

It's obvious that k,r,s respectively equal to the number of digits in the binary representation of numbers t, p, r. For example, if t - 5, P= 17, p = 3, then k= 3, r= 5, s = 2.

2. Encoding the states of input and output symbols of the source
machine.

For each q j Q one-to-one associate a binary sequence of length r- binary code = z 1 z 2 z r . Similarly to each a i X and b k Y we assign one-to-one binary sequences =x 1 x 2 x k ; =y 1 y 2 y s .

Note that the encoding of states, input and output symbols can be done in many ways. However, some sequences (codes) may not be used.

3. We make the following table:

This table contains k+r+r+s columns and 2 k + r lines. First k+r columns are written out all sets of length k+r. Each such set corresponds to a pair (), where is a possible code of some state, the code of the input symbol.

4. Filling in the last columns in the table (previous step).

For each pair (a i ,q j), where a i X; q j Q , find the code and . From the automaton table (or Moore diagram) we determine and \|/(a; q) = Y. Then we find code = " 1 " 2 ... ",. and code .

To the table row corresponding to the set

add the set

5. Definition of a system of Boolean functions.

After completing the previous step, it may turn out that all the rows in the table are filled. This will happen if at least one of the numbers m, n is not a power of 2. Thus, the functions will not be completely defined - on some sets their values ​​are not defined. Then we redefine them arbitrarily. As a rule, the extension of functions is carried out in such a way that the resulting fully defined functions satisfy certain optimality conditions, for example, they can be represented by minimal DNFs.

After this step is completed, the original automaton will define the system of fully defined Boolean functions

3.2 Initial languages.

They describe the automaton at the behavioral level. Primary languages ​​include:

1) languages ​​of logical circuits and a graph of diagrams of algorithms;

2) the language of regular expressions of the algebra of events;

3) formal and automatic grammars.

If description (4) of a fully defined automaton in standard form is given, then for any initial state of the automaton s(0) and sequences of input symbols v(0)v(1)v(2)…v(t) it is possible to calculate the response of the automaton in the form of a sequence of output symbols w(0)w(1)…w(t).

Examples.

Example 1. Newspaper SELLER machine receives coins in denominations of 1 ruble and 2 rubles. If the sum of coins is equal to 3 rubles, then the machine gives out a newspaper. If the amount is more than 3 rubles, then the machine returns all the money. Let us introduce the notation for input and output symbols and states of the automaton.

Input characters:

v 1 - a coin worth 1 ruble is lowered;

v 2 - a coin worth 2 rubles is omitted.

Output characters:

w 1 - message "Amount of 1 ruble accepted.";

w 2 - message "Amount of 2 rubles accepted.";

w 3 - issuance of a newspaper;

w 4 - money back.

Machine states:

s 0 - the amount of 0 rubles is accepted. (initial state);

s 1 - the amount of 1 ruble is accepted;

s 2 - the amount of 2 rubles is accepted.

We represent the transition function in table 2, and the output function in table 3.

The same automaton can be specified in the form of a marked digraph, the vertices of which correspond to the states of the automaton, and the arcs correspond to transitions (Fig. 3).

Below is an example of the reaction of the SELLER automaton to the input sequence v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:

Example 2 For the automaton SELLER considered above, it is possible to construct an equivalent Moore automaton, characterized by a table of transitions/outputs (Table 4).

Table 4

Figure 4 shows the graph of transitions/outputs of the SELLER automaton corresponding to Table 4. The initial state of the equivalent Moore machine includes the input symbol v(0). Therefore, it is necessary to shift the stream of input characters: .

Let us describe the behavior of a parent who sent his son to school. The son brings deuces and fives. The father does not want to grab the belt every time, as soon as the son receives another deuce, and chooses a more subtle tactic of education. It is convenient to define an automaton by a graph in which the vertices correspond to states, and the edge from state s to state q, labeled x/y, is drawn when the automaton from state s under the influence of an input signal x passes to state q with an output reaction y. The graph of the automaton simulating the smart behavior of the parent is shown in Fig. 5.

Rice. 5. Automaton describing the behavior of a "smart" father

This automaton has four states (s0, s1, s2, s3) and two input signals - grades received by the son at school: (2,5). Starting from the initial state s0 (it is marked with an input arrow), the automaton, under the influence of input signals, passes from one state to another and issues output signals - reactions to inputs. The outputs of the automaton (y0,...,y5) will be interpreted as actions of the parent as follows:

y0: - take a belt;

yl: - to scold the son;

y2: - to calm the son;

uZ: - hope;.

y4: - rejoice;

y5: - rejoice.

A son who received the same grade - a deuce, expects a completely different reaction from his father at home, depending on the background of his studies. The father remembers how his son studied before, and builds his upbringing taking into account his previous successes and failures. For example, after the third deuce in history 2,2, 2 sons will be met with a belt, and in history 2, 2, 5, 2 they will be reassured. Each history determines the current state of the automaton, and some input histories are equivalent (namely, those that bring the automaton to the same state): history 2, 2, 5 is equivalent to the empty history that corresponds to the initial state.

The current state of the automaton represents everything that the automaton knows about the past in terms of its future behavior - reactions to subsequent inputs. This history in a concentrated form is determined by the current state, and all future behavior of the automaton, as its reaction to subsequent input signals, is determined. namely the current state, but not the way the automaton came to it.

So, a state machine is a device that operates at discrete times (cycles). At the input of the finite automaton in each cycle, one of the possible input signals is received, and an output signal appears at its output, which is a function of its current state and the received input signal. The internal state of the automaton also changes. The trigger points (cycles) are determined either by forced clocking clock signals, or asynchronously, by the onset of an external event - the arrival of a signal.

Let us define the finite automaton formally.

In addition to the graphical representation for the automaton, you can also use a tabular one, setting the functions of transitions and exits in the form of tables. The example automaton will be represented by the following tables.

table 5, a defines a transition function like this:

and tab. 5b defines the function of the outputs : .(s0, 2) = y2; (s2, 5) = y3; ....

The representation of a finite automaton is actually reduced to a description of the automaton functions that define it.

There are three ways to define finite automata:

· Tabular (matrices of transitions and exits);

Graphical (using graphs);

· Analytical (using formulas).

Analytical method– the automaton is given by a system of equations. It follows from such a system that for a finite number of possible internal states, the number of possible values ​​of automaton functions also turns out to be finite. An example of such a task is the system of equations that define Mealy automata and Moore automata

tabular way. A table of the state of the automaton is compiled for the transition function - δ and the output function. Wherein:

the columns of the table correspond to the elements of the input alphabet x,

table rows correspond to states (elements of a finite set Q).

The intersection of the i-th row and the j-th column corresponds to the cell (i, j), which is the argument of the functions 8 and λ of the automaton at the moment when it is in the state q i at its entrance - the word x j , and in the corresponding cell we write the values ​​of the functions 8 and λ. Thus, the whole table corresponds to the set Q X x.

When filling in the transition table, each cell is uniquely determined by a pair of symbols: the symbol of the next state and the symbol of the output signal.

In practice, automaton functions are given by two finite tables, respectively named transition matrix and conclusion matrix. In this case, the rows are denoted by the letters of the input alphabet, and the columns by the letters of the internal alphabet (symbols encoding the internal state of the automaton).

In the transition matrix, at the intersection of row x k and column q r, the value of the transition function δ(q i , X) and inference functions λ(q, X). In some cases, both tables are combined into one table.

Graphic way.

An automaton is specified using a graph, diagram, graph, etc. An assignment using a directed graph is a more convenient and compact form of describing an automaton.

automaton graph contains

· peaks, corresponding to the state q iОQ,

· arcs, connecting vertices are transitions of the automaton from one state to another. On the arcs, it is customary to indicate pairs of input and output signals - transition signals.

If the automaton passes from the state q 1 into a state q2 under the influence of several input signals, then this variant will be represented on the corresponding arc of the graph through a disjunction. To represent the automaton, bipolar graphs with distinguished initial and final states are used.

Development of the "capacitance measuring instrument" scale

Fig.2.5. Graph of the scale of the device for measuring capacitance

Conclusion

Since the use of generators with oscillatory circuits (RC type) for generating high-frequency oscillations does not satisfy, an LC type circuit was taken for the developed generator (a three-point circuit with autotransformer coupling was taken as a phasing circuit, the active element is a transistor).

In the theoretical part of this course work, the elements of LC-type generators were considered. The classification of LC-type generators, their purpose, as well as various generator circuits were also considered. As well as the technical characteristics of the generator elements.

In the practical part, the topic concerning encoders, decoders, their purpose was disclosed, and electrical functional and electrical circuit diagrams of encoders and decoders were also designed. The theme of Karnot maps was revealed. The “b” segment of the seven-segment indicator was also developed. A state machine was developed for the scale of the instrument for measuring capacitance, as well as a graph for it.

Basic definitions of n A finite automaton is a system M =(А, B, S, y) in which n n n А = (а 1, . . . , am) is a finite input alphabet, B =(b 1, . . . , bk ) - finite output alphabet, S =(s 1, . . . , sn) - finite state alphabet, : A S S - transition function, y: A S B - output function. n If in the automaton M one state is selected, called the initial state (usually it will be considered that this is s 1), then the resulting automaton is called initial and is denoted by (M, s 1). n There are two ways to define an automaton: Automaton table, transition diagram

Automaton table n 1) 2) 3) 4) Example: set the automaton for reading the word "001" if the characters "0" and "1" are input. Input alphabet A=(0, 1) Output alphabet A=(Y, N) State alphabet S=(s 0 "" , s 1 " 0" , s 2 " 00" s 3 "001" ) Automatic table in two ways. 1) Rows are the states of the automaton. The columns are the input symbols. At the intersection of rows and columns, functions are indicated, y. 2) S, A, y are given by columns. Exercise 25 Build an automaton to search for the word CAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1 , N S 0, N S In y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3

Transition diagram n An oriented multigraph, called a transition diagram, is a multigraph, transition or graph corresponding to states. If (Si, aj)=Sk, y(Si, aj)=bl, then from the vertex Si to the vertex Sk there is an arc on which is written (aj, bl) n At each vertex si, the correctness conditions are: 0 1 S 0 "" S 1, N S 0, N S 1 "0" n Vertices, y S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1, N S 0, N 1, N fulfilled 1) for any input letter aj has an arc outgoing from si, on which aj is written (completeness condition); 2) any letter aj occurs only on one edge outgoing from si (consistency or determinism condition) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Automata and input words n For a given automaton M, its functions are M and y. M can be defined not only on the set A of all input letters, but also on the set A* of all input words. n For any input word = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . . , ajk-1), ajk).

Example: Automata and input words Example: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2 , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) \u003d N, y S 2, N S 3, Y S 3 "001" S 1, N S 0, N

Automaton mapping n Let us fix an initial state S 0 in M ​​and for each input word = a 1 a 2. . . ak we assign a word in the output alphabet: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1. . . ak). (3 a) n This correspondence, which maps input words to output words, is called an automaton mapping n If the result of applying an operator to a word is an output word, then this will be denoted accordingly by M() = .

Example: Automatic Mapping Let's assign the input word = 0101 to the word in the output alphabet: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N, y 0 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y 1 S 3 "001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

Automaton display properties 1) words and = M() have the same length: | | = | | (property of preservation of length); 2) if = 1 2 and M(1 2) = 1 2, where | 1| = | 1|, then M(1) = 1; in other words, the image of a segment of length i is equal to the segment of the image of the same length.

Types of automata n The general model of a finite automaton (S-finite), which was considered earlier, is called a Mealy automaton. n An automaton is called autonomous if its input alphabet consists of one letter: A=(a). All input words of the autonomous automaton have the form aa. . . a. n A finite automaton is called a Moore automaton if its output function depends only on states, i.e., for any s, ai, aj y(s, ai) = y(s, aj). The output function of the Moore automaton is naturally one-argument; it is usually denoted by a letter and is called the marks function. In the graph of the Moore automaton, the output is written not on the edges, but at the top.

Moore automata n Theorem: For any Mealy automaton there exists an equivalent Moore automaton. n When studying the possibilities of automata, it is sufficient to use Moore automata. This is convenient because the Moore automaton can be viewed as an automaton without outputs, the states of which are labeled in various ways.

An example of an autonomous automaton SA a S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 S S S S S A=(a), B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S9)

Indistinguishable States n Let M and T be two automata with the same input and output alphabets. A state s of an automaton M and a state r of an automaton T are said to be indistinguishable if for any input word M(s,) = T(r,). n The automata M and T are called indistinguishable if for any state s of the automaton M there is a state r of the automaton T that is indistinguishable from it and, conversely, for any r from T there is an indistinguishable state s from M. n Indistinguishable states are called equivalent

Minimal automaton n The transition from an automaton M to an equivalent automaton is called an equivalent transformation of an automaton M. n One can pose various problems of finding automata that are equivalent to a given automaton and have given properties. The most studied among such problems is the problem of minimizing the number of states of an automaton: among automata equivalent to M, find the automaton with the smallest number of states - the minimal automaton.

Aspects of the “work” of automata n Two main aspects of the “work” of automata can be distinguished: 1) automata recognize input words, i.e. answer the question of whether the input word belongs to a given set (these are recognizer automata); 2) automata transform input words into output words, i.e., they implement automaton mappings (transformer automata).

TA in the framework of metamathematics n The subject of the theory of algorithms and formal systems in the framework of metamathematics - what objects and actions on them should be considered precisely defined, what properties and capabilities combinations of elementary actions have, what can and cannot be done with their help. n The main application of the theory of algorithms is the proof of the impossibility of an algorithmic (ie, exact and unambiguous) solution of certain mathematical problems.

Algorithm n An algorithm is a prescription that uniquely specifies the process of transforming the initial data to the required result n The transformation process itself consists of elementary discrete steps, the application of which a finite number of times leads to the result

Basic types of algorithms n The theory of algorithms is a metatheory that studies various (qualitative and quantitative) properties of algorithms. n For the study of qualitative properties, 3 main types of algorithms are defined: 1) Recursive functions 2) Turing machine 3) Canonical Post systems and normal Markov algorithms.

The simplest recursive functions n S 1(x) = x+1 - the function depends on one variable x, and is equal to x+1. n On(x 1…xn) =0 - function depending on n variables and always equal to 0. n Imn(x 1…xn) = xm - function depending on n variables and always equal to the value of variable xm

Primitive recursion n The function f(x 1…xn+1) is obtained by the primitive recursion algorithm from the functions g(x 1…xn) and h(x 1…xn+2) if f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), where z=f(x 1, …xn, y) (2) Function f is called primitive recursive , if it can be obtained from the simplest functions S 1, On, Imn by a finite number of superposition and primitive recursion operations.

Example n To prove that a function is primitive recursive: 1) According to equations (1) and (2), explicitly define the functions g() and h(). 2) Show that g() and h() are the simplest functions S 1, On, Imn, or primitive recursive functions proven earlier. Exercise 26: Prove that the function f(x, y) = x+y is primitive recursive Church's thesis: The class of algorithmically computable numerical functions coincides with the class of all recursive functions.

Turing machine n Turing machine contains: n 1) External memory - a tape of n cells. Each i-th cell is in the state ai. The alphabet of states is set. The tape can be endless in both directions. Empty states are omitted. n 2) The internal memory of the machine - the device is currently in the state qi. The alphabet of the internal state is given. Initial state q 1, final q 0 or qz. n 3) Pointer - points to the current cell and moves along the tape. n 4) Control device - reads the character of the cell pointed to by the pointer. In accordance with the program, changes the state of the cell and moves the pointer.

The state and program MT n The state of the Turing machine is called the word n ​​n n n a 1…ak-1 qi ak…ar , formed by inserting the symbol of the internal state in front of the monitored cell. The Turing machine program is a set of commands that can be executed by the machine qi aj qi' aj' D, where qi is the internal state of the machine aj is the state of the monitored cell qi' is the new state of the machine aj' is a new character written to the monitored cell D = ( L, R, E) - characters symbolizing the shift of the pointer by one cell to the left, to the right and the absence of a shift, respectively.

Example MT Exercise 27: Find the final state of the Turing machine Initial alphabet: A = (0, 1) Internal state alphabet: Q = (q 0, q 1, q 2) Program: ( 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Initial word: q 111

Example MT Control 28 Find the final state of the Turing machine Initial alphabet: A \u003d (0, 1, ) Alphabet of the internal state: Q \u003d (q 0, q 1, q 2, q 3) Program: ( 1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L) A) Initial word: q 111 1 B) Initial word: q 11 111

Turing's thesis Turing's thesis: for each algorithm A, a Turing machine can be built that, given the same initial data, gives the same results as algorithm A. n If 1 q 1 2 1 qz 2, then we will say that the machine T processes the word 1 2 into the word 1 2, and denote it T(1 2) = 1 2. n The notation T() is the designation of the machine T with initial values.

Normal Markov Algorithms n Normal Markov Algorithms (NAM) transform words of finite length into each other using substitution. n Task NAM Substitution Alphabet u v Final substitution u v n Control 29 A normal Markov algorithm is specified: Alphabet is the alphabet of the Russian language. Substitution scheme (I U, L U, S M, V B, R T, T R, O X, N A) n Initial word SLON. n Find end word.

Estimating the complexity of algorithms n Suppose that the functions f(n) and g(n) measure the performance of two algorithms, they are usually called time complexity functions. We will say that the order of growth of the function f(n) is not greater than that of g(n) if there exists a positive constant C such that | f(n) |

Efficiency of algorithms A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 30 s 20.4 ms 0.28 h 4*1017 centuries 0.56 h 11.6 days 10176 centuries 1000 ms 0.83 h 1 ms

Theory of Algorithms n Theory of Algorithms - classifies problems by complexity. In this case, only recognition tasks are classified. n A recognition task is a task that answers the question: does the input data have some property. In our case: the input data is a graph, a property - is the graph Hamiltonian?

Classes P and NP n Complexity class P: there is an algorithm A that solves the problem in polynomial time. n Complexity class NP - there is an algorithm A that checks the proposed solution in polynomial time. n The Hamiltonian cycle problem is to find out whether a given graph G has a Hamiltonian cycle belongs to the NP-class.

Examples of NP problems n Boolean satisfiability problem: to find out from a given Boolean formula whether there is a set of variables included in it that turns it into 1. n Clique problem: to find out from a given graph whether there are cliques (complete subgraphs) of a given size in it . n The problem of the existence of a Hamiltonian cycle in a graph. n Existence of an integer solution to a system of linear inequalities.

Possibility of solving NP problems by enumeration of n Initially, the solution is not known. Therefore, it is important that any problem related to the NP-class can be solved in exponential time by enumeration of all possible combinations of n, which happens in the algorithm for finding the Hamilton cycle

Relation between Р and NP n Any task from P belongs to NP. n Thus, class NP includes class P. At this time, it is not known whether classes P and NP are the same, but most experts believe that they are not.

Ratio of P and NP n If it turns out that P = NP 1) NP tasks will be solved in a reasonable time. 2) There are a number of problems that intentionally use problems of exponential complexity (i.e., assuming that the problem cannot be solved). For example, In cryptography, there is a section on public key encryption, which is almost impossible to decrypt. If suddenly P = NP, then many secrets will cease to be such.

NP-Complete Problems n The most compelling reason to believe that P ≠ NP is the existence of NP-complete problems. n Informally!!!, Problem Q reduces to Problem Q′ if Problem Q can be solved in polynomial time for any input, assuming that the solution of Problem Q′ for some other input is known. For example, the problem of solving a linear equation is reduced to the problem of solving a quadratic equation.

NP-complete problems n An NP-complete problem is a problem from the class NP to which any other problem from the class NP can be reduced. n NP-complete problems form a subset of the "hardest" problems in the NP class. If for any NP-complete problem a polynomial solution algorithm is found, then any other problem from the NP class can be solved in polynomial time. n All listed NP-problems are NP-complete. Including the problem of the Hamilton cycle.

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

Lecture 31 Synthesis task. Elementary automata

Lecture 30

SYNTHESIS PROBLEM. ELEMENTARY AUTOMATES

Lecture plan:

1. Definition of a finite automaton.

2. Methods for defining a finite automaton.

1. The problem of automata synthesis.
2. Elemental machines.
3. The problem of the completeness of an automaton basis.
4. Canonical method for automaton synthesis.

1. State machine definition

SFE do not take into account the fact that real devices operate in time. Compared to the SFE, the finite automaton 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.

First, it is assumed that the input and output of the automaton can be in only one of a finite number of different states at any time. If a real transducer has a continuous input signal, then to describe it using a finite automaton, it is necessary to quantize this signal. In the formal definition of the automaton, the 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.

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

The operation of the machine is presented as follows.

The input of the automaton 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 sequence depends on the internal structure of the automaton. Note that, unlike SFE, 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 prehistory. The prehistory is taken into account 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 state machine is a set of five objects

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

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

a finite set called the alphabet of internal states;

automaton transition function: ; this function assigns a state to each “input-state” pair;

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

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

1. Ways to define a state machine

1. Tabular way of setting. Since for functions both the scope and values ​​belong to a finite set, they are specified using tables.

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

Table 1. Jump table Table 2. Output table

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

2. Graphical way of setting. A transition-output diagram is used. It is a directed multigraph in which each internal state of the automaton corresponds to a vertex. Transitions of the automaton from state to state are depicted by arrows, on each of which the input symbol that causes this transition and the output symbol generated by the automaton are written.

Fig.1 Diagram of transitions-outputs

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

The automaton is in state 1 if a carry occurs during the addition of previous digits, and in state 0 otherwise. The transition-output diagram is shown in fig. 2.

1. The problem of automata synthesis

By analogy with the problem of SFE synthesis, one can pose a synthesis problem for automata. There is an unlimited set of basic automata. It is required to assemble an automaton with a predetermined functioning. At the same time, the task of synthesis faces certain problems.

Assume that you need to connect the output of the automaton to the input of the automaton. This is possible under the condition, since otherwise the second automaton will not understand the signals coming from the first one. 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. An arbitrary injective mapping will be called an 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 automaton at the moment of time, respectively. Then the law of operation will be presented in the form

The automaton obtained after coding is called a structural automaton. We assume that the structural automaton has binary inputs, binary outputs, and the internal state of the automaton is given by a binary word of length. On 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 from structural automata it is similar to SFE.

2. Let's write relations (2) in "coordinates":

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

1. Elementary automata

We single out the simplest structural automata and give them a name.

Note first 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 automaton have one binary input and one binary output coinciding with the internal state: :

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

Table 3

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 both zero and one occur in each column of Table 3. There are only four such tables.

Table 4 Table 5

Table 6 Table 7

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

The automaton given by Table 4 is called a delay or -trigger:

that is, this automaton delays the signal by one cycle.

The automaton specified by Table 5 is called a trigger with a counting input or a -trigger. The state of the automaton changes to the opposite if the input is 1, and remains unchanged if the input is 0:

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 1s has been received at the input of the automaton. If in state 1, then is odd. Thus, the -trigger counts the number of units at the input, but since it has only two states, it counts up to two.

In the physical implementation of triggers, two outputs are used: direct and inverse (Fig. 5). If we swap them, then from the -trigger we get the automaton specified by Table 7, and from the -trigger the automaton specified by Table 6.

1. The problem of the completeness of an automaton basis

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

Efforts by 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 consider the most popular of them.

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

Proof. Consider an arbitrary automaton given by relations (2) and describe its scheme of the indicated automata, called the canonical structure (Fig. 6).

The scheme consists of two parts.

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

then it means that the automaton is in the state.

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

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

1. binary word output signal of the automaton, which is implemented according to formulas (3);
2. a binary word that enters the inputs of triggers in the storage part and controls the memory of the automaton.

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

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

The -triggers or -triggers used in the canonical scheme 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 -trigger, since the state in which the -trigger is set is equal to the input signal. For -trigger: when, 0 must be applied to the input so that the state does not change; at 1, so that the trigger "flips".

So, or in vector form

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

The theorem has been proven.

1. Canonical method for automaton synthesis

Let's consider this method on a concrete example.

Example. An automatic machine is installed on the conveyor along which parts of two types move, the task of which is to sort the parts in such a way 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 elements "AND", "OR", "NOT".

The automaton synthesis 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 its skip. 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 automaton moves cyclically through these states without changing the state when an unsuitable part arrives. The transition-output diagram is shown in fig. 7.

2. Coding of alphabets.

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

Input Output Status

3. Construction of the canonical structure of the automaton.

The canonical structure of the automaton being developed is shown in fig. eight.

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

Table 8

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

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

Using the methods of minimizing Boolean functions, we build an economical representation of functions, if possible, by formulas in the basis:

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

DEFINITION AND METHODS OF DESIGNATION OF FINITE AUTOMAT. SYNTHESIS PROBLEM. ELEMENTARY AUTOMATES