You get a bonus - 1 coin for daily activity. Now you have 1 coin

4: Construction of abstract automata according to the firmware graph scheme

Lecture



Annotation: Describes how to move from graph-circuit firmware to abstract machines. The GSA markup methods and the rules for constructing Mile and Moore automata on them are given. The concept of a combined automaton and methods of its presentation are given.

Keywords: definition, graph, graph vertices, microprogram, path, arc, logic function, unconditional transition, software, Mili automaton, Moore automaton, automaton, control device, abstract automaton, interval, input, combined automaton, multiple states

4.1 The transition from the GSA MP to the graph of the abstract machine Miles

The transition is carried out in two stages. At the first stage, the number of states is determined by marking and marking the graph scheme; on the second, the definition of the automaton graph.

Markup rules:

  1. Symbol 4: Construction of abstract automata according to the firmware graph scheme mark the vertex entry following the initial operator in the GSA and the entry of the final vertex. (Fig.4.1, a).
  2. Characters 4: Construction of abstract automata according to the firmware graph scheme - the inputs of the vertices following the operator vertices (Fig.4.1, b).

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.1.

If as a result of the markup it turns out that several marked arrows enter the same vertex of the graph scheme, they are assigned the same symbol. Further symbol 4: Construction of abstract automata according to the firmware graph scheme considered as the initial state of the machine, and the characters 4: Construction of abstract automata according to the firmware graph scheme - as intermediate states of the automaton. Thus, the number of states of the automaton is determined by the number of different symbols 4: Construction of abstract automata according to the firmware graph scheme

The transition from the marked graph-schemes to the graph of the automaton is carried out in the following order.

The graph vertices represent all the states of the automaton and the symbols are written inside the circles. 4: Construction of abstract automata according to the firmware graph scheme , i.e. existing tags on the GSA.

On the graph-diagram of the firmware, the path is searched between two adjacent states. 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme . Paths are displayed by arcs. There may be three types of paths:

  1. If this path contains logical conditions, then the arc connecting the vertices 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme graph of an automaton, is marked by a logical function 4: Construction of abstract automata according to the firmware graph scheme whose value determines the transition of the automaton from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme and the operator 4: Construction of abstract automata according to the firmware graph scheme located between 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme (Fig.4.2).

    4: Construction of abstract automata according to the firmware graph scheme


    Fig. 4.2.
  2. If this path contains logical conditions, then the arc connecting the vertices 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme graph of an automaton, is marked by a logical function, the value of which determines the transition of the automaton from the state 4: Construction of abstract automata according to the firmware graph scheme in the as state and if on the way between 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme there is no operator vertex, then this fact is marked with a '-' symbol or a symbol 4: Construction of abstract automata according to the firmware graph scheme (empty operator, skip tact) (Fig.4.3);

    4: Construction of abstract automata according to the firmware graph scheme


    Fig. 4.3.
  3. If this path does not contain logical conditions, that is, there is an unconditional transition, then this is the third type path. Such a transition is denoted by "1" instead of a logical function and operator 4: Construction of abstract automata according to the firmware graph scheme located between 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme (Fig.4.4).

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.4.

The construction of the graph of the Mili automaton using the GSA firmware will be considered on the example of the GSA presented in Fig.4.5.

At the first stage, we will execute markup according to the above rules. We get five labels, highlighted by red crosses in Fig.4.5.

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.5.

At the second stage we build the graph of Moore’s automaton. We have five vertices of the graph corresponding to five states.

By GAW we find all the paths between adjacent marks. So from the label 4: Construction of abstract automata according to the firmware graph scheme in tag 4: Construction of abstract automata according to the firmware graph scheme there is a path of the third type, that is, an unconditional transition. This path passes through the operator vertex marked by the signal 4: Construction of abstract automata according to the firmware graph scheme which is carried out on the transition arc from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme .

Consider the paths leading from the label. 4: Construction of abstract automata according to the firmware graph scheme . There are three of them. First way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertex 4: Construction of abstract automata according to the firmware graph scheme and operator vertex 4: Construction of abstract automata according to the firmware graph scheme that is, it is the path of the first kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme with output signal 4: Construction of abstract automata according to the firmware graph scheme . Second way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertices 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme and operator vertex 4: Construction of abstract automata according to the firmware graph scheme that is, it is the path of the first kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme with output signal 4: Construction of abstract automata according to the firmware graph scheme .

Third way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertices 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme and does not pass through any operator vertex, that is, it is a path of the second kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme no output signal.

Consider the paths leading from the label. 4: Construction of abstract automata according to the firmware graph scheme . There are two of them. First way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertex 4: Construction of abstract automata according to the firmware graph scheme and operator vertex 4: Construction of abstract automata according to the firmware graph scheme , that is, this is the path of the first type, corresponding to the transition of the automaton from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme with output signal 4: Construction of abstract automata according to the firmware graph scheme . Second way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme goes through the same conditional vertex 4: Construction of abstract automata according to the firmware graph scheme and does not pass through any operator vertex, that is, it is a path of the second kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme no output signal.

From tags 4: Construction of abstract automata according to the firmware graph scheme there are also two ways and both of the second type without output: from 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme ; of 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme .

Of 4: Construction of abstract automata according to the firmware graph scheme there is one way in 4: Construction of abstract automata according to the firmware graph scheme the third type, passing through the operator peak 4: Construction of abstract automata according to the firmware graph scheme .

The result of the constructed abstract Mile automaton is shown in Fig.4.6.

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.6.

If we redesign the signals on arcs, for example, replacing 4: Construction of abstract automata according to the firmware graph scheme on 4: Construction of abstract automata according to the firmware graph scheme , 4: Construction of abstract automata according to the firmware graph scheme on 4: Construction of abstract automata according to the firmware graph scheme etc., and 4: Construction of abstract automata according to the firmware graph scheme on 4: Construction of abstract automata according to the firmware graph scheme , 4: Construction of abstract automata according to the firmware graph scheme on 4: Construction of abstract automata according to the firmware graph scheme , etc., we get the abstract Mile machine gun in its usual form.

4.2 Transition from the GSA MP to the graph of the abstract Moore machine

The transition is also carried out in two stages. At the first stage, the number of states is determined by marking and marking the graph scheme; on the second, the definition of the automaton graph.

Markup rules:

  1. Symbol 4: Construction of abstract automata according to the firmware graph scheme mark the starting and ending vertices of the GSA firmware.
  2. Characters 4: Construction of abstract automata according to the firmware graph scheme mark the operator vertices (Fig.4.7, b).

    4: Construction of abstract automata according to the firmware graph scheme


    Fig. 4.7.
  3. Different tops of the GSA should be labeled with different labels.

At the second stage, we construct the graph of Moore’s automaton, and the labels correspond to the vertices of the graph within which the output signal is recorded, since in the Moore’s automaton, the output signal depends only on the state and does not depend on the input signal.

As a result of the analysis of the markup, we see that between pairs of tags we have paths of the second and third types. Each path set the appropriate transition.

The construction of Moore’s automaton will be considered on the example of the GSA MP presented in Fig. 4.8.

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.8.

At the first stage, we will execute markup according to the above rules. We get six tags (Fig.4.8).

At the second stage, we build the graph of the Mile automaton. We have six vertices of the graph corresponding to six states. Inside each vertex we write the corresponding output signal.

By GAW we find all the paths between adjacent marks. So from the label 4: Construction of abstract automata according to the firmware graph scheme in tag 4: Construction of abstract automata according to the firmware graph scheme there is one path of the third type, that is, an unconditional transition. This path is represented by a transition arc from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme .

Consider the paths leading from the label. 4: Construction of abstract automata according to the firmware graph scheme . There are three of them. First way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertex 4: Construction of abstract automata according to the firmware graph scheme that is, this is the second type of path, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme . The second path passes through conditional vertices. 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme that is, this is also the path of the second kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme . Third way out 4: Construction of abstract automata according to the firmware graph scheme at 4: Construction of abstract automata according to the firmware graph scheme passes through conditional vertices 4: Construction of abstract automata according to the firmware graph scheme and 4: Construction of abstract automata according to the firmware graph scheme that is, this is the path of the second kind, corresponding to the transition from the state 4: Construction of abstract automata according to the firmware graph scheme in state 4: Construction of abstract automata according to the firmware graph scheme by condition 4: Construction of abstract automata according to the firmware graph scheme . The result of the constructed abstract Mile automaton is shown in Fig. Fig.4.9 /

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.9.

4.3 Abstract C-automat (combined automaton)

Very often, control devices require signals of both types: the first kind as in the abstract Mily machine and the second kind as in the abstract Moore machine. In Miles, the output signal depends on both the state and the input signal and is formed in the same discrete time interval in which the input signal arrives (Fig. 4.10, a).

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.10.

4: Construction of abstract automata according to the firmware graph scheme

In Moore’s automaton, the output signal depends only on the state, and the entire time when the automaton is in this state is output (Fig. 4.10 b):

4: Construction of abstract automata according to the firmware graph scheme

The combined automaton or 4: Construction of abstract automata according to the firmware graph schemeautomaton thus contains signals of both the first kind and second and is described by a figure of eight of the form:

4: Construction of abstract automata according to the firmware graph scheme

Where 4: Construction of abstract automata according to the firmware graph scheme - The set of states of the machine;

4: Construction of abstract automata according to the firmware graph scheme - many input signals;

4: Construction of abstract automata according to the firmware graph scheme - a set of output signals of the first kind;

4: Construction of abstract automata according to the firmware graph scheme - a set of output signals of the 2nd kind;

4: Construction of abstract automata according to the firmware graph scheme

4: Construction of abstract automata according to the firmware graph scheme

4: Construction of abstract automata according to the firmware graph scheme

4: Construction of abstract automata according to the firmware graph scheme

При графическом задании 4: Construction of abstract automata according to the firmware graph scheme - автомата на переходах указываются выходные сигналы 1 рода 4: Construction of abstract automata according to the firmware graph scheme , а в вершинах выходные сигналы 2 рода 4: Construction of abstract automata according to the firmware graph scheme (рис.4.11).

4: Construction of abstract automata according to the firmware graph scheme


Fig. 4.11.

Явное задание 4: Construction of abstract automata according to the firmware graph scheme - автомата требует описание всех составляющих и выполняется так же как и для автоматов Мили и Мура.

Табличное задание 4: Construction of abstract automata according to the firmware graph scheme - автомата состоит в представлении работы автомата двумя таблицами: таблицей переходов (табл.4.1) и таблицей выходов (табл.4.2), в которой в отличие от автомата Мили в верхней строке добавляются сигналы второго рода.

Таблица 4.1.
z\a a 1 a 2 a 3
z 1 a 3 a 1 a 1
z 2 a 1 a 3 a 2
Таблица 4.2.
\u h u 1 u 3 u 2
z\a a 1 a 2 a 3
z 1 w 1 w 1 w 2
z 2 w 1 w 2 w 1

The matrix task of 4: Construction of abstract automata according to the firmware graph schemean automaton consists in the description by two matrices similarly to the matrix representation of the Mily and Moore automata.

4: Construction of abstract automata according to the firmware graph scheme

See also


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Theory of Automata

Terms: Theory of Automata