导　　师： 周晓聪

学科专业： H1202

授予学位： 硕士

作　　者： ;

机构地区： 中山大学

摘　　要： 共代数理论自从20世纪90年代以来，已经得到广泛的研究和应用，越来越引起计算机研究人员的关注，已经成为理论计算机科学的研究热点之一。目前，集合范畴上的共代数研究已经趋向成熟，共代数方法也在计算机科学中得到了初步的应用。 共代数主要是从“观察”的角度考察系统及其性质，对于研究基于状态的系统有独特的优越性，可以对系统的行为等价、不确定性等从数学上进行深入的探讨。目前，共代数理论已经逐步应用在自动机理论、面向对象程序的规范等领域。此外，共代数作为代数的对偶概念，使得共代数方法成为代数方法的一个互补的研究方法，将代数方法和共代数方法融合在一起，还可用于软件系统的规范描述和程序语言的设计。 本文首先对于共代数的理论基础范畴论作了一个初步的介绍，并对共代数的概念及其相关理论作了较为深入的探讨，特别地，在b.jocobs等人工作的基础上，进一步讨论并总结了自动机共代数的主要内容，并结合一些具体的实例进行了较为详细的阐述。为考察共代数理论与语言及其自动机之间的关系，本文运用共代数理论特别是共归纳原理证明正则表达式的主要性质，并与传统方法进行了比较。最后，作为共代数理论的一个具体应用，本文考察从正则表达式到确定型有穷自动机的转换，给出了转换的算法和具体实例，通过与传统方法进行比较，可以看出共代数理论有其独特的优势，是研究确定型有穷自动机理论的一种新的思路。

关 键 词： 范畴论 共代数 自动机 正则表达式

领　　域： [自动化与计算机技术] [自动化与计算机技术]