ALGORITHM FOR SOLVING THE PROBLEM OF ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE WITH DATAPATH OF TRANSITIONS BASED ON A MATRIX APPROACH

A new algorithm for solving the problem of algebraic synthesis is proposed for a finite state machine with a datapath of transitions, which allows finding formal solutions to the problem for a given set of transition operations. The algorithm is based on the presentation of states encoding in the form of a transition matrix. This matrix is associated with a combined matrix of operations, which contains all possible options for the transformation of state codes using a given set of transition operations. The element-by-element comparison of matrices allows revealing the availability of a formal solution for the selected set of state codes. It is shown that the proposed algorithm makes it possible to find all possible solutions using a complete enumeration of the ways of state encoding. The speed of the proposed algorithm was evaluated when it was implemented in the Python language. Keywords: finite state machine, datapath of transitions, graph-scheme of algorithm, algebraic synthesis, states encoding.