Cardinal of regular language of finite automata

doi:10.3778/j.issn.1002-8331.1706-0122

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

College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao, Shandong 266590, China

Online:2018-08-01 Published:2018-07-26

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

迟晓晴，王玉涵，王艳慧

山东科技大学数学与系统科学学院，山东青岛 266590

Abstract

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

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

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

CHI Xiaoqing, WANG Yuhan, WANG Yanhui. Cardinal of regular language of finite automata[J]. Computer Engineering and Applications, 2018, 54(15): 44-47.

迟晓晴，王玉涵，王艳慧. 有限自动机可识别语言的基数[J]. 计算机工程与应用, 2018, 54(15): 44-47.

[1]	FU Zhe1，2, LI Jun2. Survey on high performance regular expression matching algorithms [J]. Computer Engineering and Applications, 2018, 54(20): 1-13.
[2]	MO Liping, ZHOU Kaiqing. Development method of square-Hmong-characters font library for supporting component reuse [J]. Computer Engineering and Applications, 2018, 54(12): 46-50.
[3]	BAI Yu, YAN Kun, LI Shaopeng, ZHANG Huawei, LIU Yi. Spectrum sensing for OFDM signals based on Graph [J]. Computer Engineering and Applications, 2018, 54(11): 86-90.
[4]	GAO Nan1，2, LI Meili2, SHE Yanhong2. H-Estrada indices of mixed graphs [J]. Computer Engineering and Applications, 2017, 53(2): 12-14.
[5]	TIAN Qidong1, LIU Shungui1, JIANG Hui2, PENG Jianchun2. Grid vulnerability evaluation by fusing grid topology and security and stability [J]. Computer Engineering and Applications, 2016, 52(6): 223-226.
[6]	XIANG Jin, LI Cuihong, WEI Deyi, YANG Jiahong. Fast reconstruction for compressive sensing image using adjacency matrix of bipartite graph [J]. Computer Engineering and Applications, 2013, 49(1): 191-194.
[7]	HAN Guanghui. Characteristic of regular languages [J]. Computer Engineering and Applications, 2012, 48(4): 43-44.
[8]	RUAN Qunsheng1, LIN Hongkang1，2. Algorithm searching urban path route [J]. Computer Engineering and Applications, 2012, 48(34): 237-240.
[9]	WEI Dezhi, HONG Lianxi, LIN Lina, WU Xu. Improved XFA for deep packet inspection [J]. Computer Engineering and Applications, 2012, 48(34): 245-248.
[10]	PENG Jiayin. Automata and grammars theory based on Unsharp quantum logic [J]. Computer Engineering and Applications, 2012, 48(28): 57-60.
[11]	WANG Yan, LI Lingling, SHAO Xiaoyan. Research on advanced frequent itemsets mining algorithm [J]. Computer Engineering and Applications, 2012, 48(19): 119-121.
[12]	FAN Shuyi, MENG Chen, WANG Cheng. New minimized algorithm of DFA states [J]. Computer Engineering and Applications, 2012, 48(1): 47-48.
[13]	LI Qingsheng1，YANG Yuxing1，2，WANG Aimin1，3. Recognition of inscriptions on bones or tortoise shells based on graph isomorphism [J]. Computer Engineering and Applications, 2011, 47(8): 112-114.
[14]	HUANG Feidan1，CAO Fasheng1，2. Equivalence of cyclic automata [J]. Computer Engineering and Applications, 2011, 47(7): 34-35.
[15]	LIU Yingdong1，LENG Mingwei2，CHEN Xiaoyun3. Construction algorithm of FP-tree based on adjacency matrix [J]. Computer Engineering and Applications, 2011, 47(7): 153-155.

Cardinal of regular language of finite automata

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics