Automaton Theory- INTRODUCTION

Automata theory is a section of the theory of control systems that studies mathematical models of discrete information converters, called automata. From a certain point of view, such converters are both real devices (computers, automata, living organisms, etc.) and abstract systems (for example, the formal system, axiomatic theories, etc.). The theory of automata is most closely connected with the theory of algorithms.

This abstract of lectures includes the apparatus of basic models in the field of informatics: the concepts of set theory, Boolean algebra, the formal logic of propositions and predicates, graphs, i.e. those sections of computer science, without which it is impossible to build a theory of automata. In addition, the basic concepts of the theory of algorithms and the Turing machine are presented, as well as brief information on the use of Petri nets to simulate parallel processes of automaton systems.

The automaton “in general” ([French automatique ⇐ Greek automates self-acting ]) is a control system that is a finite automaton or some modification of it, obtained by changing its components or functioning. The basic concept of “finite automata” arose in the middle of the 20th century in connection with attempts to describe in a mathematical language the functioning of the nervous systems, universal computers and other real automata. A characteristic feature of such a description is the discreteness of the corresponding mathematical models and the finiteness of the ranges of values ​​of their parameters, which leads to the concept of a finite automaton.

Most problems in automata theory are common to the main types of control systems. These include problems of analysis and synthesis of automata, problems of completeness, minimization, equivalent transformations of automata, and others. The task of the analysis is to describe its behavior according to a given automaton or to determine one or another of its properties using incomplete data on the automaton. The task of the synthesis of automata is to build an automaton with a predetermined behavior or operation. The task of equivalent transformations in general form is to find a system of transformation rules (the so-called complete rule system) of automata that satisfy certain conditions and allow you to transform an arbitrary automaton into any equivalent one. The behavior of an automaton is a mathematical concept describing the interaction of an automaton with the external environment.

The concept of an automaton can serve as a model object in a wide variety of problems, which makes it possible to apply the theory of automata in various scientific and applied research. The great interest in this theory is explained by the wide possibilities of its application. Without exaggeration, it can be said that the theory of automata is one of the fundamental blocks of modern theoretical and practical informatics.