Matrix expression and reachability analysis of finite automata  

作　　者：Xiangru XU, Yiguang HONG Key Laboratory of Systems and Control, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China 

出　　处：《控制理论与应用（英文版）》2012年第2期210-215,共6页

基　　金：supported by the National Natural Science Foundation of China (No. 61174071)

摘　　要：In this paper, we propose a matrix-based approach for finite automata and then study the reachability conditions. Both the deterministic and nondeterministic automata are expressed in matrix forms, and the necessary and sufficient conditions on reachability are given using semitensor product of matrices. Our results show that the matrix expression provides an effective computational way for the reachability analysis of finite automata.In this paper, we propose a matrix-based approach for finite automata and then study the reachability conditions. Both the deterministic and nondeterministic automata are expressed in matrix forms, and the necessary and sufficient conditions on reachability are given using semitensor product of matrices. Our results show that the matrix expression provides an effective computational way for the reachability analysis of finite automata.

关 键 词：Finite automata REACHABILITY Matrix expression Semitensor product 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构] O231[自动化与计算机技术—计算机科学与技术]