Abstract: Motivated by the inconvenience or even inability to explain the mathematics of the state space optimization of finite state machines (FSMs) in most existing results, we consider the problem by viewing FSMs as logical dynamic systems. Borrowing ideas from the concept of equilibrium points of dynamic systems in control theory, the concepts of t-equivalent states and t-source equivalent states are introduced. Based on the state transition dynamic equations of FSMs proposed in recent years, several mathematical formulations of t-equivalent states and t-source equivalent states are proposed. These can be analogized to the necessary and sufficient conditions of equilibrium points of dynamic systems in control theory and thus give a mathematical explanation of the optimization problem. Using these mathematical formulations, two methods are designed to find all the t-equivalent states and t-source equivalent states of FSMs. Further, two ways of reducing the state space of FSMs are found. These can be implemented without computers but with only pen and paper in a mathematical manner. In addition, an open question is raised which can further improve these methods into unattended ones. Finally, the correctness and effectiveness of the proposed methods are verified by a practical language model.

从控制论观点审视有限状态自动机的状态空间优化

[1]Chen WY, 2007. The Theory of Finite Automata. University of Electronic Science and Technology of China Press, Chengdu, China (in Chinese).

[2]Cheng DZ, Qi HS, Zhao Y, 2012. An Introduction to Semi-tensor Product of Matrices and Its Applications. World Scientific, Singapore.

[3]Chu D, Spinney RE, 2018. A thermodynamically consistent model of finite-state machines. Interf Focus, 8(6):20180037.

[4]Dahmoune M, El Abdalaoui EH, Ziadi D, 2014. On the transition reduction problem for finite automata. Fundam Inform, 132(1):79-94.

[5]de Parga MV, García P, López D, 2013. A polynomial double reversal minimization algorithm for deterministic finite automata. Theor Comput Sci, 487:17-22.

[6]Gao N, Han XG, Chen ZQ, et al., 2017. A novel matrix approach to observability analysis of finite automata. Int J Syst Sci, 48(16):3558-3568.

[7]García P, López D, de Parga MV, 2014. Efficient deterministic finite automata split-minimization derived from Brzozowski’s algorithm. Int J Found Comput Sci, 25(6):679-696.

[8]Gören S, Ferguson FJ, 2002. Chesmin: a heuristic for state reduction in incompletely specified finite state machines. Proc Design, Automation and Test in Europe Conf and Exhibition, p.248-254.

[9]Gören S, Ferguson FJ, 2007. On state reduction of incompletely specified finite state machines. Comput Electr Eng, 33(1):58-69.

[10]Grzes TN, Solov’ev VV, 2015. Minimization of power consumption of finite state machines by splitting their internal states. J Comput Syst Sci Int, 54(3):367-374.

[11]Han XG, Chen ZQ, 2018. A matrix-based approach to verifying stability and synthesizing optimal stabilizing controllers for finite-state automata. J Franklin Inst, 355(17):8642-8663.

[12]Han XG, Chen ZQ, Liu ZX, et al., 2018. The detection and stabilisation of limit cycle for deterministic finite automata. Int J Contr, 91(4):874-886.

[13]He YS, Yu ZH, Jian L, et al., 2019. Fault correction of algorithm implementation for intelligentized robotic multipass welding process based on finite state machines. Robot Comput-Int Manuf, 59:28-35.

[14]Kamble SD, Thakur NV, Bajaj PR, 2018. Fractal coding based video compression using weighted finite automata. Int J Amb Comput Intell, 9(1):115-133.

[15]Klimowicz AS, Solov’ev VV, 2013. Minimization of incompletely specified Mealy finite-state machines by merging two internal states. J Comput Syst Sci Int, 52(3):400-409.

[16]Li YM, Pedrycz W, 2007. Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets Syst, 158(13):1423-1436.

[17]Liu DS, Huang ZP, Zhang YM, et al., 2016. Efficient deterministic finite automata minimization based on backward depth information. PLoS ONE, 11(11):e0165864.

[18]Lu JQ, Li HT, Liu Y, et al., 2017. Survey on semi-tensor product method with its applications in logical networks and other finite-valued systems. IET Contr Theory Appl, 11(13):2040-2047.

[19]Martinek P, 2018. Some notes to minimization of multiset finite automata. AIP Conf Proc, 1978(1):470019.

[20]Melnikov B, 2010. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundam Inform, 104(3):267-283.

[21]Perkowski MA, Jóźwiak L, Zhao W, 2001. Symbolic two-dimensional minimization of strongly unspecified finite state machines. J Syst Archit, 47(1):15-28.

[22]Solov’ev VV, 2010. Minimization of Moore finite automata by internal state gluing. J Commun Technol Electron, 55(5):584-592.

[23]Solov’ev VV, 2011. Minimization of Mealy finite state machines via internal state merging. J Commun Technol Electron, 56(2):207-213.

[24]Solov’ev VV, 2014. Complex minimization method for finite state machines implemented on programmable logic devices. J Comput Syst Sci Int, 53(2):186-194.

[25]Solov’ev VV, 2017. Minimization of Mealy finite-state machines by using the values of the output variables for state assignment. J Comput Syst Sci Int, 56(1):96-104.

[26]Voeten C, van Zaanen M, 2018. The influence of context on the learning of metrical stress systems using finite-state machines. Comput Ling, 44(2):329-348.

[27]Wang YB, Li YM, 2018. Minimization of lattice multiset finite automata. J Intell Fuzzy Syst, 35(1):627-637.

[28]Xu XR, Hong YG, 2012. Matrix expression and reachability analysis of finite automata. J Contr Theory Appl, 10(2):210-215.

[29]Yan YY, Chen ZQ, Liu ZX, 2015. Semi-tensor product approach to controllability and stabilizability of finite automata. J Syst Eng Electron, 26(1):134-141.

[30]Yan YY, Chen ZQ, Yue JM, et al., 2016. STP approach to model controlled automata with application to reachability analysis of DEDS. Asian J Contr, 18(6):2027-2036.

[31]Yan YY, Yue JM, Fu ZM, et al., 2019a. Algebraic criteria for finite automata understanding of regular language. Front Comput Sci, 13(5):1148-1150.

[32]Yan YY, Yue JM, Chen ZQ, et al., 2019b. Algebraic expression and construction of control sets of graphs using semi-tensor product of matrices. IEEE Access, 7:113440-113451.

[33]Yan YY, Yue JM, Chen ZQ, 2019c. Algebraic method of simplifying Boolean networks using semi-tensor product of matrices. Asian J Contr, 21(6):2569-2577.

[34]Yue JM, Yan YY, 2019. Exponentiation representation of Boolean matrices in the framework of semi-tensor product of matrices. IEEE Access, 7:153819-153828.

[35]Yue JM, Yan YY, Chen ZQ, et al., 2019a. Identification of predictors of Boolean networks from observed attractor states. Math Method Appl Sci, 42(11):3848-3864.

[36]Yue JM, Yan YY, Chen ZQ, 2019b. Language acceptability of finite automata based on theory of semi-tensor product of matrices. Asian J Contr, 21(6):2634-2643.

[37]Yue JM, Yan YY, Chen ZQ, 2020a. Matrix approach to simplification of finite state machines using semi-tensor product of matrices. Asian J Contr, 22(5):2061-2070.

[38]Yue JM, Yan YY, Chen ZQ, 2020b. Three matrix conditions for the reduction of finite automata based on the theory of semi-tensor product of matrices. Sci China Inform Sci, 63(2):129203.

[39]Zhang KZ, Zhang LJ, 2016. Observability of Boolean control networks: a unified approach based on finite automata. IEEE Trans Autom Contr, 61(9):2733-2738.

[40]Zhang QL, Feng JE, Yan YY, 2020. Finite-time pinning stabilization of Markovian jump Boolean networks. J Franklin Inst, 357(11):7020-7036.

[41]Zhang ZP, Chen ZQ, Han XG, et al., 2017. Static output feedback stabilization of deterministic finite automata. Proc 36^th Chinese Control Conf, p.2421-2425.

[42]Zhang ZP, Chen ZQ, Liu ZX, 2018a. Modeling and reachability of probabilistic finite automata based on semi-tensor product of matrices. Sci China Inform Sci, 61(12):129202.

[43]Zhang ZP, Chen ZQ, Han XG, et al., 2018b. On the static output feedback stabilization of deterministic finite automata based upon the approach of semi-tensor product of matrix. Kybernetika, 54(1):41-60.