字的组合的半群方法  

Semigroup Method in Combinatorics on Words

作　　者：刘耀军[1] 徐宗本[2] 

机构地区：[1]太原师范学院数学系,太原030012 [2]西安交通大学理学院,西安710049

出　　处：《计算机学报》2005年第7期1138-1145,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(A10071068)资助.

摘　　要：该文利用半群方法给出了语言的一些代数性质.首先,讨论了稠密语言的半群结构,给出了包含语言w(wk)(其中w∈A+,k是正整数)的一个稠密语言类;证明了稠密正规语言包含一个字与一个稠密正规右酉幺半群的积.其次,讨论了自由幺半群的正规分支可分解性,证明了自由幺半群及正规分支可分解语言与正规分支可分解的后缀语言的积是正规分支可分解的;应用这些结果证明了Shyr和Yu关于正规语言的两个猜想.Semigroup method and Combinatorics method are two important techniques in the study of words and languages. This paper presents the semigroup method and explore languages by using semigroup method. Some algebraic properties of languages be given via semigroup method. Firstly, the semigroup constructions of dense languages are given. It's proved that every dense language which syntactic monoid has the zero, or which syntactic monoid has the minimal i-deal and this ideal is a periodic semigroup having a primitive idempotent contains a language w(WK)* for some nonempty word w and some positive integer k. The theorem every code is thin is generalized to the result that every code which syntactic monoid has the zero, or which syntactic monoid has the minimal ideal and this ideal is a periodic semigroup having a primitive idempotent is thin. It's proved that every dense regular language contains a product of some word with some dense regular right unitary submonoid of A*, and by using this result it is proved that every dense regular language also contains a primitive word. Secondly, the regular component decomposition of free monoids are given. It's proved that free monoids are regular component splittable and that every product of a regular component splittable language with a regular component split-table suffix language is regular component splittable. As applications of the above results two conjectures about regular languages given by Shyr and Yu, in 1998 are proved. The two conjectures are that regular languages are regular component splittable and dense regular languages contains imprimitive words.

关 键 词：形式语言 稠密语言 有限自动机 半群 码 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]