Examples of abstract automata that perform useful actions. Thus, at the level of abstract theory, the functioning of a digital machine is understood as the transformation of input words into output words

Theory abstract automata

Vladimir 2006

Tutorial for full-time and part-time students studying specialties
in area computer technology, computer science and management.

Part 1. Theory of abstract automata…………………………………………………..3

1.1. General information……………………………..………………………………………..3

1.2. Methods for specifying automata………………………………………………………4

1.3. Examples of abstract automata that perform useful actions…………...6

1.4. Behavior of an isolated synchronous automaton………………………………..8

1.5. Regular expressions and finite state machines…………………………………….10

1.6. Algorithms and Turing machines….………………………………………………………………...11

1.7. Elements of the theory of formal grammars and languages……………………………15

1.8. Conditions for automatic display………………………………………………………..20

1.9. Construction of an automaton graph using input-output sequences…………21

1.10. Transformation of automata……………………………………………………….22

Tasks and exercises………………………………………………………………..24

Literature………………………………………………………………………………25

PART 1. THEORY OF ABSTRACT AUTOMATA

General information

Abstract automaton (AA)– discrete information converter; is a set consisting of six elements:

S = (X, Q, Y, δ, λ, q 1 )

S– abstract automaton;

X– set of input symbols (input alphabet of the machine):

X = (x 1, ..., x m);

Q – set of automaton states:

Q = (q 1, ..., q n);

Y– set of output symbols (output alphabet of the machine):

Y = (y 1, ..., y p);

δ – function of machine transitions from one state to another:

q j = δ(q i , x k),

Where: q j– next (new) state of the machine; qi– current state of the machine;
x k– current input symbol;

λ – output function:

y l = λ (q i , x k);

q 1– initial state of the machine (the designation is also used q 0).

The machine is called final, if the sets X, Q, Y- finite.

Fig.1. Representation of an abstract automaton

In Fig. 1 t– discrete time: t = nT, Where T– interval (tact) separating discrete moments of time; If T= 1, then t = n, i.e. discrete time is compared to an ordered series of natural numbers.

An abstract automaton (AA) can be thought of as a "black box" with one input and one output, which can be experimented with without knowing what is inside.

Output symbol ( y l О Y) depends not only on the input symbol ( x О X), but also from
the state in which ( q i О Q) there is a machine gun. The machine operates in discrete time; this means that the elements of the automaton description are specified only at the discrete moments mentioned above.

Let us imagine that from some initial, for example, zero moment of time, input symbols are supplied to the input of the machine, forming input word of some length (the length of any i-th word is measured by the number of characters). At the output we get output word the same length (Fig. 2).

Fig.2. Converting input words to output words

This means that the automaton can be considered as a converter of input words into output words while preserving the length of the words. The alphabet symbols present at the input and output of the machine will also be called input and output signals.

In practice, two main models describing the functioning of AA have become widespread:

1. Mili model;

2. Moore's model.

Mili model.

The operating laws of the Mealy machine are presented as follows:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t), x(t))

t – this moment time;

t+1– next moment in time;

q(t+1)– state of the machine at the next moment of time;

q(t), x(t), y(t)– elements of the description of the machine at the current time.

Moore's model.

The operating laws of the Moore machine are presented as follows:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t))

In Moore's model, the output signal explicitly depends only on the state, and indirectly -
and from the input signal.

Any machine can be designed according to one model or another.

Methods for specifying automata

Consider two main ways to define automata:

Tabular method

Automatic Miles

For a Mealy machine, the tabular method consists of constructing two tables: a transition table (TP) and an output table (TV).

b) Output table

Rice. 4. Table of transitions and outputs

Example. Transitions and outputs table:

Graph method

The automaton is represented by an oriented connected graph (digraph), the vertices of which correspond to the states of the automaton, and the arcs correspond to transitions from the state
into condition. The designations of input and output signals are distributed differently in Mealy and Moore automata.

Let's construct graphs for the Mealy and Moore automata using the above tables:

Rice. 5. Representation of the Mealy machine as a graph

Rice. 6. Representation of a Moore automaton as a graph

Comment: In a Mealy machine, the output signal is generated during a transition, and
in a Moore machine is present throughout the entire period of discrete time, until
the machine is in this state.

Deterministic automaton– an automaton in which there is complete certainty of transitions from all states depending on the input signals (under the influence of the same signal, the automaton cannot transition from any considered state to different states). The graph fragment shown in Figure 7 cannot belong to a deterministic automaton.

Fig.7. A fragment of a graph illustrating the uncertainty of transitions

Comment : Non-deterministic (for example, probabilistic) automata exist, but their consideration is not provided in this course.

Machine status qi called sustainable, if for any input signal x k, such that δ(q s , x k) = q i, the following relation is valid: δ(q i , x k) = q i. (Here qs– the state preceding qi). This means that the automaton does not change its state when the signal that brought it into the state is repeated at the next clock cycle qi. A fragment of the graph illustrating the stability of the state is shown in Figure 8.

Rice. 8. Steady state of the machine

The machine is called asynchronous, if each of its states q i О Q (i = 1, … , n) sustainable; otherwise the machine is called synchronous. Synchronous automata are important for theory, but in practice asynchronous ones are more often used; Stability of states in asynchronous automata is achieved by introducing special synchronization signals.

Examples of abstract automata that perform useful actions

1. Machine for delaying the signal by one clock cycle (for storing by one clock cycle)

Since the automaton is binary, we introduce the following notation: x 0 = y 0 = 0; x 1 = y 1 = 1.

Rice. 9. Graph of an automaton for delaying a signal by one clock cycle

A simple analysis shows that the output signal in the current clock cycle repeats the input signal that was one clock cycle earlier.

2. Automatic machine for checking binary sequences for parity.

Let's describe this machine with tables and a graph:

Transition table and output table:

Rice. 10. Graph of an automaton for checking a binary sequence for parity

Analysis shows that “0” at the output is automatically generated when the number of ones at the input is even, and “1” at the output is generated when the number of ones at the input is odd.

Both considered machines have a “weak” memory, but weak in in different ways.
The first machine has a “short” memory in time (it remembers only one signal).
The second machine has a “long” memory (the length of the input sequence can be any), but it distinguishes ( recognizes) only two classes of sequences.

3. Automatic device for delaying the signal by two clock cycles.

The machine has four states, encoded in two binary digits:
q 0 = 00; q 1 = 01; q 2 = 10; q 3 = 11.

Rice. 11. Graph of an automaton for delaying a signal by two clock cycles

Advantages of the applied coding:

· the first digit of the status code shows what signal the machine produces (it can easily be converted into a Moore machine); the second digit of the code shows under the influence of which signal the machine comes into this state.

· it is easy to check that the output signal repeats the input signal after two clock cycles.

4. A binary serial adder implemented for one bit of the input code.

The machine has two states: q 0 – no carryover (the addition of operand digits does not require taking into account the carryover unit from the previous code digit);

q 1 – there is a carryover (the unit of carryover must be taken into account).

Rice. 12. Graph of a one-bit binary sequential adder

In the numerator of the “fraction” written for each of the arcs of the graph, the digits of the terms are indicated; in the denominator – the result of summation in the current digit. The adder allows you to add binary sequences of arbitrary length.

A digital (discrete) machine can be interpreted as a device that receives, stores and converts discrete information according to a certain algorithm. From a certain point of view, automata can include both real devices (computers, living organisms, etc.) and abstract systems (mathematical machines, axiomatic theories

General theory automata are divided into abstract and structural. The difference between them is that abstract theory, abstracting from the structure of the automaton (i.e., not being interested in the method of its construction), studies only the behavior of the automaton relative to external environment. The abstract theory of automata is thus close to the theory of algorithms, being essentially its further detailing. In contrast to the abstract theory, the structural theory is interested in both the structure of the automaton itself and the structure of the input influences and reactions of the automaton to them. Structural theory studies methods for constructing automata, methods for encoding input influences and reactions of the automaton. Thus, the structural theory of automata is a continuation and further development abstract theory. Based on the apparatus of Boolean functions and the abstract theory of automata, the structural theory gives effective recommendations on the development of real computing devices.

An abstract digital automaton A is defined by a set of five objects where is the set of input signals of the automaton A (the input alphabet of the automaton A); - set of states of automaton A (alphabet of states of automaton - set of output signals of automaton A (output alphabet of automaton A); - transition function

of an automaton A, which specifies a mapping, i.e., assigns to any pair of elements of a Cartesian product of sets an element of the set - a function of the outputs of the automaton A, which specifies either a mapping or a mapping

In other words, the transition function shows that the automaton A, being in a certain state when the input signal appears, goes into a certain state. The latter can also be written by the expression The output function defining the mapping shows that the automaton L, being in a certain state when the input signal appears, produces an output signal. The latter can be written as

According to the method of forming the output function, three types of abstract automata are distinguished: Mealy automaton, Moore automaton, C-automaton. In an abstract Mealy automaton, the output function X defines the mapping. In an abstract Moore automaton, the output function defines the mapping. In the abstract C-automaton, two output functions X are introduced, and they define the mapping, respectively. In this case, the alphabet of outputs of the C-machine is either

An arbitrary abstract Milan or Moore automaton has one input and one output channel (Fig. 10.1). Arbitrary abstract C-automaton has one input and two output channels (Fig. 10.2).

There are fully defined and partial automata.

An abstract digital machine whose transition function and output function are defined for all pairs is called fully defined.

An abstract digital automaton is called partial if its transition function or output function, or both of these functions are not defined for all pairs

An abstract digital automaton is called initial if a special initial state is identified on the set of its states 5, i.e., the initial abstract automaton is determined by a set of six objects. The selection of an initial state on the set is explained by purely practical considerations related to the often arising need to fix the conditions for the start of the operation of the automaton.

An abstract automaton is said to operate in discrete automaton time, and transitions from state to state are instantaneous. At each moment of discrete time, the automaton is in some state from a set of states. If the automaton is initial, then at the initial moment of time it is always in the initial state. At the moment of being in the state, the automaton is able to perceive at the input a letter of the input alphabet in accordance with the function of the outputs X, it will at the same moment in time produce a letter of the output alphabet and, in accordance with the transition function, will move to the next

state According to the definition of an abstract automaton, the Mealy automaton in this case is characterized by a system of equations:

Moore automaton - a system of equations;

and the C-automatic machine is a system of equations:

In other words, if an input word is supplied letter by letter to the input of an initial abstract Mealy or Moore automaton set to the initial state, then at the output of the automaton the letters of the output alphabet and the output word will appear sequentially. For the case of a C-automaton, two consequences will appear at its outputs: in an abstract C-automaton, the output signal is issued with all premiums while the automaton is in the state. The output signal is barked during the action of the input signal when the C-automaton is in the state.

Thus, at the level of abstract theory, the functioning of a digital machine is understood as the transformation of input words into output words.

The concept of state in the definition of an abstract automaton was introduced due to the fact that most real processes controlled by actually built digital automata require knowledge of the history of the development of the process in time for their correct flow. In other words, the output signal produced by the machine in this moment time, is determined not only by the input effect on the machine, but also by the state in which the machine was at that moment in time. For example, if you need to build an automatic machine to control the switching of a traffic light, provided that only the signal “switch the traffic light” is received at the input of the machine, then at each moment time, in order to organize the correct operation of the machine, in addition to the input signal “switch the traffic light”, it is necessary to have information about the position of the traffic light at the previous point in time. This information is provided by the presence of various states of the abstract automaton. Abstract digital automata that correspond to the introduced definition of an abstract automaton are also called abstract automata with memory, since the existence of many different states in an automaton is possible only if the automaton has memory.

A number of processes controlled by real automata do not require knowledge of the prehistory of the development of the process in time for their correct flow. In automata that control such processes,

Table 10.1

the output signal is determined only by the input influence on the machine. These automata at the abstract level of representation are defined using a triple, where the output function specifies the mapping and are called abstract automata with trivial memory or combinational automata. The simplest analogue of a combination machine can be read as an ordinary electric flashlight, provided that the input action is pressing the “On” button, and the output signal is the lighting of the flashlight bulb.

Alphabets of inputs, states and outputs of automata are specified as ordinary sets, for example, by listing their elements. The functions of transitions and outputs can be specified matrix, graphically and analytically. Therefore, any abstract automaton can be defined in three ways! matrix, graphically and analytically

With the matrix method, the automaton is represented either by two tables: a transition table and an output table, or by a connection matrix. The transition table specifies the mapping, i.e., it determines the transition function of the automaton. The output table, depending on the type of the automaton in question, specifies either a mapping or, i.e., it determines function of machine outputs.

The transition table of an arbitrary fully defined abstract automaton is constructed as follows. The columns of the table are marked with the letters of the input alphabet of the automaton, and the rows of the table are marked with the letters of the alphabet of states of the automaton. In the cell of the transition table located at the intersection of the column marked by the input signal and the row marked by the state, a state is placed that is the result of the transition of the automaton from the state under the influence of the input signal, which is determined by the expression Example, the transition table of some abstract fully defined automaton with an input alphabet and an alphabet of states is presented in table 10.1. If the abstract automaton is partial, then in the cell of its transition table located at the intersection of the column marked by the input signal and the row marked by the state (provided that the transition from the state under the influence of the input signal is uncertain), a dash is placed, and any input word leading to the specified transition is prohibited. Filling the remaining cells is similar to the case of a fully defined automaton. An example of a transition table for some abstract partial automaton with an input alphabet and an alphabet of states is presented in Table. 10.2. The type of transition table does not depend on the type of automaton being specified (Moore automaton, Mealy automaton, C-automaton). The tables of outputs of the Moore, Mealy, and S-automata have differences. The table of outputs of a fully defined machine Mili is constructed as follows. The identification of columns and rows, as well as the table format, corresponds to the transition table of a fully defined automaton. In the cell of the output table,

Table 10.2

Table 10.3

Table 10.4

located at the intersection of the column marked by the input signal and the row marked by the state, an output signal is placed that the Mealy automaton produces, being in a state in the presence of an input signal, which is determined by the expression An example of a table of outputs of some abstract fully defined Mealy automaton with an input alphabet, an alphabet of states and an output alphabet is presented in table 10.3.

The table of outputs of a fully defined Moore automaton is constructed more simply: each state of the automaton is assigned its own output signal. An example of a Moore machine output table with an alphabet of states and an output alphabet is presented in Table 10.4.

Obviously, an abstract fully defined C-automaton is given by two output tables, the first of which is the output table of the Mealy automaton, and the second is the output table of the Moore automaton.

If the Mealy machine is partial, then in some cells of its output table there may be a dash, indicating the absence of an output signal. In this case, a dash must be placed in those cells of the output table that correspond to the same cells with a dash in the transition table of the Mealy machine. The latter is due to the fact that if in a partial Mealy automaton there is a pair ) and such that the transition from a state under the influence of an input signal is undefined, then, naturally, the value of the output signal at such a (non-existent) transition is also undefined. An example of a table of outputs of a partial Mealy automaton specified by a transition table (Table 10.2) with the output alphabet is presented in Table. 10.5

The dashes in some cells of the output table of Moore's partial automaton are not related to the dashes in the cells of its transition table. This is determined by the fact that the output signal of the Moore machine depends only on the state in which the machine is located. For example, the table of outputs of a partial Moore automaton specified by a transition table (Table 10.2),

Table 10.5

Table 10.6.

Table 10.7

can also be presented as a table. 10.4, if in each of its states the machine produces some kind of output signal, and as in Table. 10.6, if the value of the output signal of the machine for some states is undefined.

In practice, the transition and output tables of an automaton are often combined into one table, called the marked transition table of the automaton. The marked transition table of a fully defined Mealy automaton, represented by a transition table (Table 10.1) and an output table (Table 10.3), is summarized in Table. 10.7. The marked transition table of the partial Moore automaton (Table 10.2) and the output table (Table 10.4) are summarized in Table. 10.8.

In addition to the transition and output tables discussed above, an arbitrary abstract automaton can be described by a connection matrix. This description is one of the ways to specify abstract automata in a matrix manner. The connection matrix of an arbitrary abstract automaton is square and contains as many columns (rows) as the number of different states the automaton in question has. Each column (row) of the connection matrix is ​​marked with a state letter of the machine. If the automaton is initial, then the first column from the left and the first row from the top of the matrix of its connections are marked with the letter of the initial state of the automaton. In the cell of the connection matrix located at the intersection of the column marked with the letter of the state and the row marked with the letter of the state of the automaton, an input signal (or a disjunction of input signals) is placed. , under the influence of which the automaton transitions from state to state. If the connection matrix is ​​given by an abstract Milne automaton, then next to the letter of the input signal in parentheses the letter of the output signal is indicated that the Mealy automaton produces, making the transition. Connection matrix of some Mealy automaton, represented by the marked transition table (Table 10.7), shown in Fig. 10.3.

If the connection matrix is ​​specified by an abstract Moore automaton, then the output signals mark the states of the automaton that identify the rows of the connection matrix.

Table 10.8

In the graphical method of specifying, abstract automata are represented by directed graphs; states of the automaton are represented by the vertices of the graph, and transitions between states are represented by arcs between the corresponding vertices. In this case, each arc of the graph is assigned a certain letter of the input alphabet of the automaton, indicating that a given transition of the automaton is carried out only when an input signal appears, and each vertex of the graph is assigned a letter of the corresponding state of the automaton. If a Mila machine is represented by a graph, then the output signals of the machine are placed on the arcs of the graph (in accordance with the table of outputs of the machine) next to the letter of the input signal. An example of a Mealy automaton graph specified by a transition table (Table 10.1) and an output table (Table 10.3) is shown in Fig. 10.4. If a Moore automaton is represented by a graph, then the output signals of the automaton are placed near the vertices of the graph (in accordance with the table of outputs of the automaton). An example of a Moore automaton graph specified by a transition table (Table 10.2) and an output table (Table 10.4) is shown in Fig. 10.5.

In the analytical method of specifying, abstract automata are represented by four objects where defines the mapping for each state of the automaton. In other words, with the analytical method of specifying for each state of the automaton, a mapping is indicated that is a set of all triplets and such that, under the influence of an input signal, the automaton makes a transition from state to state, while producing an output signal. In relation to general definition abstract automaton, the latter is equivalent to describing the functions and X in accordance with the expressions: The mapping is written as follows:

The analytical task of the Mealy automaton, represented by the marked transition table (Table 10.7), has the following form.

Let us consider an equivalent transformation of automata. Equivalent automata are those that induce the same mapping from a set of words in the input alphabet to a set of words in the output alphabet. Let us consider only the transformation of the Moore automaton into the equivalent Mealy automaton. The transformation of a Mealy automaton into an equivalent Moore automaton is somewhat more complicated.

The transition from the Moore automaton to the equivalent Mealy automaton is convenient to carry out using the graphical method of specifying automata. In this case, it comes down to transferring the output signal produced by the Moore automaton in the state to the arcs included in the vertex marked with the letter. In the matrix method of specifying, the transition table of the Mealy automaton coincides with the transition table of the Moore automaton, and the output table of the Mealy automaton is obtained from its transition table by replacing the letter state located at the intersection of the column marked by the input signal and the row on the output signal issued by the Moore machine in the state

Development real machines(represented at least at the level of electrical circuit diagrams) requires their assignment first at an abstract level, followed by a transition to a structural level that takes into account the logical elements used in the circuit of the machine and the connections between them. In this regard, the task of synthesizing an abstract automaton arises, starting from some initial, for example, verbal description his works. Existing algorithms for the synthesis of abstract automata are usually not used in practice due to the complexity and cumbersomeness of the calculations and are therefore not included in the textbook material. However, for a better understanding of the concept of an abstract automaton and how to define it, here we consider an example of the synthesis of an abstract automaton, based on purely speculative considerations.

Example. Build an abstract digital automaton for controlling traffic light switching, provided that only the “switch traffic light” signal is received at the input of the automaton. Let us denote this signal by the letter and its absence by the letter

Obviously, the input alphabet X of such an automaton will consist of two letters: Since the synthesized automaton must ensure that the traffic light switches to red, yellow and green color, then we introduce three corresponding output control signals. We also assume that at the moment of the start of operation the machine is in the state The operation algorithm is trivial; a possible solution for the Mealy machine is shown in Fig. 10.6, and for the Moore machine - in Fig. 10.7. For (simplification, we assume that at the initial moment of time, the Moore automaton produces an output signal “turn on green.” Note that to construct the automaton graph, you will need to introduce four different states. The number of states can be reduced, for example, by increasing the number of input signals of the automaton or expanding the capabilities of the automaton in in terms of remembering the history of the development of the control process over time (in the example under consideration, only the moment of issuing the last output signal is remembered).

In conclusion, we note that we are considering only deterministic automata for which the condition of unambiguous transitions is satisfied: an automaton that is in a certain state cannot transition to more than one state under the influence of any input signal. An automaton specified by a transition table is always deterministic, since at the intersection of a column and a row of the transition table, only one state is written if the transition is defined, and a dash is written if the transition is not defined. In relation to the graphical method of specifying an automaton, the uniqueness condition means that in the graph of the automaton, two or more arcs marked by the same input signal cannot emerge from any vertex.

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: " Most of automata theory has been successfully used in system programs and text filters in UNIX OS. This allows many people to work 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.

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

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 language high level 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.

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.

States;

- input signals: "n", "2" and "5".

Output reactions:

Example 3 1. Electronic clock (Fig. 1.5).

Various electronic watches functionality 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 watch shown in Figure 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.

At the output, it produces symbols (in the general case) of a different alphabet.

Abstract automaton

Formally, an abstract automaton is defined as five

Limiting the number of parameters of an abstract automaton defined the concept of a finite automaton.

The functioning of the automaton consists of generating two sequences: a sequence of the next states of the automaton and a sequence of output symbols, which for a sequence of symbols unfold at discrete time moments t = 1, 2, 3, ... Discrete time moments are called clock cycles.

The functioning of the automaton at discrete moments of time t can be described by a system of recurrent relations:

To clarify the properties of abstract automata, a classification has been introduced.

Abstract automata form a fundamental class of discrete models, both as a model in their own right, and as a fundamental component of Turing machines, store-memory automata, finite state machines, and other information transformers.

Wikimedia Foundation. 2010.

• State diagram (automaton theory)
• Nagorno-Karabakh

See what “Abstract automaton” is in other dictionaries:

abstract automaton- abstraktusis automatas statusas T sritis automatika atitikmenys: engl. abstract automaton vok. abstrakter Automat, m rus. abstract automaton, m pranc. automate abstrait, m … Automatikos terminų žodynas

Machine- In Wiktionary there is an article “automatic” Automatic: Automatic is a device that independently performs some actions ... Wikipedia

State machine- A finite state machine is an abstract machine without an output stream, the number of possible states of which is finite. The result of the machine's operation is determined by its final state. Exist various options finite machine tasks. For example,... ... Wikipedia

TURING MACHINE- An abstract automaton (that is, a computer or other precise, defined mechanism), theoretically characterized by British mathematician Alan M. Turing in the 1930s. Basically, a Turing machine consists of a tape and a read head. Ribbon… … Dictionary in psychology

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

Automata theory- Automata theory is a branch of discrete mathematics that studies abstract automata, computers, presented in the form of mathematical models and problems that they can solve. Automata theory is most closely related to ... ... Wikipedia

Computer- Diagram of a personal computer: 1. Monitor 2. Motherboard 3...Wikipedia

Formal methods- Example of a formal specification using Z notation In computer science and engineering software formal methods is a group of techniques based on mathematical apparatus for... Wikipedia

1.1 Basic concepts

1.4 Relationship between Mealy and Moore models

1.5 Equivalent machines. Equivalent transformations of automata

1.6 Minimizing a number internal states machine gun

Bibliography

Introduction

Subject test work in the discipline "Applied Theory of Digital Automata" - "Abstract Digital Automata".

The purpose of the work is to become familiar with the basic concepts of abstract digital automata; types of abstract automata; ways of specifying abstract automata; the connection between the Mealy and Moore models; equivalent automata and equivalent transformations of automata; minimizing the number of internal states of the automaton and the Aufenkamp-Hohn algorithm.

1. Abstract digital automata

1.1 Basic concepts

A digital machine can be interpreted as a device that receives, stores and converts discrete information according to a certain algorithm. From a certain point of view, both real devices (computers) and abstract systems (mathematical models) can be classified as automata.

An automaton is a discrete information converter capable of accepting various states, transitioning from one state to another under the influence of input signals, and producing output signals.

The general theory of automata is divided into abstract and structural.

The abstract theory of automata, abstracting from the structure of the automaton (i.e., not being interested in the method of its construction), studies only the behavior of the automaton relative to the external environment. The abstract theory of automata is close to the theory of algorithms, being essentially its further implementation.

In contrast to the abstract theory of automata, the structural theory of automata is interested in both the structure of the automaton itself and the structure of the input influences and reactions of the automaton to them. Structural theory studies methods for constructing automata, methods for encoding input influences and the automaton’s reactions to them. The structural theory of automata is a continuation and development of abstract theory. Based on the apparatus of Boolean functions and the abstract theory of automata, structural theory provides effective recommendations for the development of real computer technology devices.

An abstract digital automaton (DA) is a mathematical model of a discrete control device.

Abstract TA is defined by a set consisting of six elements:

X=(x 1, x 2,. x n) - set of input signals (input alphabet);

Y=(y 1 , y 2 , y m ) - set of output signals (output alphabet);

A = ( a 0 , a 1 , a 2 ,. a N ) - set of states (alphabet of states);

a o - initial state (a o

- function of machine outputs, specifying either display (XxA)

In other words, the transition function

Output function shows that the automaton S, being in some state a j

The concept of state was introduced into the definition of an automaton due to the fact that there is often a need to describe the behavior of systems whose outputs depend not only on the state of the inputs at a given time, but also on some prehistory, i.e. from signals that were previously received at the system inputs. A state corresponds precisely to some memory of the past, allowing time to be eliminated as an explicit variable and outputs to be expressed as a function of states and inputs at a given time.

An abstract automaton operates in discrete automaton time t=0,1,2,. and transitions from state to state are instantaneous. At each moment t of discrete time, the automaton is in a certain state a (t) from the set A of states of the automaton, and at the initial moment of time t=0 it is always in the initial state a o. At time t, being in state a (t), the automaton is able to perceive signal x (t) on the input channel

1.2 Types of abstract automata

According to the method of forming the output function, three types of abstract automata are distinguished: Mealy automaton, Moore automaton, C-automaton. The Mealy machine is characterized by a system of equations:

a (t+1) = δ (a (t), x (t)). (1-1)

Moore's automaton - system of equations:

a (t+1) = δ (a (t), x (t)). (1-2)

C-automatic - system of equations:

a (t+1) =δ (a (t),x (t)).

An arbitrary abstract Mealy or Moore automaton (Fig. 1.1.) has one input and one output channel. An arbitrary abstract C-automaton has one input and two output channels (Fig. 1.2.).

Figure 1.1 - Abstract automaton

Figure 1.2 Abstract C-automaton

If the input of an abstract Mealy or Moore automaton, set to the initial state a o, is supplied letter by letter with a certain sequence of letters of the input alphabet x (0), x (1),. is the input word, then at the output of the machine the letters of the output alphabet y (0), y (1), will appear sequentially. - exit word. For the case of a C-automaton, two sequences will appear at its outputs: y 1 (0), y 1 (1),. and y 2 (0), y 2 (1),. In an abstract C automaton, the output signal y 2 (t) =

Thus, at the level of abstract theory, the functioning of a digital machine is understood as the transformation of input words into output words.

There are fully defined and partial automata.

A fully defined abstract digital automaton is one whose transition function or output function, or both of these functions, are defined for all pairs of transitions (x i ,a j).

An abstract digital automaton is called partial if its transition function or output function, or both of these functions are not defined for all pairs of transitions (x i,a j).

An abstract digital automaton is called initial if the initial state a o is distinguished on the set of its states A.

1.3 Methods for specifying abstract automata

To set state machine S, it is necessary to describe all elements of the set: S=( X,A,Y,

In the tabular method, the machine is specified by two tables: a transition table and an output table, or a connection matrix. The transition table of an arbitrary fully defined automaton is constructed as follows: the rows of the table are marked with the letters of the input alphabet of the automaton, and the columns of the table are marked with the letters of the alphabet of states of the automaton; In the cell of the transition table located at the intersection of the row marked by the input signal x i and the column marked by the state a j, the state a k is placed, which is the result of the transition of the machine from the state a j under the influence of the input signal x i, which is determined by the expression a k =