Matrix Conditions of Language Recognition for Finite State Machines Using the Theory of Semi-tensor Product of Matrices
Jumei Yue, Yongyi Yan, Zhiqiang Li, Xin Jin, Song Gao · 2019
Using the theories of many-valued logic and semi-tensor product of matrices (STP), this paper investigates how to mathematically determine whether or not a regular language is recognized by a finite automaton. To this end, the behavior of finite automata is first formulated as bilinear dynamic equations, which provide a uniform model for deterministic and non-deterministic finite automata. Based on the bilinear model, the recognition capacity of finite automata understanding of regular languages is investigated and serval algebraic criteria are obtained. With the algebraic criteria, to judge whether a regular sentence is accepted by a finite automaton or not, one only need to calculate an STP of some vectors, rather than making the sentence run over the machine as traditional manners. Further, the inverse problem of recognition is considered, an algorithm is developed that can mathematically construct all the accepted sentences for a given finite automaton. The algebraic approach of this paper may be a new angle and means to understand and analyze the dynamics of finite automata.