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

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

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