Finite automata and ways to set them. Automata Ways of setting Basic definitions n Finite. Standard or automatic description languages

As stated earlier, Y (x,q) specifies the order of transformation of the input symbols and the state of the automaton on the previous cycle into the state on the next one, a Q (x,q) - transformation of input symbols and the state of the automaton at the current cycle into an output symbol. If a q 0 is the initial state of the automaton, and i- measure number, then its work is described by the system:

These ratios are called systems of canonical equations finite automaton. You can use them from q 0 , sequentially find all subsequent states of the automaton and output symbols.

There are two types of machines - initial and non-initial. AT initial automata have a fixed initial state (i.e. they always start from the same state q0). In non-initial automata, any of the set Q; this choice determines the further behavior of the automaton.

The representation of a particular finite automaton is actually reduced to a description of the automaton functions that define it. It follows from system (9.3) that for a finite number of possible internal states, the number of possible values ​​of automaton functions also turns out to be finite. They can be described in various ways, the most common of which is tabular and with the help diagrams.

AT tabular way automaton functions are given by two finite tables, named respectively transition matrix and output matrix. In these tables, the rows are denoted by the letters of the input alphabet, and the columns are denoted by the letters of the internal alphabet (symbols encoding the internal state of the automaton). In the transition matrix at the intersection of the row (xk) and column (qr) the values ​​of the function Y are placed ( q r, x k), a in the matrix of outputs - the values ​​of the function Q (q r , x k).

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 problems of 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. Automaton - a 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. Any devices are suitable for the definition of an automaton, including those with which 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 gears and cam mechanisms, gears and levers, perform 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 sets in motion twelve fairy-tale characters located on the dial.

Let us point out some interesting historical facts related to 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 was 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 such complex systems that they are both computational, control, and informational 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- one). The mathematical model of 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) at a given 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.

Automata theory is a section of discrete mathematics that studies models of discrete information converters. Such converters are both real devices (computers, living organisms) and imaginary devices (axiomatic theories, mathematical machines). In essence, a finite state machine can be described as a device M , which has input and output channels, while at each of the discrete time moments, called clock moments, it is in one of the final states.

On the input channel at any time t =1, 2, ... to device M input signals arrive (from some finite set of signals). The law of state change to the next moment of time is set depending on the input signal and the state of the device at the current moment of time. The output signal depends on the state and the input signal at the current time (Fig. 1).

The state machine is a mathematical model of real discrete information processing devices.

state machine called the system A= (X , Q , Y ,  ,  ), where X , Q , Y are arbitrary non-empty finite sets, and  and  - functions, of which:

lots of X ={a 1 , ..., a m ) is called input alphabet , and its elements are input signals , their sequences are in catchphrases ;

lots of Q ={q 1 , ..., q n ) is called many states automaton, and its elements - states ;

lots of Y ={b 1 , ..., b p ) is called output alphabet , its elements are output signals , their sequences are output words ;

function  : X  Q Q called transition function ;

function  :X  Q Y called output function .

In this way,  (x , q )Q ,  (x , q )Y for  x X , q Q .

An imaginary device is associated with the state machine, which works as follows. It can be in a state from the set Q , receive signals from the set X and issue signals from a set Y .

2. Methods for defining a finite automaton

There are several equivalent ways to define abstract automata, three of which are: tabular , geometric and functional .

2.1. Table assignment of the machine

It follows from the definition of an automaton that it can always be defined by a table with two inputs containing t lines and P columns, where at the intersection of the column q and lines a function values ​​are worth  (a i , q j ),  (a i , q j ).

2.2. Defining an automaton by a Moore diagram

Another way to specify a finite state machine is graphical, that is, using a graph. The automaton is represented as a labeled directed graph G(Q , D ) with many vertices Q and many arcs D ={(q j ,  (a i , q j ))| q j Q , a i X ), while the arc ( q j ,  (a i , q j )) is labeled with a pair ( a i ,  (a i , q j )). Thus, with this method, the states of the automaton are depicted by circles, in which the symbols of the states are entered q j (j = 1, …, n ). From each circle is carried out t arrows (directed edges) one-to-one corresponding to the characters of the input alphabet X ={a 1 , ..., a m ). Arrow corresponding to the letter a i X and leaving the circle q j Q , the pair ( a i ,  (a i , q j )), and this arrow leads to a circle corresponding to  (a i , q j ).

The resulting drawing is called automaton graph or, Moore diagram . For not very complex automata, this method is more illustrative than tabular.

We recommend reading

Plumbing

Two tests showed two strips: the principle of the pregnancy test, instructions for use, result, ultrasound and gynecologist consultation What to do the test shows two strips

Furniture

When to register for pregnancy: specific dates and the need for registration

Furniture

What drops in a nose that. Types of nasal drops. Drops beetroot from the common cold

Vacation home

What is the reason for the constant desire to drink?

Wallpaper

Centralized library system of the Khaibullinsky district of the Republic of Bashkortostan Bianka Igor Kubersky

Finishing

Goat cheese cheese at home recipe with photo step by step