Methods for specifying finite state machines. Definition of finite state machines Finite state machines, methods of setting and basic properties

As stated earlier, Y (x,q) specifies the order of transformation of input symbols and the state of the machine at the previous clock cycle into the state at the next one, a Q (x,q) - transforming input symbols and the state of the machine at the current clock cycle into an output symbol. If q 0 is the initial state of the machine, and i- cycle number, then its operation is described by the system:

These ratios are called systems of canonical equations finite state machine. You can use them starting from q 0 , sequentially find all subsequent states of the machine and output symbols.

There are two types of machines - initials And uninitial. IN In initial automata, the initial state is fixed (i.e. they always start working from the same state q 0). In non-initial automata, any of the set can be chosen as the initial state Q; This choice determines the further behavior of the machine.

The representation of a specific finite automaton actually comes down to the description of the automaton functions that define it. From system (9.3) it follows that for a finite number of possible internal states, the number of possible values ​​of the automaton function also turns out to be finite. They can be described in various ways, the most common of which is tabular and with the help diagrams.

IN tabular method automata functions are specified by two finite tables called respectively transition matrix And output matrix. In these tables, rows are designated by letters of the input alphabet, and columns by letters of the internal alphabet (symbols encoding the internal state of the machine). In the transition matrix at the intersection of a row (xk) and column (qr) the values ​​of the function Y are placed ( q r, x k), A in the output matrix - the values ​​of the function Q (q r , x k).

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

Automatic table n 1) 2) 3) 4) Example: set an automaton to read the word “001” if the input characters are “0” and “1”. 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. is specified by 1) Lines – states of the machine. Columns are input symbols. At the intersection of rows and columns, functions, y, are indicated. 2) S, A, y are specified by columns. Exercise 25 Build an automaton to search for the word KAKADU 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 transition diagram called a graph is a multigraph, transitions or graph correspond to states. If (Si, aj)=Sk, y(Si, aj)=bl, then an arc is drawn from vertex Si to vertex Sk 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 are fulfilled 1) for any input letter aj has an arc emanating from si, on which aj is written (completeness condition); 2) any letter aj occurs only on one edge coming out of 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) = N, y S 2, N S 3, Y S 3 “001” S 1, N S 0, N

Automatic mapping n Let us fix the initial state S 0 in M ​​and each input word = a 1 a 2. . . ak we match the 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, mapping 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 we will denote this accordingly M() = .

Example: Automatic mapping Let's match the input word = 0101 to a 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

Properties of automatic mapping 1) words and = M() have the same length: | | = | | (length conservation property); 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 a segment of the image of the same length.

Types of automata n The general model of a finite automaton (S-finite), which was discussed 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 are of the form aa. . . A. n A finite automaton is called a Moore automaton if its output function depends only on states, that is, for any s, ai, aj y(s, ai) = y(s, aj). The output function of the Moore machine is naturally one-argument; it is usually denoted by a letter and called the mark function. In the graph of a Moore machine, the output is written not on the edges, but at the vertex.

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

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, S 9)

Indistinguishable states n Let M and T be two automata with identical input and output alphabets. State s of the automaton M and state r of the automaton T are said to be indistinguishable if for any input word M(s,) = T(r,). n Automata M and T are called indistinguishable if for any state s of the automaton M there is an indistinguishable state r of the automaton T 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 You can pose various problems about finding automata equivalent to a given one and having 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 an automaton with the smallest number of states - a 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, that is, they answer the question whether the word given as input belongs to a given set (these are automata recognizers); 2) automata convert input words into output words, i.e., implement automata mappings (automatic converters).

TA within the framework of metamathematics n The subject of the theory of algorithms and formal systems within the framework of metamathematics - which 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 (i.e., exact and unambiguous) solution to certain mathematical problems.

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

Main types of algorithms n Algorithm theory is a metatheory that studies various (qualitative and quantitative) properties of algorithms. n To study 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 - a function depending on n variables and always equal to 0. n Imn(x 1…xn) = xm - a function depending on n variables and always equal to the value of the 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 primitively recursive, it is necessary: ​​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 previously proven primitive recursive functions. 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 The Turing machine contains: n 1) External memory – a tape of n cells. Each i-th cell is in state ai. The alphabet of states is specified. The tape can be endless in both directions. Empty states are omitted. n 2) Internal memory of the machine - the device is currently in the qi state. The alphabet of the internal state is specified. Initial state q 1, final state q 0 or qz. n 3) Pointer – points to the current cell and moves along the tape. n 4) Control device – reads the symbol of the cell to which the pointer points. In accordance with the program, changes the state of the cell and moves the pointer.

State and program MT n The state of a Turing machine is called the word n ​​n n n a 1…ak-1 qi ak…ar , formed by inserting an internal state symbol before the cell being observed. A Turing machine program is a set of commands that a machine qi aj qi' aj' D can execute, where qi is the internal state of the machine aj is the state of the cell being monitored qi' is the new state of the machine aj' is the new symbol written to the cell being monitored D = ( L, R, E) – symbols symbolizing the shift of the pointer by one cell to the left, right and no shift, respectively.

Example MT Exercise 27: Find the final state of a 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 ) Start word:q 111

Example MT Exercise 28 Find the final state of a Turing machine Initial alphabet: A = (0, 1, ) Internal state alphabet: Q = (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, which, 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 machine T processes 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 the original values.

Normal Markov Algorithms n Normal Markov algorithms (NAMs) transform words of finite length into each other using substitution. n Task NAM Alphabet Substitutions u v Final substitution u v n Exercise 29 The normal Markov algorithm is given: Alphabet - the alphabet of the Russian language. Substitution scheme (Y U, L U, S M, V B, R T, T R, O X, N A) n Initial word ELEPHANT. n Find the final word.

Estimating the complexity of algorithms n Let us assume that the functions f(n) and g(n) measure the efficiency of two algorithms, they are usually called time complexity functions. We will say that the order of growth of the function f(n) is no greater than that of g(n) if there is 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 1,024 s 100 ms 30 s 20.4 ms 0.28 h 4*1017 centuries 0.56 hours 11.6 days 10176 centuries 1000 ms 0.83 hours 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: input data - graph, property - is the graph Hamiltonian?

Classes P and NP n Complexity class P: there is an algorithm A, problem solver 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 consists of finding out whether a given graph G has a Hamiltonian cycle and belongs to the NP class.

Examples of NP problems n The satisfiability problem for Boolean functions: find out from a given Boolean formula whether there is a set of variables included in it that turns it to 1. n Clique problem: from a given graph find out whether it contains cliques (complete subgraphs) of a given size . 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 brute force n Initially the solution is not known. Therefore, it turns out to be important that any problem belonging to the NP class can be solved in exponential time by searching through all possible combinations n Which is what happens in the algorithm for finding a Hamilton cycle

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

Relationship between P and NP n If it turns out that P = NP 1) NP problems will be solvable in a reasonable time. 2) There are a number of problems that deliberately 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 practically impossible to decrypt. If suddenly P = NP, then many secrets will cease to be such.

NP–complete problems n The most serious 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 the solution to problem Q′ for some other input is known. For example, the problem of solving linear equation reduces 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 a polynomial solution algorithm is found for any NP-complete problem, 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 about the Hamilton cycle.

The representation of a finite automaton actually comes down to the description of the automaton functions that define it.

There are three ways to define finite state machines:

· Tabular (matrices of transitions and outputs);

· Graphic (using graphs);

· Analytical (using formulas).

Analytical method– the automaton is specified by a system of equations. From such a system it follows that for a finite number of possible internal states, the number of possible values ​​of automata 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 method. A state table of the machine is compiled for the transition function – δ and the output function. Wherein:

· table columns correspond to elements of the input alphabet X,

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

The intersection of i-i row and j-th column correspond to cell (i, j), which is the argument of functions 8 and λ of the automaton at the moment when it is in the state q i at its input is a word xj, and in the most appropriate cell we write the values ​​of the functions 8 and λ. Thus, the entire table corresponds to the set Q X X.

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

In practice, automata functions are specified by two finite tables, called respectively transition matrix And output matrix. In this case, the rows are designated by the letters of the input alphabet, and the columns by the letters of the internal alphabet (symbols encoding the internal state of the machine).

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 output functions λ(q, X). In some cases, both tables are combined into one table.

Graphic method.

The automaton is specified using a graph, diagram, graph, etc. Specifying using a directed graph is a more convenient and compact form of describing the automaton.

Automaton graph contains

· Peaks, corresponding to the condition q iÎQ,

· Arcs, connecting vertices are transitions of the automaton from one state to another. It is customary to indicate pairs of input and output signals – transition signals – on the arcs.

If the machine goes from the state q 1 in a state q 2 under the influence of several input signals, then on the corresponding arc of the graph this option will be represented through a disjunction. To represent an automaton, two-pole graphs with distinguished initial and final states are used.

Development of a scale for a “device for measuring capacitance”

Fig.2.5. Scale graph of a capacitance measuring device

Conclusion

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

In the theoretical part of this course work 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 technical characteristics of generator elements.

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

Baranov Viktor Pavlovich. Discrete Math. Section 6. Finite state machinesand formal languages.

Lecture 31. Definition and methods of specifying a finite state machine. Synthesis task. Elementary auto And you

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 transformer b developer of information. At the same time, the concept of a finite automaton, like any model, is I entered 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 real b If the 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, the finite set of input and output states of the automaton is called coo t responsible input and output alphabet, and individual states the letters of these alphas and vits.

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

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. Z A 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 d is a device with memory, i.e. the output of the machine is determined not only b to the entrance, but also to the background. The history was taken into account I is determined 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.

State machinename five objects

, (1)

Where

input alphabet; one of the possible input states;

finite set, calledoutput alphabet; element n You of this set determine the possible output states;

finite set, calledalphabet of internal states I am ;

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

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

The law of operation of the automaton: the automaton changes its states according to T function and generates output signals in accordance with the function to tion:

1. Methods for specifying a finite state machine

1  . Tabular method of assignment. Since functions and domain are defined e tions and values ​​belong to a finite set, they are specified using tables.

Example 1. We define the automaton as follows: , .We define the function usingtransition tables,and function using output tables.

Table 1. Transition table Table 2. Output table

If the sequence of signals at the input of the machine is known, then the tables e moves and exits, the output sequence is uniquely determined.

2  . Graphic method of assignment. Used transition-output diagram.It is a oriented multigraph, in which each T The current state of the automaton corresponds to the vertex. The transitions of the machine from state to state are depicted by arrows, on each of which the input symbol is written, in s calling this transition, and the output symbol produced by the machine.

| | |

Fig.1 Transition-output diagram

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

The machine is in state 1 if, when adding the previous digits, And transfer, and in state 0 otherwise. Transition-output diagram and zana in fig. 2.

00|0 11|1 01|0

01|1 10|0

10|1 00|1 11|1

Rice. 2

1. Automata synthesis problem

By analogy with the problem of synthesis of SFE, we can pose the problem of synthesis for automatic A Comrade There is an unlimited set of basic machines. It is required to assemble an automatic machine with a predetermined functioning. At the same time, the task of synthesis faces T with certain problems.

Let's assume that you need to connect the output of the machine to the input of the machine. This is possible provided that otherwise Tue O the swarm machine will not understand the signals coming from the first one. This leads to confusion And situations when some connections are impossible.

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

Let be a finite set of elements, and let be a multiplicity e number of binary words of length, where. We will call an arbitrary injective mappingencoding a set in 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

(2)

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. 3 shown abstract automaton and the corresponding structural automaton.

… …

Rice. 3

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

1 . Compatibility of inputs and outputs, since binary and n formation. We won't give general definition circuits from structural automata it is similar to SFE.

2  . Let us write relations (2) in “coordinates”:

(3)

From (3) it follows thatthe law of functioning of a structural automaton is specified with And Boolean function system.

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: :

Rice. 4.

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

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 n you 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 O It is important that each column of Table 3 contains both a zero and a one. All such tables e g h e tyre.

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 inverting internal states.

The automaton specified by table 4 is called delay or -trigger:

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

The automaton specified by table 5 is calledtrigger with 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 at the initial moment of time- the trigger is in state 0. If in e which point in time- the trigger is in state 0, this means that the input of the machine received even number units. If the state is 1, then is odd. This way and zoom, - the trigger counts the number of units at the input, but since it has only two states I niya, then he counts to two.

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

Rice. 5.

1. The problem of completeness of an automaton basis

A set of structural automata is called complete (or automata b A zis), if from them it is possible to construct any predetermined structural automaton.

The efforts of mathematicians to obtain an analogue of Post's theorem for automata have not increased. n were successful. In 1964 M.I. Briefly proved the non-existence of an algorithm for determining e of the completeness of the 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. Automation system,containing a complete set of PV and -trigger (or -trigger) is complete.

Proof. Consider an arbitrary automaton given the relation e nyami (2), and describe its circuit from the indicated automata, calledcanonical structure(Fig. 6) .

The scheme consists of two parts.

…

…

…

Rice. 6.

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.

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.

Outputs:

1. binary word output signal of the machine, which is implemented T according to formulas (3);
2. binary word that goes to the inputs of flip-flops in memory A main 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 completely with and the FE system.

At each moment in time, memory control signals must translate a V tomato 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 properties: e following property: for any pair of states there is an input signal e driving machine 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 -trigger: at the input you need p O give 0 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 a conveyor along which two types of parts move and, V linen machine, whose task is to sort the parts so that after passing through e As they walked past the machine, they formed groups. Unsuitable machine part l nods from the assembly line. 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 . Output alphabet , where C collision of part, P her pass. 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.

| | |

Rice. 7.

2  . Coding alphabets.

One of possible options coding is given in the following e current 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.

Rice. 8.

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

, .

Table 8

These functions are calledpartially defined, since they are not defined at. To represent these functions by formulas, they are further defined in such a way as to obtain a simpler form of formulas.

4  . Presentation of machine output functions and memory management functions r mules.

Using methods for minimizing Boolean functions, we construct, if possible, eq. O Nominal representation of functions, formulas in the basis:

5  . Implementation of the SFE and the final circuit of the machine (Fig. 9).

Rice. 9.

SFE

SFE

NOT

OR