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

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

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

is 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. We 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

	State

	State

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 won't give general definition schemes 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

	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 both zero and one occur in each column of Table 3. 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 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 even number units. If in state 1, then 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. a binary word is the current internal state of the automaton.

1. binary word - the 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 to flip the trigger.

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. On the conveyor, along which parts of two types move and, an automatic machine is installed, 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.

The input alphabet is . The output alphabet is , where C is the collision of the part, P is 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 options coding is given 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

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 word given to the input belongs to a given set (these are automata recognizers); 2) automata transform input words into output words, i.e., they implement automaton mappings (transformer automata).

TA within the framework of metamathematics n The subject of the theory of algorithms and formal systems within the framework of metamathematics - what objects and actions on them should be considered precisely defined, what properties and possibilities 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.

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 an internal state symbol 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: 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: 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, the class NP includes the class P. In given time, it is not known whether the classes P and NP coincide, but most experts believe that they do 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.

Elements of automata theory

Plan:

1. The concept of an automaton, the principle of operation of an automaton

2. Methods for specifying finite automata

3. General Tasks automata theory

Theoretical information

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

The concept of an automaton, the principle of operation of an automaton

concept machine considered in two aspects:

1. Machine - device which performs some functions without the direct participation of a person. An automaton 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. Automatic - mathematical concept denoting the mathematical model of real technical devices. The automaton is an abstract device, it is not clear why and how it works and, in general, why it can work. In this aspect, the automaton is a "black box", which 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 the abstract theory of automata and the structural theory of automata.

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

Subject of study structural automata theory 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 State Machines

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

In the process of operation of a finite automaton, a finite number of its internal states sequentially change, and the state of the automaton at a certain point in time is uniquely determined by the input and output signals. Such automata are the basis of all modern computer technology and all kinds of discrete systems of automatic control and management.

The concept of an automaton is so abstract that it is difficult to say when a person did without any automata at all. The definition of an automaton includes any device, including those that primitive people hunted or threw stones, protecting their home from the enemy.

Algorithm- understandable and an exact formal instruction to the performer that unambiguously determines the content and sequence of operations that translate a given set of initial data into the desired result

It is believed that the first software device created by man was a clock. Watch mechanisms with the help of a spring that drives the 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 drives twelve fairytale heroes located on the dial.

We point out a few interesting historical facts associated with automata as mechanical devices.

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

2. The astronomer Johann Müller (Regiamontanus) (1436-1476) created a mechanical eagle that greeted the entrance to Nuremberg of Holy Roman Emperor Maximilian II with a tilt of the head and movement of the wings.

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

4. Russian inventor of the 19th century. A. M. Gamuletsky created a whole mechanical cabinet, in which there were many automata designed by him. Here, among other things, there was a talking head of a sorcerer and a cupid playing a harp, which amazed the imagination of contemporaries.

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

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

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

Types of machines.

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

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

A characteristic feature of a finite automaton is the presence memory, which determines the state of the automaton depending on time. The external manifestation of the various states of the automaton is its reaction to the same type of influences (signals).

In the operation of finite digital automata, an important concept is time.

Automata 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 in stadiums, alarm devices.

To control machines it is customary to attribute devices to control a certain process, including specifically: an elevator, a conveyor, a machine tool, a barrier.

To computing machines include microcalculators, computer processors and other devices that perform calculations.

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

2. Finite automata - from the point of view of informatics, these are automata, which are discrete information converters. These include transducers that contain a finite set of input and finite output signals, as well as a finite set of internal states

3. Digital machines- automata that converts digital information. In such an automaton, the input signals are given as a finite set of instantaneous symbols: their duration is so small that it can be neglected. For a fixed time, the input symbols are transformed, and the output is a jump transition from one state to another state.

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

The abstract automaton is:

~ Mathematical model,

~ Algorithm actions of some transformation of code sequences,

~ Law transformations of the input alphabet into the output one.

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

In synchronous machines the duration of the input signals and the time of the transitions 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 time of the transitions are not coordinated with each other. They depend on external sources - various events, and sampling interval is variable (for example, in combination locks). In asynchronous automata, the next change in the values ​​of input signals can occur only if the transient 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 size, then the difference lies in whether the automaton has final or endless number of internal states.

Under the endless automaton is usually understood as a certain mathematical idealization of ideas about an automaton that has an infinite number of states. The memory of such an automaton can potentially grow indefinitely. For example, the famous Post and Turing abstract automata 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 the behavior and structure at each moment of time are uniquely determined by the current input information and the state of the automaton itself at the previous moment of 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 the states of memory and is described by statistical laws.

8. Universal machine. In automata theory, it is proved that in order to perform various transformations of information, it is enough to construct universal automatic machine with the help of a program and appropriate coding, capable of solving any problems.

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

X- finite set of input symbols, input alphabet:

X \u003d (x 1 (t), x 2 (t), ..., x n (t));

Y- finite set of output symbols, output alphabet:

Y \u003d (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)), q0- initial state;

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

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

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

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

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

All hours of work T is divided into a finite number of intervals, on the boundary of which the state of the automaton changes. At the same time, t(Г 0) shows the number of changes that have occurred before time Г 0 .

An example of discretization is the usual cinema: time is divided into intervals of 1/24s. The human eye perceives the following of discrete frames as continuous movement.

9. Synchronous automata are divided into Mealy automata and Moore automata. Depending on the way to organize the exit function synchronous machines are divided into Mealy machines ( automata of the first kind) and Moore automata (automata of the second kind).

In the Mili vending machines- output signal y(t) x(t) and state q(t- 1) the automaton at the previous moment of time (t- 1). mathematical model such automata is the system of equations:

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

In Moore machines output signal y(t) uniquely determined by the input signal x(t) and state q(t) in this moment time t. The mathematical model of such automata is the system:

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

In such automata, the output function depends only on the states of the automaton 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, performing a character-by-character scan. At a certain point in time, the state machine is in some 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 automata– 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 unchanged during operation. Therefore, the minimal combinational automaton has only one state.

11 Boolean 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 exit function has the form of a system P logic functions from t variables.

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 outputs);

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 qi 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 qiО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

№	indication	+	-	overload	off	┤
0	initial state	1	0	0	0	No
1	0	2	0	13	0	Yes
2	50	3	1	13	0	Yes
3	100	4	2	13	0	Yes
4	150	5	3	13	0	Yes
5	200	6	4	13	0	Yes
6	250	7	5	13	0	Yes
7	300	8	6	13	0	Yes
8	350	9	7	13	0	Yes
9	400	10	8	13	0	Yes
10	450	11	9	13	0	Yes
11	500	13	10	13	0	Yes
12	OV	0	0	0	0	No
13	accident	0	0	0	0	No

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

Conclusion

Since the use of generators with oscillating 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 term paper 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 specifications generator elements.

In the practical part, a topic was covered regarding encoders, decoders, their purpose, and electrical functional and electrical circuit diagrams of encoders and decoders were 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.

Baranov Viktor Pavlovich Discrete Math. Section 6. State Machinesand formal languages.

Lecture 31 Synthesis task. Elementary cars and you

Lecture 30 DEFINITION AND METHODS OF DESIGNATION OF FINITE AUTOMAT.

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

Second, it is assumed that time changes discretely. The input and output states correspond to a discrete time sequence. b Since the moment of time is uniquely determined by its index, then for the sake of simplicity we will assume that time takes the values ​​1, 2, ..., ... The time interval is called 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. W a The dependence of the output sequence on the input sequence depends on the internal structure of the automaton. Note that, in contrast to the SFE, which do not have memory, the automaton pre d is a device with memory, i.e., the output of the automaton is determined not only b to the entrance, but also to the backstory. History accounting 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;

is a finite set calledoutput alphabet; element you of this set determine the possible output states;

is a finite set calledalphabet of internal states I nii;

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

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

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

1. Ways to define a state machine

1. Tabular assignment method. Since for functions and scope e values ​​and values ​​belong to a finite set, then they are specified using tables.

Example 1 We define the automaton as follows: , . Define the function usingjump tables,and the function with exit tables.

Table 1. Jump table Table 2. Output table

Entrance	State

Entrance	State

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

2 . Graphical way to set. used transition-output diagram.It is a directed multigraph in which each internal t the vertex corresponds to the early state of the automaton. Transitions of the automaton from state to state are depicted by arrows, on each of which an input symbol is written, in s calling this transition, and the output symbol generated by the automaton.

| | |

Fig.1 Diagram of transitions-outputs

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

The automaton is in state 1 if, when adding the previous digits, the and carries a carry, and in state 0 otherwise. Transition-exit 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. The problem of automata synthesis

By analogy with the problem of synthesizing the SFE, one can pose the problem of synthesis for the automatic a comrade There is an unlimited set of basic automata. It is required to assemble an automaton with a predetermined functioning. In this case, the problem of synthesis collides t with 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 that otherwise about swarm machine will not understand the signals coming from the first. This leads to confusing and situations where some connections are not possible.

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

Let be a finite set of elements, and be a set e set of binary words of length, where. An arbitrary injective mapping will be calledencoding the set in 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

(2)

The automaton obtained after coding is called structural . 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. 3 shown abstract automaton and its 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 will not give a general definition of a circuit 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 given with and Boolean Function Stem.

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

Rice. four.

To set the automaton shown in Fig. 4, it is enough to specify only the table p e transitions:

Table 3

Entrance	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 n you are zero. 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 about to ensure that each column of Table 3 contains both zero and one. Such tables are ego h e tyre.

Table 4 Table 5

Entrance	State
					Entrance	State

Table 6 Table 7

Entrance	State

Entrance	State

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 delay or -trigger :

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

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

Let at the initial time- trigger is in state 0. If in n e which point in time- the trigger is in state 0, this means that an even number of ones has been received at the input of the automaton. If in state 1, then odd. So arr and zom, - the trigger counts the number of units at the input, but since it has only two states I niya, then counts to two.

When triggers are physically implemented, two outputs are used: direct and inverted (Fig. 5). If we swap them, then- trigger, you get an automaton specified by table 7, and from- trigger - the automaton specified by table 6.

Rice. 5.

1. The problem of the completeness of an automaton basis

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

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

Proof. Consider an arbitrary automaton given by the relation e (2), and describe its scheme of the indicated automata, calledcanonical structure(Fig. 6) .

The scheme consists of two parts.

…

…

…

Rice. 6.

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. a binary word is the current internal state of the automaton.

Outputs:

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

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 completely with and the FE stem.

At each moment in time, the memory control signals must translate a in tomato 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 e next 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 -trigger, since the state in which the -trigger is set is equal to the input signal. For -trigger: when you need to enter n about give 0 to keep the state unchanged; at -1 to flip the trigger.

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. On the conveyor, along which parts of two types move and, installed in flax machine, whose task is to sort parts in such a way that after passing e passing by the machine, they formed groups. Wrong part machine sta l nods from the assembly line. 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.

The input alphabet is . The output alphabet is , where C - collision of the part, P is 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 automaton moves cyclically through these states without changing the state when an unsuitable part arrives. The transition-output diagram is shown in fig. 7.

| | |

Rice. 7.

2 . Alphabet coding.

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

Rice. eight.

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

, .

Table 8

These functions are calledpartially defined, since 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 management functions r mules.

Using the methods of minimizing Boolean functions, we build, if possible, ek about nominal representation of functions, formulas in the basis:

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

Rice. 9.

SFE

SFE

NOT

OR