正则语言的一个特征

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (4): 43-44.

正则语言的一个特征

韩光辉

武汉商业服务学院信息工程系，武汉 430056

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-01 发布日期:2012-04-05

Characteristic of regular languages

HAN Guanghui

Department of Information Engineering, Wuhan Commercial Service College, Wuhan 430056, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-01 Published:2012-04-05

摘要/Abstract

摘要： Myhill-Nerode定理利用等价关系描述了正则语言的一个重要特征，它是有限自动机理论中的一个经典、优美的结果。为了将Myhill-Nerode定理推广到更一般的情形，引入了有限自动机M上的状态转移半群和Σ*上的M-半群，讨论了其若干性质。在此基础上，将Myhill-Nerode定理中的等价关系一般化，给出了正则语言的一个新的特征定理，Myhill-Nerode定理成为该定理的一个推论。讨论了正则语言的最一般的特征，提出了有待进一步研究的问题。

关键词: 正则语言, 有限自动机, 等价关系, 状态转移半群, M-半群

Abstract: Myhill-Nerode theorem describes an important characteristic of regular languages, it is a classical and elegant result in finite automata theory. In order to extend Myhill-Nerode theorem, states transition semigroup on a finite automaton M and M-semigroup on Σ* are introduced, their some properties are discussed. The equivalence relation in Myhill-Nerode theorem is generalized, a new characteristic of regular languages is given based on the states transition semigroup and the M-semigroup, then Myhill-Nerode theorem becomes its corollary. The most general characteristic of regular languages is discussed and the future work is presented.

Key words: regular language, finite automata, equivalence relation, states transition semigroup, M-semigroup

韩光辉. 正则语言的一个特征[J]. 计算机工程与应用, 2012, 48(4): 43-44.

HAN Guanghui. Characteristic of regular languages[J]. Computer Engineering and Applications, 2012, 48(4): 43-44.

[1]	迟晓晴，王玉涵，王艳慧. 有限自动机可识别语言的基数[J]. 计算机工程与应用, 2018, 54(15): 44-47.
[2]	赵焕焕1，菅利荣1，刘勇2. 基于集对顺势相似关系的变精度粗糙集模型[J]. 计算机工程与应用, 2017, 53(6): 51-56.
[3]	董泽民1，石强2. 基于归一化模糊联合互信息最大的特征选择[J]. 计算机工程与应用, 2017, 53(22): 105-110.
[4]	张辰，李红军，罗柳红，何英豪. 等价关系矩阵的置换合同性质与标准形计算[J]. 计算机工程与应用, 2017, 53(13): 42-48.
[5]	李俊余1，2，王霞1，2. 对象定向概念格的决策约简[J]. 计算机工程与应用, 2016, 52(18): 154-157.
[6]	邱婷婷，李克典. 不协调目标随机信息系统中基于对象的μ-约简[J]. 计算机工程与应用, 2016, 52(10): 75-79.
[7]	秦华妮. 直觉模糊集的商空间[J]. 计算机工程与应用, 2015, 51(2): 21-25.
[8]	安秋生1，孔祥玉2，苏钦1. 粗糙关系数据库的数学基础[J]. 计算机工程与应用, 2015, 51(14): 108-112.
[9]	苏艳琴1，张光轶2，徐廷学3. 一种融合RST与模糊聚类的故障诊断方法[J]. 计算机工程与应用, 2013, 49(17): 6-8.
[10]	曹月芹. 基于模糊知识粒度的混合属性约简算法[J]. 计算机工程与应用, 2013, 49(17): 108-111.
[11]	花秀娟1，辛小龙1，朱熙2. 模糊商子格[J]. 计算机工程与应用, 2012, 48(8): 35-36.
[12]	魏德志，洪联系，林丽娜，吴旭. 一种改进的XFA在深度包检测中的应用[J]. 计算机工程与应用, 2012, 48(34): 245-248.
[13]	彭家寅. 基于Unsharp量子逻辑的自动机和文法理论[J]. 计算机工程与应用, 2012, 48(28): 57-60.
[14]	雷国平，谭泽富. 有限自动机在CMMB解复用中的应用研究[J]. 计算机工程与应用, 2012, 48(17): 154-160.
[15]	黄飞丹1，曹发生1，2. 循环自动机的等价性[J]. 计算机工程与应用, 2011, 47(7): 34-35.