Automata, methods of specification of
The various ways of describing automata and their functioning or behaviour. The method of specification of an automaton will depend on the approach to the concept of an automaton. If the macro-approach is adopted (cf. Automaton, finite), it is the external behaviour of an automaton which is described. If the micro-approach is adopted, the definition should include a description of the elements from which the automaton is constructed, and the schemes of their composition. Methods of specifying finite automata are described below.
Macro-approach.
To specify a finite automaton for given alphabets
,
and
is tantamount to describing the functions
and
or to describing the behaviour of this automaton (cf. Automaton, behaviour of an). The functions
and
are often defined by means of a table, a diagram or a matrix of transitions. The table of transitions
of the automaton
consists of two subtables
and
,
,
,
. The functions
and
are defined by
,
. If all the columns of
coincide, the table
defines a Moore automaton. For instance, let
,
,
; the table
(Fig. a) will then specify the functions
and
of some automaton
(Fig. bshows the subtables
and
of
).
Figure: a014060a
Figure: a014060b
The diagram of (transitions of) an automaton is an oriented graph with a one-to-one correspondence between the vertices of the graph and the elements of
, and between the edges of the graph and certain sets of pairs of the form
,
,
. Each vertex of
is the starting point of at least one edge, and the set
of all pairs assigned to the edges with the same vertex as their origin has the form
. The functions
and
are then defined as follows:
,
if the pair
is assigned to the edge issuing from from
and if this edge ends in the vertex
. It is convenient to formulate certain properties of automata in the language of diagrams (connectivity of an automaton, attainability of states, etc.). Fig. c shows the transition diagram of the automaton
.
Figure: a014060c
The transition matrix is used to describe the functioning of the transition system (cf.Automaton, finite). It is represented by the
-matrix
whose elements are subsets of the alphabet
(including the empty subset) such that
if and only if
, so that for any
the relations
if
and
are true. In order to extend the function
to the set
(where
is the set of all words over the alphabet
including the empty word), one considers the sequence of powers of the matrix
. Multiplication of
by itself is carried out by the usual algorithm, using the operations of concatenation and union of word sets instead of multiplication and addition. If
is a word of length
and
where
is an element of the matrix
, one has
. Thus, the transition matrix
of the transition system
and the matrix
have, respectively, the forms:
![]() |
![]() |
A number of minimization (reduction) algorithms and algorithms of automaton synthesis are associated with these methods of specifying automata.
In order to specify the behaviour of an initialized (not necessarily finite) automaton (transformer), one must define the function
which maps
into
(or
into
, where
are the sets of all the superwords over the alphabets
and
, respectively).
Figure: a014060d
This function may be defined by means of an information tree. From each vertex of the information tree there issue edges, which are in one-to-one correspondence with the respective letters of
. To each vertex is assigned a state of the automaton
, while to each edge is assigned a letter of
in the following way. The state
is assigned to the root. If the state
has been assigned to some vertex, the letter
is assigned to the edge corresponding to the letter
from
, while to the vertex in which this edge terminates the state
is assigned. To each word
corresponds a unique sequence
of edges of this tree such that
issues from the root and
issues from the vertex of termination of
. The word
, where
is the letter from
assigned to the edge
,
, is identical with the value
. If the function
is realized by a finite automaton, the corresponding information tree may be effectively determined by means of a finite subtree. Fig. d shows the subtree of the initialized automaton
(the left-hand edges, issuing from the vertices, correspond to the symbol
, while the right-hand edges correspond to the symbol
).
The behaviour of a finite automaton (acceptor) in terms of a representable event (super-event) may be effected with the aid of a regular expression (cf. Regular event). Such events may also be specified as sets of words generated (derived) in some formal system (a semi-Thue grammar, etc.). In this case the semi-Thue system is given as the quadruple where
are finite alphabets,
,
is an axiom scheme of the form
and
is the set of schemes of derivation rules of the form
,
, where
,
and
is a variable which assumes values from
. If, moreover,
and
belong to
, one has
. The word
is deducible in the system
if there exists a sequence of words
such that
is obtained from
,
, by the application of a certain rule from
,
and
does not contain the rule
. A grammar generating a regular event has a similar form. It is given by the quadruple
where
from
is an axiom,
is the set of rules of the form
or
. The word
is deducible in
if
includes the rules
,
. Algorithms which yield the transition matrix of an automaton from formal schemes of this type are known. Thus, an event represented in the acceptor
by the state
may be defined, for example, as the set of words that are deducible in the semi-Thue system
![]() |
![]() |
![]() |
There exist several other ways of specifying an automaton. For instance, a (necessarily finite) transition system may be specified as an algebra
where
is the set of unary operations on
such that
. Thus, the transition system
may be regarded as the algebra
, where
,
,
,
. One may also consider the algebra
where
is the set of words of the form
,
,
and
is the set of unary operations on
such that
. The algebra
is defined by the system of
-generators and the set of defining relations
. Such an algebra specifies a (usually partial) automaton
such that if
is a relation from
, the relation
is true. For example, the transition system
may be specified by a system of
-generators and the set of defining relations
. It is then assumed that
,
.
The behaviour of an automaton may be described in the language of the logic of one-place predicates. A choice of the class of formulas defining a finite automaton may be performed in various ways. The description may be incomplete, because the choice defines a class of automata whose the behaviour is identical to within the accuracy of this description. For instance, the "questionnaire" approach involves specifying classes of automata with the aid of fragments of information trees, a partial definition of the functions and
, etc.
The above ways of specifying automata may also be applied, with suitable modifications, to the behaviour of certain generalized finite automata (non-deterministic, infinite, etc.; cf. Automaton). Thus, the elements of the table of a finite, non-deterministic automaton may consist of arbitrary subsets of the set
. The behaviour of a finite, non-deterministic acceptor is described by a regular expression, as in the case of a deterministic acceptor. Other generalizations of finite automata are finite probabilistic automata (cf. Automaton, probabilistic), automata over terms, mosaic structures, etc.
To specify a probabilistic automaton on known alphabets
,
,
means to specify, for any given
and
(
,
) an arbitrary probability measure
on the set of all pairs
,
,
. To do this, one usually considers a system of square matrices with non-negative elements
![]() |
![]() |
such that each matrix is stochastic. The measure
is defined by the relation
. The probabilistic automaton
is considered in conjunction with a certain initial probability distribution on the set
:
![]() |
Sometimes probabilistic automata are defined by specifying only the matrices or only the matrices
, where
![]() |
. Any finite Markov chain can be regarded as a finite probabilistic automaton in which the matrices
,
, are identical. The system of matrices shown below defines some probabilistic automaton
(
,
,
) and the matrices
,
,
,
of this automaton:
![]() |
![]() |
![]() |
![]() |
In order to define a finite automaton over terms when the alphabets
and
are known one must first specify a mapping
of the set
into the finite set of non-negative integers such that there exists at least one element
for which
and, secondly, one must define, for each
,
, a
-ary function
mapping the set
into
. To each element
for which
there corresponds an element
, called an initial state of the automaton. For example, if
,
,
,
,
,
,
,
,
, then the functions
,
,
define some automaton over terms
with initial state
.
In order to specify a mosaic structure (an infinite union of transition systems of the form , where
, cf. Automaton), one must define for each integral point of the
-dimensional space an ordered set of integral points; this set is called its neighbourhood. The input alphabet
of the transition system
placed at a given point is the Cartesian product of the set of states of the transition systems placed at the points of its neighbourhood. For example, let
, and let the ordered set
be the neighbourhood
of an integral point
of the two-dimensional space. In order to specify a uniform two-dimensional mosaic structure, the function
is defined as follows:
; in all other cases
. Here, the input alphabet
is the Cartesian product
.
Micro-approach.
A micro-approach definition of a structural automaton describes its constituent elements and the scheme of their combination. This description may be detailed or more general. It is frequently restricted to the so-called canonical scheme of the construction of an automaton. The elements then divide into two groups: functional elements (one-state automata) and memory elements. The canonical scheme (Fig. e) consists of two functional blocks and
to which are added Moore automata
,
, as memory elements. The blocks
and
consist of functional elements. When the structure is defined in this way, these blocks are not further described, but a specification is given (e.g. by means of tables) of the vector functions realized by these blocks:
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
where and
are the input and the output alphabets, respectively, of the canonical scheme.
Figure: a014060e
Figure: a014060f
This scheme specifies the structural automaton , where
, while the functions
and
are defined as follows:
![]() |
![]() |
![]() |
![]() |
An important example of structural automata are logical networks (cf. Automaton, finite). Fig. f shows the canonical scheme of an automaton isomorphic to the automaton
(cf. Fig. cfor its diagram),
. The automaton
is a Moore automaton such that
,
.
Structural automata are frequently described by means of canonical equations, i.e. systems of the form
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
where is an integer parameter,
, while the functions
,
,
,
, and the variables
,
, take their values from the set
. A canonical scheme in which all the memory elements are identical corresponds to this system:
, where
,
;
,
. The functioning of the automaton
may essentially be described as follows. At the moment
suppose that the letter
is assigned to the input of
, then the same letter is produced as the output of
at the moment
. Let Fig. f represent an automaton
whose canonical equations have the form
![]() |
![]() |
![]() |
In the general case, a description of structural automata involves defining a selection of elementary automata and a certain class of "correctly constructed" schemes (networks), the latter usually being defined by induction.
References
[1] | C.E. Shannon (ed.) J. McCarthy (ed.) , Automata studies , Princeton Univ. Press (1956) |
[2] | V.M. Glushkov, "Synthesis of numerical automata" , Moscow (1962) (In Russian) |
Comments
See the Editorial Comment to the article Automata, equivalence of.
Automata, methods of specification of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_methods_of_specification_of&oldid=11434