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 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.
Deterministic Finite Automaton (DFA)- - 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
verification of systems of interacting processes;This can be judged by the speeches of scientists and specialists at the “Software 2000...” seminar.
Doug Ross: "...80 or even 90% of computer science in the future will be based on the theory of finite state machines..."
Herver Gallaire: “I know people from Boeing who are working on aircraft stabilization systems using pure automata theory. It’s hard to imagine what they accomplished with this theory.”
Brian Randell: "Much of automata theory has been successfully used in system programs and text filters in UNIX OS. This allows a lot of people to perform at a high level and develop very effective programs."
1.1. Basic concepts and definitions.
The simplest information converter (Fig. 1.1, a) displays a certain set of information elements X received at the input into a certain set at the output Y. If the sets X and Y are finite and discrete, that is, the transformation is carried out at discrete moments in time, then such information converters are called finite converters. Elements of sets X and Y in this case are pre-encoded with binary codes and a transformation of one set to another is constructed.
The result of a transformation often depends not only on what information currently appears at the input, but also on what happened before, that is, on the background of the transformation. For example, the same input - a neighbor's apology after he stepped on your foot on a crowded bus - will cause you to have one reaction the first time and a completely different one the fifth time.
Rice. 1.1.
Thus, there are more complex information converters (IT), the reaction of which depends not only on the input signals at the moment, but also on what happened before, on the input history. Such PIs are called automata (circuits with memory). In this case, they talk about automatic transformation of information (Fig. 1.1, b). The machine can react differently to the same input signal, depending on the state in which it was. The machine changes its state with each input signal.
Let's look at a few examples.
Example 1 1 Karpov Yu.G. Automata Theory - St. Petersburg: Peter, 2003. Automaton describing the behavior of a “smart” father.
Let us describe the behavior of a father whose son studies at school and brings in D's and A's. The father does not want to grab the belt every time his son gets a bad grade, and chooses more subtle parenting tactics. Let us define such an automaton by a graph in which the vertices correspond to states, and the arc from state s to state q, marked x/y, is drawn when the automaton from state s under the influence of the input signal x goes to state q with output reaction y. The graph of an automaton that models the smart behavior of a parent is presented in Fig. 1.2. This machine has four states 
, two input signals - estimates and output signals, which we will interpret as the actions of the parent as follows:
Take the belt;
Scolding your son;
Calm your son;
Hope;
Rejoice;
Rejoice.
Rice. 1.2.
A son who receives the same grade - a D - will have a completely different reaction from his father at home, depending on the background of his studies. For example, after the third bad mark in the story, the son will be greeted with a belt, and in the story they will calm him down, etc.
A finite state machine can be implemented either in software or in hardware. Software implementation can be done on any high level language different ways. Figure 1.3 shows a block diagram of a program that implements the behavior of the automaton in example 1. It is easy to see that the topology of the program block diagram repeats the topology of the transition graph of the automaton. Associated with each state is an operation NEXT, which performs the function of waiting for the next event of the arrival of a new input signal and reading it into some standard buffer x, as well as subsequent analysis of what kind of signal it is. Depending on what signal came to the input, one or another function is performed and a transition to a new state occurs.
Rice. 1.3.
We will consider the hardware implementation of the machine in the second part of this section.
Example 2. "Student"
The automaton, the model of which is presented in Fig. 1.4, describes the behavior of the student and teachers.
Rice. 1.4.
States;
- input signals: "n", "2" and "5".
Output reactions:
Example 3 1. Electronic clock (Fig. 1.5).
Electronic watches with various functional capabilities are one of the most widely used electronic devices in everyday life, the control of which is based on a finite-state machine model. They usually show: time, date; they have functions such as “setting time and date”, “Stopwatch”, “Alarm clock”, etc. Simplified structural scheme electronic clock is shown in Fig. 1.5
Rice. 1.5.
The registers display either time, date, or stopwatch depending on the "Control". Control device built on the basis of a finite state machine model. The state machine responds to pressing the “a” button on the body by transitioning to the “Set minutes” state, in which the event of pressing the “b” button will cause the number to increase.
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...
Computers presented in the form of mathematical models - and the problems they can solve.
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.
Encyclopedic YouTube
1 / 3
✪ Lesson 12. Basics of automata theory. Mathematical logic. Computer science lessons
✪ How to rule the world by learning just one simple model!
✪ Lesson 15. Solving applied problems in automata theory. Mathematical logic. Computer science lessons
Subtitles
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) automaton M if it consists of words w based on the alphabet Σ (\displaystyle \Sigma) such that if these words are entered into M, at the end of processing it arrives at one of the receiving states F:
L = ( w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F ) (\displaystyle L=\(w\in \Sigma ^(\star )|(\hat (\delta ))(S_(0) ,w)\in F\))Typically, an automaton moves from state to state using a transition function δ (\displaystyle \delta ), 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 character is called ϵ (\displaystyle \epsilon )-transition(epsilon transition).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.