Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (15): 44-47.DOI: 10.3778/j.issn.1002-8331.1706-0122

Previous Articles     Next Articles

Cardinal of regular language of finite automata

CHI Xiaoqing, WANG Yuhan, WANG Yanhui   

  1. College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao, Shandong 266590, China
  • Online:2018-08-01 Published:2018-07-26

有限自动机可识别语言的基数

迟晓晴,王玉涵,王艳慧   

  1. 山东科技大学 数学与系统科学学院,山东 青岛 266590

Abstract: This paper studies the cardinal problem of regular language of finite automata by using adjacency matrix of directed graphs. By establishing a one-to-one correspondence relationship between the regular language of the finite automaton and its directed graph from the initial node(the initial state of the finite automaton) to the termination node(the end state of the finite automaton), using the adjacency matrix, the cardinality formula of the regular language of the finite automaton is given, and the sufficient conditions for the two automata to be unequal are studied.

Key words: finite automata, regular language, adjacency matrix

摘要: 利用有向图的邻接矩阵研究有限自动机的可识别语言的基数问题。通过建立有限自动机的可识别语言与其有向图中从初始结点(有限自动机的初始状态)到终止结点(有限自动机的终止状态)的路的一一对应关系,利用邻接矩阵给出了有限自动机的可识别语言的基数公式,研究了两个自动机不等价的充分条件。

关键词: 有限自动机, 可识别语言, 邻接矩阵