字的组合的半群方法.pdfVIP

第 28 卷 　第 7 期 计 　　算 　　机 　　学 　　报 Vol . 28 No . 7 2005 年 7 月 C H IN ESE J OU RN AL O F COM PU T ER S J uly 2005 　 字的组合的半群方法 1) 2) 刘耀军 　　徐宗本 1) (太原师范学院数学系 　太原 　0300 12) 2) ( 西安交通大学理学院　西安 　7 10049) 摘 　要 　该文利用半群方法给出了语言的一些代数性质. 首先 ,讨论了稠密语言的半群结构 ,给出了包含语言 ( k) ( + ) w w 其中 w ∈A , k 是正整数 的一个稠密语言类 ;证明了稠密正规语言包含一个字与一个稠密正规右酉幺半 群的积. 其次 ,讨论了自由幺半群的正规分支可分解性 ,证明了自由幺半群及正规分支可分解语言与正规分支可分 解的后缀语言的积是正规分支可分解的;应用这些结果证明了 Shyr 和 Yu 关于正规语言的两个猜想. 关键词 　形式语言 ;稠密语言 ;有限自动机 ;半群 ;码 中图法分类号 TP30 1 Semigroup Method in Combinatorics on Words 1) 2) L IU YaoJ un 　XU Zo ngBen ) 1 ( D ep art ment of M at hem at ics , Taiy uan Teachers ’Col leg e , Taiy uan 　0300 12) ) 2 ( Facul ty of S cience , X i ′an J i aotong Uni vers ity , X i ′an 　7 10049) Abstract 　 Semigroup met ho d and Co mbinatoric s met ho d are t wo import ant t echnique s in t he st udy of wor ds and lan guage s. Thi s p ap er p re sent s t he semigroup met ho d and exp lore language s by u sing semigroup met ho d .