文献类型：会议论文

英文题名：Matrix Conditions of Language Recognition for Finite State Machines Using the Theory of Semi-tensor Product of Matrices

作者：Yue, Jumei[1];Yan, Yongyi[2];Li, Zhiqiang[3];Jin, Xin[1];Gao, Song[1]

第一作者：Yue, Jumei

通讯作者：Yue, JM[1]

机构：[1]Henan Univ Sci & Technol, Coll Agr Engn, Luoyang 471000, Peoples R China;[2]Henan Univ Sci & Technol, Coll Informat Engn, Luoyang 471000, Peoples R China;[3]Henan Univ Econ & Law, Sch Math & Informat Sci, Zhengzhou 450046, Peoples R China

第一机构：Henan Univ Sci & Technol, Coll Agr Engn, Luoyang 471000, Peoples R China

通讯机构：[1]corresponding author), Henan Univ Sci & Technol, Coll Agr Engn, Luoyang 471000, Peoples R China.

会议论文集：38th Chinese Control Conference (CCC)

会议日期：JUL 27-30, 2019

会议地点：Guangzhou, PEOPLES R CHINA

语种：英文

外文关键词：Logical systems; semi-tensor product of matrices; STP; finite state machines; finite automata; matrix approach; finite-valued systems

摘要：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.