正则语言的一个特征

摘要：

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

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

所属期刊栏目：48

分类号：TP301.1(计算技术、计算机技术)

在线出版日期：2012-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：43-44