在形式语言和自动机理论[1]中,有限自动机和它接收的正则语言已经应用到各个方面,但是有限自动机只能接收正则语言的限制,使得有必要把传统的有限自动机进行推广,用半环[2]-[ 14]和形式幂级数[2][10]-[15]来研究有限自动机,使有限自动机的应用更加广泛,特别是在图像压缩,语音识别等方面。本文主要从以下几个方面进行了研究:1.介绍了代数理论的基础知识。首先,从半环的概念开始介绍了序列,半环中元素的星和准逆运算,半环中的恒等式。随后又引入了矩阵的定义,分块矩阵,并重点介绍了矩阵中的恒等式。最后又详细介绍了形式幂级数,并把半环,矩阵及相关的性质扩展到形式幂级数矩阵半环上,最后建立起形式幂级数矩阵半环中的矩阵与有限自动机的联系。2.介绍形式幂级数半环上的有限自动机。首先证明了布尔形式幂级数半环和语言半环的同构,在此基础上把语言半环上的有限自动机从两个个方面进行了推广后给出了形式幂级数半环上的有限自动机的定义和行为的定义。然后证明了A<Σ>-有限自动机所识别的幂级数集合组成有理封闭半环,随后又给出了有理幂级数和正则表达式的定义及一些结论。3.介绍了A<<Σ*>>-有限自动机在图像方面的一些应用,首先介绍了用字母表上的字符串表示数字图像的像素地址及图像的自动机表示,最后给出A<<Σ*>>-有限自动机近似表示多分辨率灰度图像及图像编码算法的主要思想,该方法的有效应用将使图像压缩的比例得以提高。
