Minimization of Incompletely Specified Mealy Finite-State Machines by Merging Two Internal States

摘要

A heuristic method for the minimization of Mealy finite state machines (FSMs) with unspecified values of the output variables based on merging two states is considered. Necessary and sufficient conditions for the possibility to merge two states and for forming wait states are given. Algorithms for determining the set of state pairs that can be merged, algorithms for finding the best pair for merging, and for the minimization of the number of FSM states and FSM input variables are presented. The proposed method makes it possible to reduce the number of internal states by a factor of 1.22 on the average and sometimes even by a factor of 2.75. The number of FSM transitions is reduced by a factor of 1.32 on the average and sometimes by a factor of 2.27. Compared with the well-known STAMINA computer program, the proposed method does not reduce the number of states but considerably reduces the number of transitions by a factor of 1.55 on the average and sometimes by a factor of 3.92.