本原字的问题.doc

本原字的问题 本原字的问题摘要 本原字是代数语言学中1个基本且重要的概念.它主要应用是在可识别语言与有限自动机中，而关于对可识别语言与自动机1直是理论计算机科学研究中的重要分支.Shyr和Yu提出了关于正规语言的两个猜想：每个稠密正规语言含有非本原字；每个稠密正规语言中也含有本原字.目前，在计算机中有许多种语言，语言种类之多类似于代数系统之多.自由含幺半群是研究形式语言的基础.形式语言研究的主要对象是文法规则，根据不同的文法规则就可以产生不同的计算机语言.那么，在本原字的研究中也用到半群.本文首先通过半群在形式语言等方面的广泛应用，引进本原字的概念；其次，用数形结合的方法对本原字的性质进行讨论，给出本原字的判定方法；最后对于本原字和码之间的关系，本文略为涉及.关键词： 半群；自由幺半群；本原字；码The Problem of Primitive Word  ABSTRACT    Primitive word is a basic and important concept in the algebra languages. It is used in identify languages and finite automata, but they are important offsets in the research of theory computer. Shyr and Yu give two thoughts of formal language: every dense regular language contains imprimitive words, and also contains primitive words. There are many languaes in the computer at present, and the kind of languages are as many as algebraic systems. Free monoid is a basic of researching formal language. Primary object of studying formal language is grammar rule, and different grammar rule may give birth to different computer language. Of course, semigroup is also used in primitive word. First, semigroup has great application in formal language, that the concept of primitive word is introduced. Secondly, primitive word is talked about in character and used in diagram. And the method of judge and primitive word are presented. At last, it is touched upon the connection of primitive word and code.  Key words  semigroup; free monoid; primitive word; code