Automata theory. Cheat sheet on automata theory (TA) Theory of finite state machines and examples

A.A. Ozhiganov Theory of automata. Textbook - St. Petersburg: NRU ITMO, 2013. - 84 p. - copy

Annotation:

The purpose of this textbook is to familiarize students with the methods of synthesis of digital automata. Information about abstract automata of Mealy and Moore is provided. Tabular and graph methods of representing automata are considered, the concept of an automaton's reaction to an input word and the definition of equivalent automata are introduced. Methods for mutual equivalent transformation of automata are presented. General information about microprogram control, the concepts of microinstructions, microoperations, microprograms, methods of representing microprograms in the form of graph diagrams of algorithms (GDA), transition formulas, matrix and logical diagrams of algorithms are provided. Methods for marking GSA and rules for constructing Mealy and Moore automata using them are given. Methods for the canonical synthesis of structural automata are considered. Examples are given of the synthesis of memory of a structural automaton based on D -, T -, RS - and JK flip-flops.

Description:

The manual is intended for students specializing in the field of information technology and can be used in the preparation of bachelors and masters in the fields of 230100 “Informatics and Computer Engineering”, 231000 “Software Engineering” and engineers in the specialty 230101 “Computers, complexes, systems and networks”.

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

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

• 1 Terminology
• 2 Application
  • 2.1 Typical tasks
• 3 See also
• 4 Literature
• 5 Links

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.

Slot machines

Automata can be deterministic or non-deterministic.

• - a transition function such that
• - initial state

• - set of states of the machine
• - the alphabet of the language that the machine understands
• is a transition relation, where is an empty word. That is, an NFA can make a jump from state q to state p, unlike DFA, through an empty word, and also move from q to a several states (which, again, is impossible in DFA)
• - set of initial states
• - set of final states.

A language L is said to be read (accepted) by an automaton M if it consists of words w based on an alphabet such that if these words are entered into M, upon completion of processing it arrives at one of the receiving states F:

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

Application

The theory of automata underlies all digital technologies and software, for example, a computer is a special case of the practical implementation of a finite state machine.

Part of the mathematical apparatus of automata theory is directly 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

• Pumping Lemma
• Abstract automaton
• Game of Life
• Minimum form of machine
• Shannon - Lupanov theorem

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

• Application of automata theory

automata theory

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 expedient 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.

Vyatka State University

FACULTY OF AUTOMATION AND COMPUTER ENGINEERING

Department of Electronic Computers

Automata Theory (Part I) Lecture Notes

Automata theory (part I). Lecture notes / Kirov, Vyatka State University, 2010, 56 p.

The lecture notes for the course “Theory of Automata” (Part I) provide the necessary theoretical material, including the basics of the applied theory of digital automata, the basic definitions and rules for the synthesis of abstract finite automata, the circuit of a discrete converter V.M. Glushkov and three main models of finite automata: the Mealy model, the Moore model and the C-automaton model. Next, we consider methods for encoding memory elements, minimizing automata with memory, and the canonical method for synthesizing structural automata. Particular attention is paid to the rules for constructing an optimal combinational circuit of an automaton using canonical equations, taking into account the selected memory elements. Relevant literature is indicated.

The course of lectures is intended for full-time students of the specialty 230101 - "Computers, complexes, systems and networks", as well as bachelors of the specialty 230100.62 - "Informatics and Computer Science".

Compiled by: Ph.D., Associate Professor of the department. EVM V.Yu. Meltsov.

Vyatka State University, 2010

Meltsov V.Yu.

1. Introduction 4

2. Problems of analysis and synthesis 4

3. Abstract control automaton 7

4. Synthesis of abstract automata 9

5. Synchronous machine 10

6. Asynchronous machines 11

7. Mealy and Moore automata 12

8. Methods for specifying automata 14

8.1 Tabular method of specifying automata 15

8.2. Setting the machine using graph 17

8.3. Matrix method of specifying automata 19

9. Transition from the Mili machine to the Moore machine and back 19

10. Stages of synthesis of automata 23

11. Minimizing the number of internal states of the automaton 26

12. Minimization of fully defined automata. 27

13. Combined model of automatic machine (C-automatic machine) 31

14. Structural synthesis of automaton 32

14.1. Canonical method of structural synthesis of automaton 32

14.2. Structural synthesis of C-automaton 35

15. Coding the states of the machine 41

15.1. Method of anti-race coding of states of automaton 42

15.2. Adjacent coding of states of automaton 45

15.3. Coding the states of the machine to minimize the combinational circuit 47

16. Elementary memory machines 50

17. Synthesis of automata on PLM and ROM 54

1. Introduction

In recent years, research and work on the creation and use of various automatic systems for information processing have been carried out with great intensity. Such systems are usually implemented in the form of blocks that form a control and information processing system. In accordance with this, a new scientific discipline arose, which was called “Systems Theory”.

The goal of systems theory is to create an arsenal of ideas and tools that would be equally useful to specialists in a variety of fields (electrical engineering, mechanics, physics, chemistry, sociology, etc.). This goal is achieved by viewing the system not through its internal structure, but through the mathematical laws that determine its observable behavior. In this case, the most often used approach is called the “black box” method (i.e., a method in which the input data and the data obtained at the output of the machine are analyzed, while internal processes are not considered). It has been proven that all systems can be characterized in the same terms and analyzed using the same set of rules.

An integral part of systems theory is the theory of automata. It deals with mathematical models designed to represent physical phenomena to varying degrees. The use of the automata theory model is not limited to any particular area, but is possible to solve problems in almost any field of research.