Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition |
| |
Authors: | Yongyi YAN Zengqiang CHEN Zhongxin LIU |
| |
Affiliation: | 1. College of Computer and Control Engineering, Nankai University, Tianjin 300071, China,2. College of Science, Civil Aviation University of China, Tianjin 300300, China |
| |
Abstract: | This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata (DFA) and nondeterministic finite automata (NFA). |
| |
Keywords: | finite automata reachability analysis transition function expression matrix approach semi-tensor product |
|
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |
|