R. M. Babakov

For a finite state machine with a datapath of transitions, a new algebraic synthesis algorithm is proposed that combines the enumeration of state coding ways with the enumeration of transition operations. The algorithm is based on the representation of any transition operation in the form of an arithmetic-logical operator over two operands, which are the code of the state machine’s current state and a constant of the corresponding format. This allows you to automate the enumeration of transition operations by enumerating the constants in the used operations within the range of values of the state codes of the finite state machine. The result of the algorithm is a set of solutions of the algebraic synthesis problem, each of which contains values of the state codes and a set of values of the constants of the used operations. The combination of enumeration of transition operations with enumeration of state coding ways expands the search area and increases the number of solutions found for the algebraic synthesis problem compared to the prototype algorithm that does not use enumeration of transition operations. A software implementation of the proposed algorithm was performed, confirming its correctness and effectiveness. Keywords: finite state machine, datapath of transitions, graph-scheme of algorithm, algebraic synthesis, enumeration of transition operations.

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.