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

Cardinal of regular language of finite automata

作　　者：迟晓晴 王玉涵 王艳慧 CHI Xiaoqing;WANG Yuhan;WANG Yanhui(College of Mathematics and Systems Science,Shandong University of Science and Technology,Qingdao,Shandong 266590,China)

机构地区：[1]山东科技大学数学与系统科学学院,山东青岛266590

出　　处：《计算机工程与应用》2018年第15期44-47,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11501331;No.11471255);山东省自然科学基金(No.BS2015SF002);山东科技大学优秀教学团队建设计划(No.JXTD20160507)

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

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]