文档介绍：太原科技大学硕士学位论文下推自动机的半环方法姓名:麻勇军申请学位级别:硕士专业:计算机软件与理论指导教师:刘耀军 20090701 下推自动机的半环方法中文摘要当今自动机理论及其相关的形式语言的理论得到了高度的发展,由其衍生出的知识也层出不穷。但经典自动机和语言理论也存在某方面的不足,特别是一些证明从数学的角度看仍不够完美,一个典型的例子就是在自动机的理论中,自动机状态转换的描述,仅仅是定义了状态转换,从数学运算的角度看还不够严密。本文在下推自动机概念的基础上给出了其在半环上的定义,下推转换矩阵的引入,使下推自动机的行为和半环代数理论上的等式建立了联系。从而使下推自动的讨论更加简洁。首先,介绍了课题研究的对象下推自动机的概念、下推自动机的及时描述、下推自动机所接受的语言等相关概念与半环、半模、收敛等概念。并重点讨论了偏序半环和关于偏序半环上等式的一些性质。最后说明了课题实现的具体目标和意义。接着,引入了与语言理论密切相关的形式幂级数的概念,并将半环的概念转换到形式幂级数,同时在引入矩阵概念的基础上也将半环的概念转移到矩阵,重点证明了布尔形式幂级数矩阵半环和形式幂级数布尔矩阵半环的子半环同构,进一步结合形式幂级数布尔矩阵半环和分块矩阵的相关理论给出了:与矩阵星运算求解相关的线性系统,并证明了线性系统与矩阵星运算相关的一些定理。最后,提出了语言半环的概念,证明了它和布尔形式幂级数半环是同构的。在语言半环到语言矩阵半环扩展的基础上定义了下推转移矩阵,进而定义了下推自动机和下推自动机行为。特别是下推转换矩阵的引入,通过一系列矩阵半环同构将下推自动机行为的研究转移到布尔形式幂级数矩阵半环上,最终使下推自动机的计算转变为矩阵半环上下推转换矩阵的乘法和加法运算。关键词:半环;线性代数;下推自动机;形式语言 The SemiringsMethod forPushdown Automata Graduate Name:Yongj unMa Maj puter software andtheory Directed by:Yaojun Liu ABSTRACT Automata theory and theclosely relatedtheory offormal languages form nowadays such highly developed and diversified body ofknowledge. Customary expositions of automata and language theory are often unsatisfactory inthe sense thatentirely different adhoc proofs are given in very similarsituations;moreover,many ofproofs stillremain inadequate fromthemathematical point typicalexample ofthelatter stateof affairsisthat one defines acertain construction and then simply claims without proof that the construction works as pushdown automata are introduced by using themethod ofsemirings and thetools from linearalgebra,That bulidtheconnection between semirings algebraic systems of equations and the makes the discussion of pushdown automata more simply. First gives an introduction to research objects which inculding pushdown automata and semirings andprovides abackground and amotive for our study. Then discusses the concept offormal power series,and convert the concept ofsemirings toformal power transfers semirings into matrix inthe foundation foftheconcept ofma