Automata, minimization of

Minimization of the parameter values of automata which results in equivalent and, in a sense, optimal automata. The problem of minimization of automata arises during the synthesis of automata, and its specific nature will depend on the approach adopted in the study of the problem.

If the macro-approach is adopted, the usual procedure is to minimize the number of states of automata, thus obtaining minimal or reduced automata. The actual method of search for reduced automata will depend on the form in which they are defined and on their type of behaviour. If, for example, the behaviour of a finite automaton (cf. Automaton, finite), defined with the aid of, for example, a transition diagram, is understood to mean the system of finitely-determined functions (cf. Finitely-determined function) realized by the automaton, the minimal finite automaton equivalent to the initial automaton can be effectively found. This is based on Moore's theorem, according to which it may be established by an experiment of length $ n - 1 $ whether or not two states of an automaton with $ n $ states are distinguishable from one another. The minimization algorithm consists of constructing an automaton as defined above whose states correspond to the classes of indistinguishable states of the initial automaton, whereas the transition and the output functions are defined by means of representatives of these classes. The minimal automaton is unique up to a state-isomorphism. If the final automaton is considered as an acceptor representing — by means of the subset of isolated states — an event described with the aid of the given regular expression, the minimal automaton is effectively constructed, and the algorithm of its construction may be divided into two stages. In its first stage, the initial regular expression is used to construct some automaton, not necessarily minimal, representing the corresponding regular event. Such an automaton may be constructed, for example, by induction from the operations of union $ \cup $, concatenation $ \circ $ and iteration $ * $ which are included in the regular expression. The automata $ \mathfrak A _ {1} , \mathfrak A _ {2} $ and $ \mathfrak A _ {3} $ which represent, respectively, the events $ R _ {1} , R _ {2} $ and $ R _ {3} $ serve to effect the special constructions of the automata $ \mathfrak A _ {4} , \mathfrak A _ {5} $ and $ \mathfrak A _ {6} $ which represent the events $ R _ {1} \cup R _ {2} $, $ R _ {1} \circ R _ {2} $ and $ R _ {3} ^ {*} $; moreover, the number of states of $ \mathfrak A _ {4} $ does not exceed the product of the number of states of $ \mathfrak A _ {1} $ and $ \mathfrak A _ {2} $; the number of states of $ \mathfrak A _ {5} $ does, generally, not exceed the product of the number of states of $ \mathfrak A _ {1} $ with the number of all subsets of the set of states of $ \mathfrak A _ {2} $; while the number of states of $ \mathfrak A _ {6} $ does not exceed the number of subsets of the set of states of $ \mathfrak A _ {3} $. During the second stage of the algorithm the number of states of the resulting automaton is minimized in the usual way, the classes of indistinguishable final states of the initial automaton corresponding to the final states of the minimal automaton. The minimal automaton representing a given super-event is constructed in the same manner. There are unique (up to a state-isomorphism) minimal automata which represent given events and super-events.

A reduced automaton, which is unique up to a state-isomorphism, also exists for non-deterministic finite automata, and for both deterministic and non-deterministic infinite automata. In the former case, this automaton is found using a method similar to that in the case of finite automata discussed above, while in the second case its construction is, as a rule, non-effective. For a stochastic automaton with a finite number of states there exists, generally speaking, a continuum of various reduced automata are equivalent to the initial automaton. This is why there is no effective way of describing the set of reduced automata derived from a given stochastic automaton.

In the micro-approach to the study of finite automata, a given automaton is constructed starting from some finite selection of a basis $ \mathfrak B $ of logical networks. Given an automaton $ \mathfrak A $, defined, for example, by canonical equations, it is required to exhibit a logical network $ S $, constructed from the elements of the basis $ \mathfrak B $ using superposition and feedback operations, realizing $ \mathfrak A $ and containing a minimum number $ L ( \mathfrak A ) $ of elements of $ \mathfrak B $ necessary for the realization of this automaton. In this sense the network $ S $ will be the optimal scheme of the automaton $ \mathfrak A $. In the general case, the problem of realizing an arbitrary automaton $ \mathfrak A $ with the aid of networks over a basis $ \mathfrak B $ is unsolvable, and for this reason the complexity function $ L ( \mathfrak A ) $ of the automaton $ \mathfrak A $ cannot be calculated. If a basis of $ \mathfrak A $ is known to be complete (cf. Automata, complete systems of), the construction of any optimal network for $ \mathfrak A $ can be effectively realized e.g. in the following manner. It is known that the realizability check of an automaton $ \mathfrak A $ with the aid of a given network $ S $ can be effectively established. Moreover, for a given number $ l $ the number of networks over a base $ \mathfrak B $ of complexity at most $ l $ can be calculated, and all these networks can be effectively constructed. Therefore, a sequential inspection of all networks of complexity $ 1 \dots L ( \mathfrak A ) $ for the realizability of the automaton $ \mathfrak A $ may be used as the algorithm for constructing all optimal networks for a given automaton $ \mathfrak A $. The problem of the behaviour of the function $ L ( \mathfrak A ) $ and of certain of its generalizations is part of the general problem of synthesis of automata. There exist several heuristic algorithms for the synthesis of minimal schemes for automata, based on the special properties of the bases and on specific interpretations of the concept of optimality. For references see Automaton, finite.