AbstractIn this paper, we use a new mathematical tool, semi‐tensor product of matrices, to investigate the problem of simplification of finite state machines (FSMs) in a mathematical manner. First, based on the dynamic equations of state transition and output behavior which are developed recently, an algebraic criterion of k‐difference states is established. Second, using the criterion, a scheme is designed to construct the incompatible graphs of FSMs. Third, with the incompatible graphs and the method of searching internally stable sets of graphs proposed by the authors, a solution is proposed to obtain all of the compatible state set (CSS) of FSMs. Then, with the aid of the CSS, we investigate three kinds of structures of state space of FSMs, including compatible cover of state set (CCSS), representative set of state set (RSSS), and minimum representative set of state set (MRSSS); necessary and sufficient conditions are proposed to formulate the three kinds of structures. Finally, examples are given to exemplify minimum realizations of FSMs by these conditions.