The mathematical apparatus of automata theory is used in. Automata theory

Each question is posted on one separate page (except for one - “Algebraic and structural theory of spacecraft”, which takes up two pages). Cheat sheet format: doc.

Cheat sheet questions

1. Subject of automata theory
2. Classification of machines
3. Applications of automata theory
4. Binary multiplication
5. Multiplication in inverse codes
6. Division
7. Division in inverse codes. Peculiarities
8. Features of performing operations in floating point format
9. Binary decimal codes. Addition in DDC
10. Glushkov discrete converter model
11. Microprogramming
12. Operating machine structures
13. Synthesis of an operating automaton (OA) of a procedural type
14. Synthesis of OA structural type
15. Automatic languages. Formal task of the Automaton
16. Models of Mili and Moore assault rifles
17. Equivalence of finite state machines (FAs). Moore's theorem
18. Minimizing Finite State Machines
19. Equivalence of the Mealy and Moore automata
20. Types of control automatic machine (CA)
21. Structural diagrams of UA. Mili and Mura
22. Stages of synthesis of a control automaton with hard logic (CALA)
23. Examples of UAZL synthesis
24. Races and ways to deal with them
25. UA with programmable logic (UAPL)
26. Algebraic and structural theory of CA
27. Combining several UA into one
28. Software implementation of spacecraft. Implementation options. Template State
29. Purpose and brief characteristics of VHDL
30. Implementation of UA in VHDL
31. Understanding the UML modeling language
32. Concept of languages ​​and formal grammars
33. Classification of languages
34. Pumping Lemma
35. The concept of NCA. Obtaining DKA according to NKA
36. Regular expressions. Syntax diagrams. Kleene's theorem
37. Application of RV. Various RV notations
38. CS-grammars and store machines
39. Turing machines
40. Using MT to analyze algorithms

Example of a question from a cheat sheet

Subject of automata theory

An automaton is an object (ideal, material, or more specifically, a device) that processes information.

The study of methods for transforming information is the subject of automata theory in a broad sense.

The theory of automata is part of cybernetics, as the science of methods of storing, perceiving, transmitting and processing information in machines and living organisms.

Automata theory uses various mathematical models. The most general of them are studied by abstract automata theory and algebraic TA.

From the point of view of abstract TA, an automaton is a collection of sets and mappings. For example, an automaton can be specified as six objects: A = , Where:

• X – set of input symbols of the machine
• Y – set of output symbols of the machine
• Q – set of states of the machine
• q0 – initial states of the machine
• A – transition function: Q x X -> Q
• B – output function: Q x X -> Y

Automatic transformations: The output words of the automaton depend not only on the output words of the states, but also on the meanings of the words in the previous state.

A mathematical automaton is sometimes considered as an algebra, and a set of states of the automaton and operations on this set are distinguished.

A technical automaton is a physical device for which not only the behavior or the law of operation is important, but also its internal structure, the obtaining of this structure, therefore in technology they consider the structural theory of the automaton, the subject of which is the study of the structure of the automaton, the analysis and synthesis of circuits of the automaton with given properties.

The following types of Automata Theories can be distinguished:

• Abstract TA (mathematical);
• Structural TA (technical);
• General TA;
• Applied TA;

PTSA is a discrete automaton - a device that converts digital information according to a given algorithm.

A TT machine is a device that performs transformation (recognition) of input words (text).

Automata theory

Automata theory- a branch of discrete mathematics that studies abstract automata - computers presented in the form of mathematical models - and the problems that they can solve.

The theory of automata is most closely related to the theory of algorithms: an automaton transforms discrete information step by step into discrete moments of time and generates a result according to the steps of a given algorithm.

Terminology

Symbol- any atomic block of data that can produce an effect on a machine. Most often, a symbol is a letter in ordinary language, but it can be, for example, a graphic element in a diagram.

• Word- a string of characters created through concatenation (connection).
• Alphabet- a finite set of different symbols (many symbols)
• Language- a set of words formed by the symbols of a given alphabet. Can be finite or infinite.

They say the language is L read (accepted) an automaton M if it consists of words w based on an alphabet such that if these words are entered into M, at the end of processing it arrives at one of the receiving states F:

Typically, an automaton moves from state to state using a transition function, while reading one character from the input. There are also machines that can go to a new state without reading a symbol. The function of jumping without reading a character is called -transition(epsilon transition).

Application

In practice, automata theory is used in the development of lexers and parsers for formal languages ​​(including programming languages), as well as in the construction of compilers and the development of programming languages ​​themselves.

Another important application of automata theory is the mathematically rigorous determination of the solvability and complexity of problems.

Typical tasks

• Construction and minimization of automata- construction of an abstract automaton from a given class that solves a given problem (accepting a given language), possibly with subsequent minimization by the number of states or the number of transitions.
• Synthesis of automata- construction of a system from given “elementary automata”, equivalent to a given automaton. Such an automaton is called structural. It is used, for example, in the synthesis of digital electrical circuits on a given element base.

see also

Literature

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman Introduction to Automata Theory, Languages, and Computation. - M.: Williams, 2002. - P. 528. - ISBN 0-201-44124-1
• Kasyanov V.N. Lectures on the theory of formal languages, automata and computational complexity. - Novosibirsk: NSU, 1995. - P. 112.

Links

Wikimedia Foundation. 2010.

See what “Automatoma Theory” is in other dictionaries:

Automata theory

Automata theory- a section of theoretical cybernetics that studies mathematical models (called here automata or machines) of real or possible devices that process discrete information in discrete cycles. The main... ... Economic and mathematical dictionary

automata theory- A section of theoretical cybernetics that studies mathematical models (called here automata or machines) of real or possible devices that process discrete information in discrete cycles. The basic concepts of this theory... ... Technical Translator's Guide

Noun, number of synonyms: 1 taut (1) ASIS Dictionary of Synonyms. V.N. Trishin. 2013… Synonym dictionary

automata theory- automatų teorija statusas T sritis automatika atitikmenys: engl. automata theory vok. Automatentheorie, f rus. automata theory, f pranc. théorie des automates, f … Automatikos terminų žodynas

This term has other meanings, see State Diagram. State diagram is a directed graph for a finite state machine, in which the vertices indicate the states of the arc and indicate transitions between two states. In practice... ... Wikipedia

The theory of machines and mechanisms (TMM) is a scientific discipline about the general methods of research, construction, kinematics and dynamics of mechanisms and machines and the scientific foundations of their design. Contents 1 History of the development of the discipline 2 Basic concepts ... Wikipedia

THEORY- (1) a system of scientific ideas and principles that generalize practical experience, reflecting objective natural laws and provisions that form (see) or a section of any science, as well as a set of rules in the field of any knowledge million... ... Big Polytechnic Encyclopedia

Theory of algorithms Economic and mathematical dictionary

Theory of algorithms- a branch of mathematics that studies the general properties of algorithms. The problem of constructing an algorithm with certain properties is called an algorithmic problem; its unsolvability means the absence of a corresponding algorithm; If… … Economic and mathematical dictionary

Books

• Automata theory. Textbook for bachelor's and master's degrees, Kudryavtsev V.B. The textbook contains extensive material on the theory of automata. It introduces the concept of an automaton, gives theories...

A section of theoretical cybernetics that studies mathematical models (called automata, machines) of actually existing (technical, biological, etc.) or fundamentally possible devices that process discrete information in discrete time steps. A. t. arose Ch. way under the influence of the demands of the technology of digital computing and control machines, as well as the internal needs of the theory of algorithms and mathematical logic. The concept of “automaton” varies noticeably depending on the nature of the named devices, the adopted level of abstraction and the appropriate degree of generality (automata are finite, infinite, growing, probabilistic, deterministic, autonomous, etc.).

The question is about developing such a concept of “automatic machine”, which would have a max. degree of generality and at the same time could serve as a basis for setting and solving quite meaningful problems, cannot yet be considered completely solved. At the same time, it can be considered as a special case of the general concept of a control system.

The term "A. T." came into use in the 50s of the 20th century, although the corresponding problems began to take shape to a large extent back in the 30s within the framework of the theory of algorithms and the theory of relay devices. Even then, fairly general concepts of computation were formulated in algorithm theory. automaton (see Turing machine) and (implicitly) the concept of a finite automaton (head of a Turing machine). It was found that to implement

for all kinds of effective transformations of information, it is not at all necessary to build specialized machines each time; in principle, all this can be done on one universal machine using a suitable program and suitable coding. This theory the result later received engineering embodiment in the form of modern universal computing. cars However, a detailed study of the processes occurring in automata of various kinds and the general laws to which they are subject began later only within the framework of automatic theory. The difference in formulations between the problems of the theory of algorithms and automatic theory can be briefly characterized as the difference between the questions of what automata can do and how they do it. Since the use of other types of automata (other than Turing machines) obviously does not expand the stock of computable transformations of information, for the theory of algorithms such use is only episodic in nature and is associated only with the proof technique used. On the other hand, for A. t. such consideration becomes an end in itself. Theor. and applied problems of automation, computing. technology and programming, biological modeling. behavior, etc. continue to stimulate the problems of A. t. However, along with this, A. t. is already developing its own internal problems. In mathematical theory, the apparatus of algebra, mathematical logic, combinatorial analysis (including graph theory), and probability theory is widely used.

In automatic theory, its individual directions emerge quite clearly, depending on the choice of the types of automata studied (finite, probabilistic, etc.), the adopted level of abstraction (see Abstract theory of automata, Structural theory of automata) or the specifics of the mathematics used. methods (see Algebraic theory of automata). At the same time, related problems and methods are intensively developed in the theory of relay devices, in the theory of digital computers, and in the theory of programming, so it is often difficult to distinguish between the spheres of action of these theories and automatic technologies.

Behavior and structure. At the basis of mathematical theory are exact mathematics. concepts that formalize intuitive ideas about the functioning and behavior of the machine, as well as its structure (internal structure). From the point of view of their behavior, automata are most often considered as converters of dictionary information, that is, converters of sequences of letters into sequences of letters. The implemented transformation is usually interpreted as the calculation of the values ​​of some function (operator) from given values ​​of the arguments or as the transformation of records of the conditions of problems of some type into records of the corresponding solutions. In particular, the so-called recognizing automata, perceiving input information, react to it in such a way that they accept some input signal sequences and reject others. In this sense, they recognize or, as they also say, represent multiple input sequences. Finally, the generating automaton functions as an autonomous system, not associated with input information; its behavior is determined by what output sequences it is capable of generating. The above classification in terms of transformation, recognition and generation depends on the rules of operation of the automaton, i.e. on the program of interaction of its internal states with input (coming from the external environment) and output (generated into the external environment) signals. Let Q, X, Y be, respectively, the set of internal states of the input and output signals of the machine. If this is a deterministic automaton, its program is formalized in terms of the transition function H and the output function Ф, indicating for each input signal x and each state the state into which the automaton goes and the output signal it produces

Abstract automatic theory is characterized by a higher level of abstraction: in it, the concept of an automaton is identified with the concept of the automaton’s program, that is, with the five (), in complete abstraction from its structure. The structure of an automaton reflects the way it is organized from simpler interacting components (elementary automata or simply elements), properly connected into a single system. E.g. Comput. the machine is composed of elementary cells such as triggers, inverters, etc.; The nervous system is made up of neurons. The structural classification of automata is determined by the nature of the allowed connections (connections can be rigid or change during operation, subject to certain geographic restrictions), as well as the specifics of the functioning and interaction of the elements used (for example, elements can only exchange information or they can generate new elements, increasing the structure). Formalization of structural concepts is carried out in terms of various kinds of schemes (see Logical network). A. N. Kolmogorov outlined an approach that led to the formulation of a very general, but still constructive concept of the structure of an automaton (see Growing automata), which, apparently, covers all known types of automata structures and all those that can be foreseen at the modern level Sciences. It is quite obvious that there is a close connection between the structure of the automaton and its behavior. However, a separate study of each of these two aspects, with significant abstraction from the other, is not only possible, but often useful in posing and solving many important problems. Such a study is carried out in the abstract (behavioral) and structural theories of automata, respectively.

Types of machines. The most common is the classification of automata and related ones. sections of A. t. devoted to various

types of machines, according to the following characteristics.

1) Memory capacity. Finite and infinite automata are characterized respectively. finiteness and infinity of memory capacity (number of internal states). Finite state machines are separate blocks of modern computing. cars and even the car in general. The brain can also be thought of as a state machine. Infinite automata are a natural mathematics. an idealization that grows from the idea of ​​an automaton with a finite but infinitely large number of states. What is meant here is only the potential infinity of memory, which manifests itself in the fact that memory, although it remains finite at every moment of time, can increase indefinitely. This idealization arose for the first time within the framework of the theory of algorithms in the process of clarifying the intuitive idea of ​​an algorithm. A structurally growing automaton is represented as a connection of elements capable of multiplying and expanding the circuit. Modern computers can be considered as growing (and at the same time potentially infinite) automata in the following sense: in order for calculations to be completed in all cases, it is necessary to allow for the possibility of unlimited expansion of external (tape) memory.

2) Random selection mechanism. In deterministic automata, the behavior and structure at each moment in time are uniquely determined by the current input information and the state of the automaton that developed at the immediately preceding moment. In probabilistic (stochastic) automata they also depend on some random choice. Stochastic automata should not be confused with nondeterministic ones, in which the condition of unambiguity is also violated (however, without the participation of a random selection mechanism).

Problems and methods. The central problems of automatic theory include problems of analysis, i.e., describing the behavior of an automaton based on its given program or structure, and synthesis, i.e., constructing automata whose behavior would satisfy predetermined requirements. These problems are closely related to many other problems that are being intensively studied (completeness and universality, minimization, languages, asymptotic estimates, etc.). Most of all, analysis and synthesis have been studied in the theory of finite deterministic automata, and they are interpreted differently in the abstract and structural theories of automata. So, for example, in structural theory, synthesis (see Structural synthesis of automata) means the construction of a circuit from a given assortment of elements that would be optimal. (or close to optimal) in the sense of some put forward criterion for the complexity of circuits. Combinatorial information methods and asymptotic estimates predominate here (K. Shannon, S. V. Yablonsky, O. B. Lupanov, etc.). In the abstract theory of automata, one is content with constructing a program for the functioning of the automaton (see Synthesis of abstract automata), for example, in the form of transition and output functions for a finite automaton, which usually serves as the source material for the further development of structural synthesis. Here, mainly algebraic (S.K. Kleene, V.M. Glushkov, etc.), mathematical and logical ones are used. (B. A. Trakhtenbrot, R. Büchi, etc.) and game (R. McNotop) methods and concepts. The problem of analysis and synthesis of finite deterministic automata also occupies a prominent place in the theory of relay devices.

In the theory of experiments with automata (E. Moore), methods are developed that make it possible, based on information obtained from external observation of the behavior of an automaton, to restore the program of its functioning or at least some of its properties. These methods can be considered as a unique technique for abstract synthesis and decoding of automata (Ya. M. Barzdin). The works of K. Shannon, M. Rabin and others served as an impetus for the development of the theory of probabilistic automata in the following directions: 1) to what extent the concepts and methods of the theory of deterministic automata are transferred to stochastic automata; 2) what simplifications of the calculations. processes are achievable by moving from a narrower class of deterministic automata to a broader class of probabilistic automata. The study of growing automata is focused mainly on the following problems: 1) development of models of growing automata and the study of their individual classes (iterative automata - F. Henni, register automata - V. M. Glushkov, self-reproducing automata - J. von Neumann, generalized growing automata - A. N. Kolmogorov, Ya. M. Barzdin); 2) evaluation computation. abilities and difficulties of computing growing automata (Ya. M. Barzdin, B. A. Trakhtenbrot, J. Hartmanis, G. S. Tseytin, M. Rabin, etc.).

Connection with other scientific areas.

The significance of the theory of algorithms and the theory of relay devices for automatic technology has already been explained above. It is also worth pointing out the reverse return of mathematical technology, the methods of which made it possible to solve a number of problems that arose in mathematics. logic and theory of algorithms (R. Buchi). The problems emerging in the theory of growing automata (for example, the complexity of calculations) lie essentially at the intersection of the theory of algorithms and the asymptotic laws of the structural synthesis of automata. There is a strong mutual penetration of mathematical linguistics and mathematical linguistics, one of the important concepts of which is generative grammar, an object very close to a generative automaton. Therefore, certain rather important provisions of the theory of grammars can, in principle, be attributed to automatic theory. In the abstract theory of automata, mathematics. issues of learning, as well as the appropriate behavior of one individual or team, were clarified and studied in terms of automatic games (M. L. Tsetlin). Useful

There was also a connection between the theory of finite state machines and the theory of digital computer design and programming theory (V. M. Glushkov, A. A. Letichevsky).

Lit.: Gavrilov M A. Theory of relay contact circuits. M.-L., 1950 [bibliogr. With. 298-299]; “Proceedings of the Mathematical Institute named after. V. A. Steklova of the USSR Academy of Sciences,” 1958, v. 51; Glushkov V. M. Synthesis of digital automata. M., 1962 [bibliogr. With. 464-469]; Kobrinsky N. E., Trakhtenbrot B. A. Introduction to the theory of finite automata. M., 1962 [bibliogr. With. 399-402]; Tsetlin M. L. Research on the theory of automata and modeling of biological systems. M., 1969 [bibliogr. With. 306-316]; Trakhtenbrot B. A., Barzdin Ya. M. Finite automata (Behavior and synthesis). M., 1970 [bibliogr. With. 389-395]; Automatic machines. Per. from English M., 1956. B. A, Trakhtenbrot.

AUTOMATINE THEORY, a section of discrete mathematics that studies mathematical models of discrete information converters, called automata. Examples of such converters are both real systems (computers, technical automata, living organisms) and abstract systems (abstract computers, axiomatic theories). Automata theory arose in the mid-20th century in connection with the study of automata as mathematical models of biological systems and computers. Subsequently, the problems of automata theory expanded significantly.

The theory of automata is closely related to the theory of algorithms, in particular with the theory of abstract computers, since automata can be considered as a case of their approximation.

An automaton can be characterized as a device that has input and output channels and is in one of the internal states at each discrete moment in time. At such a moment, impact signals are received through the input channel. At the same moments, the device produces reaction signals through the output channel. The states of the machine, action signals and reaction signals are specified by the letters of the corresponding alphabets: the state alphabet, as well as the alphabets of input and output signals. The laws of interaction of letters of these alphabets are specified by two functions - the transition function and the output function, mapping pairs (state - input letter) into states and output letters, respectively. The input environment for an automaton is the set of words in the input alphabet, and its internal and output environments are the sets of words in the alphabet of states and the output alphabet. The machine processes words from the input environment letter by letter into words from the other two environments. This process is called automaton behavior. The properties of alphabets and functions define different types of automata. In the case when all alphabets are finite, a finite automaton is obtained, otherwise the automaton is called infinite. Replacing functions with relations leads to partial and non-deterministic automata; using random functions results in a probabilistic automaton. When interpreting the input medium in terms or graphs come to automata over baths and automata in labyrinths.

Most of the problems of automata theory are common to the main types of control systems, these include problems of analysis and synthesis of automata, problems of completeness, minimization, as well as problems associated with equivalent transformations of automata. The task of analysis is to describe its behavior for a given automaton or, based on incomplete data about the automaton and its functioning, to establish certain of its properties. The task of synthesis is to construct an automaton with a given behavior, or functioning. This problem is related to problems associated with assessing the complexity of automata that have a given behavior, as well as with the construction of automata that are optimal in a certain sense. The completeness problem is to find out whether a given set of automata can be obtained from a smaller set using some operations on automata. The task of minimizing automata consists of minimizing the values ​​of parameters of automata (for example, the number of states), which produces an automaton that is equivalent in one sense or another to the original one. In addition to problems common to the main types of control systems, automata theory considers specific problems characteristic of automata. Thus, depending on the conditions of the problem, it is convenient to specify the behavior of automata in different languages ​​(regular expressions, canonical equations, predicate logic language, etc.), in connection with which important tasks are choice a convenient adequate language and translation from one language to another is sufficient. The problem of minimizing the number of states of an automaton is related to the problems of synthesis and equivalent transformations. In connection with the modeling of the behavior of automata of one class by automata of another class, the problems of minimizing the modeling automata and estimating their complexity arise. A special section of automata theory is associated with so-called experiments with automata. The main objective of this section is to obtain certain information about the structure of the machine by observing its reaction to certain external influences. In this case, problems arise related to the classification of experiments and the solvability of problems by certain types of experiments, as well as with estimates of the lengths of minimal experiments sufficient to solve certain problems. The concept of an experiment with automata is also used in problems of control of automata. Special sections of automata theory are games of automata and the behavior of automata in a random environment, which consider issues of interaction of automata with each other and with certain external environments. Many of the problems listed above can be considered mass problems (see Algorithmic problem). For finite state machines, most of them have a positive solution.

Automata theory finds application in many fields. For example, the solvability of some formal calculi is proved using the theory of automata. Methods and concepts of automata theory are significantly used in mathematical linguistics. The concept of an automaton can serve as a model object in a variety of problems, making it possible to use automata theory in various applied research.

Lit.: Kudryavtsev V.B., Aleshin S.V., Podkolzin A.S. Introduction to the theory of automata. M., 1985.