（计算机软件与理论专业论文）语言半环上的有限自动机的推广.pdf

中文摘要 在形式语言和自动机理论n 1 中，有限自动机和它接收的f 则语言已经应用到各个方 面，但是有限自动机只能接收正则语言的限制，使得有必要把传统的有限自动机进行推 广，用半环小4 1 和形式幂级数嘲n 0 h 。5 3 来研究有限自动机，使有限自动机的应用更加广 泛，特别是在图像压缩，语音识别等方面。 本文主要从以下几个方面进行了研究： 1 介绍了代数理论的基础知识。首先，从半环的概念开始介绍了序列，半环中元素 的星和准逆运算，半环中的恒等式。随后又引入了矩阵的定义，分块矩阵，并重点介绍 了矩阵中的恒等式。最后又详细介绍了形式幂级数，并把半坏，矩阵及相关的性质扩展 到形式幂级数矩阵半环上，最后建立起形式幂级数矩阵半环中的矩阵与有限自动机的联 系。 2 介绍形式幂级数半环上的有限自动机。首先证明了布尔形式幂级数半环和语言半 环的同构，在此基础上把语言半环上的有限自动机从两个个方面进行了推广后给出了形 式幂级数半环上的有限自动机的定义和行为的定义。然后迂明t a 有限自动机所识 别的幂级数集合组成有理封闭半环，随后又给出了有理幂级数和f 则表达式的定义及一 些结论。 3 介绍了彳 有限自动机在图像方面的一些应用，首先介绍了用字母表上的 字符串表示数字图像的像素地址及图像的自动机表示，最后给出彳 一有限自动机近 似表示多分辨率灰度图像及图像编码算法的主要思想，该方法的有效应用将使图像压缩 的比例得以提高。 关键词：有限自动机；彳 有限自动机；有理幂级数；图像压缩 a b s t r a c t t h ef i n i t ea u t o m a t aa n dt h er e g u l a rl a n g u a g e sa r ev e r yu s e f u l 【l 】b u tt h e f i n i t ea u t o m a t ac a no n l yr e c e i v et h er e g u l a rl a n g u a g e s oi ti sn e c e s s a r yt o g e n e r a l i z e t h et r a d i t i o n a lf i n i t ea u t o m a t at o 彳 一f i n i t ea u t o m a t a t h e m e t h o do fs e m i r i n g s 2 1 。【1 4 1 a n df o r m a l p o w e rs e r i e s 【2 】【1 o 】- 【15 】m a k e s f i n i t e a u t o m a t at ob eu s e dm o r ew i d e l y ，e s p e c i a l l yi ni m a g ec o m p r e s s i o na n ds p e e c h r e c o g n i t i o n i nt h i sa r t i c l ew ed i s c u s st h ef o l l o w i n gt h r e ep r o b l e m s f i r s t l y ，t h ef u n d a m e n t a lk n o w l e d g eo fl i n e a ra l g e b r ai s i n t r o d u c e d w e b e g i nw i t ht h ec o n c e p to fs e m i r i n g ，t h es e q u e n c e ，s t a ra n dq u a s i - i n v e r s eo f s e m i r i n ga n ds e m i r i n g i d e n t i t i e s t h e nt h ed e f i n i t i o no ft h em a t r i x ，b l o c k m a t r i xa n dt h em a t r i xi d e n t i t i e sa r ei n t r o d u c e d f u r t h e r m o r et h ef o r m a lp o w e r s e r i e sa r ed i s c u s s e d d e t a i l e d l y a n dt h e p r o p e r t i e s o ft h e s e m i r i n g a r e g e n e r a l i z e dt om a t r i xs e m i r i n go v e rt h es e m i r i n go ff o r m a lp o w e rs e r i e s f i n a l l y t h er e l a t i o n sb e t w e e nm a t r i xs e m i r i n go v e rt h ef o r m a lp o w e r ss e r i e sa n df i n i t e a u t o m a t aa r ee s t a b l i s h e d s e c o n d l y ，t h ef i n i t e a u t o m a t ao v e rf o r m a lp o w e rs e r i e ss e m i r i n ga r e i n t r o d u c e d f i r s to fa l lt h ei s o m o r p h i s mo ft h eb o o l e a ns e m i r i n ga n dl a n g u a g e s e m i - r i n gi sp r o v e d b a s eo nt h el a n g u a g e so fs e m i - r i n g ，t h ef i n i t ea u t o m a t ai s g e n e r a l i z e di nt w oa s p e c t s ：t h ef o r m a ld e f i n i t i o n so f 彳 - f i n i t ea u t o m a t a a n dt h eb e h a v i o ro f 彳 一f i n i t ea u t o m a t a l a s tt h ep o w e rs e r i e ss e t i d e n t i f i e db y 么 - f i n i t ea u t o m a t ac o n s i s t sar a t i o n a l l yc l o s e ds e m i r i n gi s p r o v e d t h i r d l y ，s o m ea p p l i c a t i o n sa b o u t t h e 么 一f i n i t ea u t o m a t ai nt h ei m a g e a r e aa r ed i s c u s s e d t os t a r tw i t h ，ii n t r o d u c eh o wt od e n o t ep i x e la d d r e s so f d i g i t a li m a g ew i t ht h ew o r do ft h ea l p h a b e t 0 ，1 ，2 ，3 ) t h e nt h ea u t o m a t o n r e p r e s e n t a t i o no ft h ei m a g ei sd i s c u s s e d f i n a l l yt h em e t h o do fa p p r o x i m a t i o n f o rm u l t i r e s o l u t i o ng r a yl e v e li m a g eu s i n g 彳 一f i n i t ea u t o m a t aa n dt h e m a i ni d e ao fe n c o d i n ga l g o r i t h mf o rg r a yl e v e li m a g ei sg i v e n k e yw o r d s ：f i n i t ea u t o m a t a ；a 一f i n i t ea u t o m a t a ；r a t i o n a lp o w e rs e r i e s ； i m a g ec o m p r e s s i o n i v 目录 第一章引言l 1 1 课题研究的背景l 1 2 课题研究目的和意义2 1 3 目前国内外研究现状3 1 4 本文的研究内容和安排3 第二章代数理论5 2 1 半坏理论5 2 1 1 幺半群5 2 1 2 半环的定义5 2 1 3 序列6 2 1 4 半环中的恒等式7 2 2 形式幂级数8 2 3 矩阵1 0 2 3 1 矩阵的定义1 0 2 3 2 半环a 扩展到矩阵半环a 麒1 1 2 3 3 矩阵半环中的收敛l2 2 3 4 分块矩阵1 2 2 3 5 半环a 的等式及定理扩展到矩阵半环a 腻1 1 4 2 4 同态和表示1 8 第三章彳 一有限自动机和有理幂级数1 9 3 1 预备知识1 9 3 1 1 语言半环1 9 3 2 彳 有限自动机2 l 3 2 1 么 一有限自动机的形式定义2 l 3 2 2 么 有限自动机的行为的形式定义2 1 3 3 有理幂级数2 9 第四章彳 有限自动机的应用3 3 4 1 图像划分和像素地址表示方法3 3 4 2 数字图像的自动机表示3 4 4 3 用彳 有限自动机表示多分辨率狄度图像3 5 。 v 第五章总结和展望4l 参考文献4 3 致 射47 攻读学位期间发表的学术论文4 9 v i 理沦【1 6 1 是研究离散数字系统的功 能，结构及两者关系的数学理论。随着微电子及信息等科学技术的迅猛发展，自动机理 论非常丰富并且有着广泛的应用领域，例如电路原理、模式识别与匹配、语音识别、手 写体识别、密码算法、数据压缩、图像压缩与图像处理等。自动机理论已逐步向不同领 域渗透，成为了许多学科的重要理论和应用基础。 许多国内外学者用许多方法来研究自动机，有状态转换函数、 r t l 、v h d l 1 7 】 以及矩阵形式等方法。采用状态转换函数能反映自动机关系结构，但要描述自动机的转 换过程需要依靠状态转换图。而且当关系很复杂时，要获得状态转换图是比较麻烦的。 r t l 和v h d l 方法是采用语言描述，它们主要是讨论自动机的实现。从代数结构方面 研究自动机推动了自动机理论发展，为了有利于利用计算机完成自动机状态转换推演过 程，需要用一种数学推理描述自动机态转换过程，并可以很好地在理论上讨论自动机内 在结构。对于状态转换图可以借助图论进行讨论，在5 0 年代，s s e s h u 等【l7 j 就利用 矩阵工具研究有限自动机，8 0 年代主要以时序线路测试为目的，从线路的具体结构函数 出发，建立了时序机的矩阵模型，矩阵形式与其它方法相比能很好地完成对自动机状态 转化过程的演算，然而它更重要的价值在于启发我们将其推广到一般有限自动机，对有 限自动机的理论研究产生重要影响。 随着现代科学技术的发展，有限自动机己成为许多学科的重要的理论和应用基础。 有限自动机理论是自动机理论的一个重要分支，它是神经网络、保密学、控制理沦等众 多学科领域的重要研究工具。探索有限自动机理论研究的新思路和它的广泛应用都具有 非常重要的学术意义和现实意义。掌握了有限自动机的基本概念，将为后面学习其他更 复杂的自动机打下良好的基础。 在客观世界中，具有有穷多个状态的系统比比皆是。例如，日常用的指针式钟表就 是一种有穷状态系统，它共有1 2x6 0 6 0 个状态，秒针每走一步，系统就从一种 状态转移到另一种状态。一局棋也是一种有穷状态系统，棋手每走一步，就从一种状态 转移到另一种状念。在： 业产品中，也有很多类似的例子。比如，电梯的控制结构就是 有穷状态系统的一个典型例了。电梯停在每一楼层作为一个状态，它的控制系统不必记 住以前的所有动作，而只要知道现在的位置以及用户给出的信号就可以通过改变它的状 态( 上或f ) 来满足用户的要求。某些电子产品中的丌关电路，是有穷状态系统的又一 实际例子。一个丌关电路由有穷多个门电路组成，每个“门”可以处于两种状态一一丌 l 语言、l ，_ 环上的有限自动机的推广 和关( 通常记为l 和0 ) 之一。具有 个门的开关网络可以根据输入的信号可以从一 种状态变为另一种状态。 随着计算机技术的广泛应用，在现实生活中，用计算机来进行控制、协调完成一系 列的功能过程非常普遍。从这些具体的应用中我们可以抽象出许多有限状态系统的模 型。这类可以抽象为有限自动机的系统具有一些相同或相似的特点，即： ( 1 ) 系统能够处于某个相对稳定的状态下； ( 2 ) 状态数量有限； ( 3 ) 某个事件( 输入) 发生； ( 4 ) 这个事件触发一个或一系列的处理过程，包括执行特定的功能，产生相应的输出 等； ( 5 ) 处理结束，状态转移到一个新的相对稳定的状态。 确定的有限自动机d f a 1 是一个五元组m = 他z 西q o , f ) 。其中q 是有限的状态 集合；t 是有限的输入字母表；6 是转换函数，是从qxt 到q 的映射；q o 是初始 状态，q o q ；f 是终止状态集合f q 。转换函数6 是用来表示状态的转换关系 的。对状态g ，p q ，字符a t ，当在状念9 ，读入( 或输人) 字符a 后，状态转 换成p ，用转换函数表示，则可写成占向，矽= p 。 另由转换函数6 的定义可知，它是从qx 丁到q 的映射，其第一个自变量是一 个状态，第二个自变量是一个字符，它的值便是转换的后继状态。当有限自动机m 读 一个字符串时，它从初始状态和开始，经过一系列状态转换。最后如果能到达终止状 态，则这一字符串可被有限自动机接受，否则，则该字符串不被接受。为描述有限自动 机的工作过程，对于它在某一时刻的工作状况，可以用两个信息表明：一是在该时刻有 限自动机所处的状态g 称为当前状态；一是在该时刻等待输入的字符串w 。这两者构 成一个瞬时描述，称为格局，用向，训表示。 从上面的定义可以看出传统的有限自动机和语言理论【1 8 】- 【2 5 1 常常存在某些方面的 不足，许多证明从数学的角度看不够完美和简练，一个典型的例子就是在自动机的经典 理论中，自动机状态转换的描述，仅仅是定义了状态转换，而没有与数学之间建立足够 的联系。为了促进有限自动机研究的发展，国内外许多学者把有限自动机和代数理论联 系起来，这样更有利于用数学思想和数学方法研究自动机，使自动机的讨论更加简洁。 文【2 6 】中给出了上的有限自动机的半环表示( 语言半环上的有限自动机即经典的有限 自动机) ，从而使有限自动机的行为和矩阵半坏代数理论上的线性系统建立了联系。并 用此方法给出了f 则语言性质的证明，从数学的观点来看形式语言性质的证明更加简 第一章引言 洁，更加令人信服。 1 2 课题研究的目的和意义 有限自动机足识别正则语。a 。的模型。对于有限自动机和f 则语言的研究可追溯到 2 0 世纪4 0 年代初，那时m c c u l l o c h 和p i t t s 把有限状态机器用做神经网络模型，此后 正则语言开始被广泛的研究。有限自动机和它所识别的正则语言有着非常广泛的应用， 而且应用得也非常成功。其中，正则表达式和作为语言识别器的有限自动机主要应用在 编译，文本编辑和文本搜索等同语言，字符串相关的领域。但有限自动机识别语言的能 力限制在正则语言，而在数据处理，尤其在语音识别 2 7 1 一【3 0 】，图像压缩 3 1 1 一【3 4 1 等方面需 要更一般的模型，需要在边上赋予一定的权值( 消耗) 。彳 有限自动机对自动机 中的每条转移规则赋予一定的权值，这样就可以计算自动机中每条路径的权值，从而可 以进一步计算出每个输入字符串的权值，其研究既具有非常重要的理论意义，也有着非 常明显的实用价值。语言半环上的有限自动机( 有限自动机) 只是彳 上的有限 自动机刚3 5 卜1 3 8 1 的一种特殊情况，因此水 上的有限自动机比有穷状态自动机功能 更为强大，具有更强的语言生成能力。同时根据半环结构的不同使得水 上的 有限自动机具有更广泛的应用领域。根据权值耿值半环结构的不同，彳 上的有限 自动机有各种不同的模型。这些不同的模型有着各自不同的特性，使得彳 上的 有限自动机的应用更为灵活与广泛。这些不同模型有不同的工程应用背景，有的用于图 像处理与压缩，有的用于自然语言处理及语音识别。 本文在文献【2 6 】的基础上把有限自动机进行了推广，把上的有限自动机推广到 彳 上的有限自动机，上的有限自动机就是经典有限自动机( 即有限自动机) ， 它接收的是形式语言，而么 有限自动机接收的是形式幂级数，形式幂级数其实 就是形式语言的扩展，这样把有限自动机的经典理论推广到形式幂级数上，这样也产生 了研究自动机理论的统一的方法。 1 3 目前国内外研究现状 当前国外的一些专著中，语言和自动机理论使用数学方法取得了很多的成果，半环 代数理论是较为活跃的代数学研究领域之一，他们已经成功的把半环和有限自动机结合 起来进行研究，并且把经典的有限自动机推广到水 有限自动机，把形式语言推 广到形式幂级数，c u l i k l 3 9 1 在数字图像与压缩， k a n t u n e n 【3 9 】，m o h r i l 3 9 1 等在自然语言处 理及语音识别等领域墩得了很多的成功，使得自动机理沦的研究更加广泛，也更加实用。 国内近年对于自动机理论和半坏的研究也取得了较多成果，同时对自动机的研究也有较 语言? l ，环上的有限白动机的推广 多的研究成果发表，像有限自动机的矩阵模型表示等也把自动机的研究和数学思想结合 起来，但是将半环与自动机两者进行结合的研究与国外存在很大差距，尤其是把形式幂 级数，半环和有限自动机结合起来的研究更是比较少见。本文f 是在国外的许多研究成 果的基础上把他们三者结合起来进行研究。 1 4 本文的研究内容和安排 本文主要是在前人研究的基础上进一步把半环，形式幂级数和有限自动机结合起来 进行研究。主要内容如下： 第一章引言主要介绍了自动机理论的发展及研究方法引出了有限自动机理论，最后 介绍了本课题的研究背景和国内外研究现状。 第二章介绍代数理论。 第三章首先介绍语言半环的概念以及和形式幂级数半环之间的关系，然后给出 尔 有限自动机的形式定义和水 有限自动机行为的定义以及有关有理幂级 数的定理。 第四章水 有限自动机的应用【4 0 】一【4 5 1 。 第五章总结和展望。 4 一个恒等元素l 组成，使得对于任意的a m ，都有j a = a = a 。如果对于任意 碍b e m 都有c i b = b a ，那么称幺半群m 为交换幺半群。二元运算符号可以经常 被省略，即经常把a b 记为动，通常把幺半群中的二元运算叫做求积。 如果在问题讨论中，幺半群的二元运算和恒等元是明显的，则把幺半群记为m ，否 则把幺半群记为 。在形式语言与自动机理论的讨论中，最重要的一类幺半群 是由一个非空的可数集生成的自由幺半群半。其中，c 是所有形如： x i x 2 “x n ，x i e z 的有限字符串( 也称为字) 组成的集合，把字w 2 接在字w ，之后所形成的字称作两个串 w ，w ? 的积w ，w 2 。不含任何字母的字称作空字，记为s 。空字是乖的恒等元。 设为字母表，术是由生成的自由幺半群，称拳的子集为上的语言。 把字w 中出现的字母表中字母的个数( 重复出现的以出现的次数计算) 称为字w 的长度，记为l w l 。由定义可见，空字的长度为o ，即l si = o 。 2 1 2 半环 半环是带有两个二元运算+ 、和两个特殊元素0 、l 的集合，并且满足 ( 1 ) 是交换幺半群； ( 2 ) 是幺半群； ( 3 ) 分配律：对a 中任意元素珥勿c 都有 a ( b + c ) = a b + a c ，( a + b ) c = a c + b c ； ( 4 ) 对a 中任意元素a 都有0 a = a 0 = 0 。 如果对于任意谚b a ，都有a b = b a ，则称半环a 为交换半坏。 如果该半环中的运算和常值元素都是明显的则将此半环简记为a ，否则，将半环记 为 。 在语言理论中，最重要的半环是b o o l e a n 半环b = 0 ，1 ) ，其运算为1 + 1 = 1 1 = 1 ， 其运算表为： 语言、t - 环上的有限自动机的推广 0l o0o l01 表2 1b o o l e a n 半环的运算表示 t a b l e 2 im a t h e m a t i c a lo p e r a t i o nr e p r e s e n t a t i o no fb o o l e a ns e m i r i n g 由表格可见，0 是加法的恒等元，1 是乘法的恒等元。设儡历c 是b 中的任意三个 元素。 由0 是加法恒等元知如果q ，6 ，c - - 个之中有一个为0 ，则自然a + p + = a + p + 矽， 当b 髓c 都为1 时，因为1 + 1 = 1 ，所以也有a + p + 砂= 口+ p + 砂，因此， 是 幺半群，又因为运算表关于主对角线对称，所以+ 适合交换律，因此， 是交 换幺半群。 由1 是乘法恒等元知如果仍6 ，c 三个之中有一个为1 ，则自然有a p 砂= a p 矽，当珥抚c 都为o m t ，因为0 0 = 0 ，所以也有a p 砂= a p 砂，因 此， 是幺半群，又因为运算表关于主对角线对称，所以适合交换律，因此， 是交换幺半群。 由o 是乘法零元知，当口= d 时，a p + 砂= a b + o c = d ；因为1 是乘法恒 等元，所以当a = 时，a p + 砂= 口b + a c = b + c 。因此乘法适合分配律。 综上所述， 是交换半环。 半环的例子。 。 ， 2 1 3 序列 把映射aj 专脓为a m 的序列。把a 中所有序列组成的集合记为。如果口， 则记口= ( 口( n ) ) 零序列o ：对于所有n 0 ，都有d 例= o 单位序列刁：对于所有胛0 ，都有刁例= 1 设a ，c ea 。序列c 口定义为：对于所有门0 ，都有( c a ) ( n ) = c ( 口( n ) ) 序 列ac 定义为：对于所有刀0 ，都有( 口c ) ( n ) = ( 口( n ) ) c 序列口。定义为： 口。( o ) = c ， 对于所有n 0 ，都有口。( n ) = 口( n 一1 ) 6 第二章代数理论 设6 1 ，口2 ，ai + 口2 定义为：对于所有1 1 0 ，都有( 口i + 口2 ) ( n ) - - 历i ( n ) + 口2 ( n ) ala2 定义为：对于所有n 0 ，都有( 口l 口2 ) ( n ) = al ( n ) 口2 ( n ) 因为中的加法和乘法都是按照分量计算的，所以半环a 的加法和乘法被a n 继承 了下来。因此 是半坏。 设d a ，如果d 满足下面的条件( d 1 ) ( d 3 ) ，则称d 是彳中的一个收敛集。 ( d 1 ) r l d 。 ( d 2 i ) 如果口l ，口2 ed ，那么口l + 口2 d 。 ( d 2 i i ) 女口果口d ，c a ，刃b 么c a d ，口c d 。 ( d 3 ) 女果口d ，c 彳，另b 么口c d 。 设d 是爿中的一个收敛集，l i m ：d 寸a 是一个映射，如果l i m 满足如下条件( 1 i m 1 ) 一( 1 i m3 ) ，则称l i m 是d 上的一个极限函数。 ( 1 i m l ) l i mr l = l 。 ( 1 i m 2 i ) 如果口i ，a2 d ，那么l i m ( ai + 口2 ) = l i m ( a1 ) + l i m ( a2 ) 。 ( 1 i m 2 i i ) 如果口d ，c a ，勇b 么l i m ( c a ) = cl i m ( a ) ，l i m ( ac ) = l i m ( a ) c 。 ( 1 i m 3 ) 女口果口d ，c a ，习b 么l i m a 。= l i m a 。 由定义可见，对于任意c a ，都有l i mcn = l i mr lc = c 。 经常不特别指明d 和l i m ，而利用术语“a 中收敛”和“a 中极限”，而且只有在极 限存在时才考虑收敛集合。l i m0 l 也常常表达为l i m 。一o o 口( n ) 。 因为收敛序列一定有极限，所有l i m a 也可以表示为l i m 。专0 0 口( n ) 。最小收敛集 d d a n 满足条件( d 1 ) 一( d 3 ) ，且有 o d = 口：存在n 口o 使得对于一切k o 都有口( n a + k ) = 口( n a ) ) 离散收敛：定义映射l i m a ：d a 专a ，l i m a ( a ) = 口( 1 1 6 ) ，则函数l i m a 满足条件( 1 i m l ) 一( 1 i m 3 ) ，称引入收敛仍和极限函数l i m d 的收敛叫做离散收敛，且对于任意的收敛集 d ，如果口d a ，贝u 有l i m a = l i m d 口。 2 1 4 半环中的恒等式 l 、准逆与星 半环中元素的幂：设a 是半环a 中的元素，定义a o = l ，对于n 1 ，定义a n = a a 旷1 。 ，”、。 设d 是a 的”一个收敛集，口儿如果l 蔷口7j d ，则称嬲蔷为口的 准逆，记为a + 。即a + = l i my a ，。 , 1 - - o 0 0 _ 语言半环上的有限自动机的推广 如果( 姜口7 。，则称! 姥嘉口。为。的星，记为口。即以= ! 壁姜口。 如果a + 存在，那么a + 存在，且a = 口+ + 1 = 1 + a + 。 如果a 存在，那么a + 存在，且a + = a a = a * a 。 设口彳，( 委口7 。，如果( 窆j = o 口7 ) 是离散收敛的，则存在。，使得对一 _ + in 切七0 ，都有口7 = 。 j = oj = o 2 、半坏中的恒等式 设彳是半环，d 是a 的收敛序列集，l i m 是d 上的一个极限函数，a ，a l ，a 2 是半环a 中的元素。 定理2 1 3 1 ( q 口：) + 存在当且仅当( a 2 a ，) 。且在( a l a 2 ) 存在情况下， ( a l 口：) + q = q ( a 2 a 1 ) + 。 定理2 2 吲如果( q + 哆) ，q ，a 2 a l * ) 存在，且。l i r a 。( + a 2 ) ”= 0 ， 那么 a l + 嘭) = a 1 ( 叩，+ ) + = ( a l * a 2 ) q 。 定理2 3 【3 1 如果( q + 口2 ) ，q ，( q + a 2 a l * a 2 ) 存在，且 l i m a i ”= 1 1 墨a l + a 2 a l 嘭) ”= o ， 盯 一 7 那么 ( 口i + 啦) = ( q + a 2 a 1 呸) + 1 + a 2 ) 。 2 2 形式幂级数 设是非空集合，掌是由生成的自由幺半群。设s 是一个非空集合。称+ 到s 的映射，为形式幂级数。厂在w e y * 处的值记为仉叫，记r 为 r = ( ，w ) w w 称仉叫为此幂级数的系数。称，为变量在中的幂级数。所有幂级数组成的集合记为 s 。 s 可以是幺半群、半环，本文主要讨论的是半环。 设彳是半环， ，彳 ，r 的支撑汜为 s u p p ( r ) = 加三事i 一训刃 如果一个幂级数r a 的所有系数足1 或0 那么这个幂级数叫做语言l 水 = r 彳 ：s u p p ( r ) s ) ， 彳 = 厂a ：s u p p ( r ) 占) ) 对于任意w 木，( o ，w ) = o 。，= 盖醋 户协虢 子集记为a ，称 设a e a ，r ，r l , r z e a ，w ，l c ，引入幂级数的如下运算： ( r l + r 2 ，w ) 2 ( r l ，w ) + ( r 2 ，w ) ， ( r l r 2 ，w ) 2 。眦：。( r l ，w 1 ) ( r 2 ，w 2 ) ( a r ，w ) 2a ( r ，w ) ， ( r a ，w ) 2 ( r ，w ) a 下面证明如果 是半环，则 a ，+ ，0 ，s 是半环 l 、证明( a ，+ ，0 ) 是交换幺半群 ( 1 ) ( 0 + r ，w ) = ( 0 ，w ) + ( r ，w ) = o + ( r ，w ) = ( r ，w ) 即o + r = r 同理可得r + o = r 说明0 是加法 的恒等元。 ( 2 ) ( ( r l4 - r 2 ) 4 - r 3 ，w ) = ( ( r l4 - r 2 ) ，w ) + ( r 3 ，w ) - - ( r l ，w ) + ( r 2 ，w ) + ( r 3 ，w ) 5 ( r l ，、) + ( r 2 + 1 3 ，w ) 2 ( r l + ( r 2 + r 3 ) ，w ) 综上所述( 彳 ，+ ，o ) 是幺半群，如果a 是交换幺半群，则a 也是交 换幺半群。 2 、证明( 彳 ，是幺半群 ( 1 ) ( r 占，w ) 2 。w 。：( r ，w 1 ) ( s ，w 2 ) 2 ( r ，w ) ( s ，s ) 2 ( r ，w ) 即r o c 2 r 同理可得cr2r 说明 s 是乘法的恒等元。 ( 2 ) i i l ：明结合律 ( ( 吨) r 3 ，w ) 2 w = w w 3 ( q r 2 ，w ) ( r 3 ，w 3 ) ，( 。却：( _ ，w - ) ( r 2 ，w z ) ) ( r 3 ，w ，) 9 语言j ，环上的有限自动机的推广 同理可得 2 ( 。却：( r l ，w - ) ( r 2 ，w z ) ( r 3 ，w ，) ) 2 。：m 屹心( r l ，w 一) ( r 2 ，w z ) ( r 3 ，w ，) ( r l ( r 2 r 3 ) ，w ) 2 。硼峨( r l ，w - ) ( r 2 ，w z ) ( r 3 ，w ，) 因此，( r f f 2 ) r 3 = r l ( r 2 r 3 ) 。于是， 3 、证明乘法对加法的分配率 ( a 木，是幺半群。 ( ( r l + r 2 ) r 3 ，w ) 2 w = w i w 2 ( r l + r 2 ，w - ) ( r 3 ，w ：) 2 。州：( ( r l ，) + ( r 2 ，w ) ) ( r 3 ，w z ) 2 。叫：( ( r l ，川) ( 吩，w z ) + ( r 2 ，w t ) ( r 3 ，w z ) ) 2 w = w i w 2 ( r l ，w 1 ) ( 巧，w z ) + w ：w i w 2 ( r 2 ，嵋) ( 吩，w z ) = ( r l r 3 ，、 ，) + ( r 2 r 3 ，w ) = ( r f f 3 + r 2 r 3 ，、) 所以( r l + r 2 ) r 3 = r l r 3 + r 2 r 3 ，同理可得r l ( r 2 + r 3 ) = r f f 2 + r l r 3 。 4 、( o r ，w ) 2 w ：w i w 2 ( o ，w 一) ( r ，w ：) 2 0 ，( r o ，w ) 2 w m w i w 2 ( r ，w - ) ( o ，w z ) 2 0 所以 a ，+ ，0 ，f 是半环 a 半环向a 半环转换 若r ea ，l c ，w 丰则( r ，w ) a 依据它就可以将a 半环向水 半环进行 转换。设a e a ，r ，r l , r 2 a 丰 ，w e 丰，根据前面幂级数的运算和规定可得。 同理可以将序列半环( ，+ ，oo ，了1 ) 转换到( 彳 ) n 或 半环上， ( 彳 ) n 和“木 这两个半环同构。如果d 是a n 的收敛集，则d 是( 彳 ) n 上的收敛集，d 上的极限函数定义为l i m ：d j 彳 ，如果( r ，f ) = o ，即空字前的系数为0 ，则称r 是准f 则的或是f 的。如果r e a 是准正则的，那么r 木总是存在的，且r 木= ( 兰厂，w ) w ) 。 w e e + 设r ea ，如果l i m ( r ，s ) 。= 0 ，那么称r 是无循环的。 w 己 第二章代数理论 2 3 矩阵 矩阵：设，和，是两个非空的町数指标集，称，i 到半环a 的映射m 为 矩阵。 2 3 1 矩阵的表示 设i ，i 。，把 在 数。把半坏彳上的所有的i i m 下的象记为m u ，称之为矩阵m 的( f ，i 。) 系 矩阵组成的集合记为么川 若l 是单点集，则称m 为行向量；若i 是单点集，则称m 为列向量；若i 和i 都 是有限集合，则称m 为有限矩阵。 对于每个i i ，令 r ( i ) = 俐m i ，f 0 ) ， 如果对于每个i i 令r ( i ) 是有限集，则称m 是行有限的。对于每个i i ，令 c ( i ) = f | m i ，i o ， 如果对于每个i f ，都有c ( i ) 是有限集，则称m 是列有限的。 彳表示所有行有限矩阵组成的集合，彳岔，表示所有列有限矩阵组成的集合， 么：x ，表示所有行列有限矩阵组成的集合。 一般地，i 表示非空可数指标集，q 表示有限指标集。本文中有限自动机上的矩阵 都是行有限自动机，因此后面的所有矩阵均指有限矩阵。 2 3 2 半环a 扩展到矩阵半环a “7 由于矩阵的加法和乘法都是矩阵对应元素在半环a 上的加法和乘法，这样就可以把 半环上的概念扩展到矩阵半环上。 下面证明如果 是半环，那么 ， ， 都是半环 如果m l ，m 2 a 7 ，定义和m + 鸩a h 7 ， 对于任意f ，f i ， ( m + m ：) ，= ( m ) v + ( m z ) ， 即矩阵的加法是加法对应元素在半环a 上的加法。零矩阵是每个元素都是0 的矩阵即 ( o ) = o 。有了上面的概念就可以知矩阵的加法符合结合律和交换律且单位元是0 ， 这样就可以将半环a 的相应概念扩展到矩阵上，那么 ， ， 都足交换幺半群。 对于瞄a ，i x ，m ，a7 ：“，若则定义积m 是行有限的，或尬是列有限的，则定 义m l m 2 a 小7 3 为 l l 语言、i - 环上的有限白动机的推广 ( m ，m ：) 仙= z ( m ，：( m z ) ，2 ，。 如果蚴是行有限的，那么积的定义中和的指标集为r ( i l ) 如果尬是列有限的，则 积得定义中和的指标集为c t 6 ) ，他们都是乃的有限子集，因此如上和式有定义。定义 单位矩阵e a a 7 为： e l , 2 - 2 蕞毫 称瓯，b 为k r o n e c k e r 符号。 即矩阵的乘法是矩阵对应元素在半环a 上的先乘后加，矩阵乘法满足结合律且矩阵 的乘法对加法符合分配律，e 是矩阵乘法的单位元，0 是矩阵乘法的零元，综上所述可 知 ， ， 都是半环，在后面彳? 7 表不这三个半环中的任蒽一个。 2 3 3 矩阵半环中的收敛 设a 是半环，刃是a 上的一个收敛集，l i m 是刃上的极限，下面将彳上的收敛 集和极限转换到a i x i 对于序列( 彳川) ，序列的第n 个元素是( ，z ) 。对于任 意f j i ，形成一个系数序列 鸬，( 么) 帆a ，( 聍) = ( ”) u 。 定义设d 是半环彳的一个收敛集，如下定义a n 7 中的收敛集 喀( 么 7 ) 一，p r 当且仅当 ( i ) 对于任意f ，j 1 ， 序列鸬。，d ， ( i i ) 对于每个i 1 ，存在有限集合1 0 , ，f ) s i ， 使得对于所有j i - i ( u ，f ) 都有鸬。，= 0 。 直观的讲，有限矩阵的半环彳瓜7 中的序列是收敛的充分必要条件是对于任意 f ，j ，( ，f ) 都有鸬，j 在a 中收敛，且对于任意f ，j l - i ( u ，f ) 都有 h l 。j = 0 o 按照收敛集的定义可以验证d r 是( 彳 叫上的收敛集。同样可以验证映射 l i m r ：d r - - - a t m ( 1 i m r 曲i = l i m p ，j 是d 矗上的极限函数。同理可以将么上的收敛集合极限转换到彳分7 半环上。 下面将离散收敛集仍转换到矩阵半环a 似7 上，表示为例r ，且可以验证 l i m n ：( d o r a l ，( 1 i m r 0 i j = l i m a i ，t i j 论 是a 。上的收敛。根据半环a 向形式幂级数的转换时定义的极限函数l i m o ! = l i r a ( o r ，w ) w e 矩阵半坏的收敛转到形式幂级数矩阵半环的收敛。 2 3 4 分块矩阵 考虑在a 7 中的矩阵m 。 假设存在非空可数指标集合，对于每个，是，咆一个非空可数子集，使 得u 一，且对于任意 ，五， 五，都有j inl = ，则称 l ：j ) 是 ，酶l 个划分。，的一个划分把，分解为两两互不相交的非空子集的并。 矩阵的定义知m ：i x i a 是一个映射，把映射的定义域限制在lxl j , 上得到 映射m ：i j , x 厶专爿，按照矩阵的定义，这是a 厶。如中的一个矩阵，记为m ( i j , ，i s ：) ， 称之为m 的( ，乇) 块。可知如果m 彳h 7 ， 则 m 氓，i j 2 1 詹p m o 设m l ，m 2 a 7 ，对于任意 ，j 2 ， 块 m ( ，：) ，m ：( ，：) a 叫2 ， 由么 7 z 的矩阵与a 7 ：蚶，中的两个矩阵之积是彳，l x 6 中的矩阵知。对于任意 歹j ，m 。( ，) 彳 7 ，m ：( ，：) 彳弘止，都有m ，( l ，) 鸩( 1 ，一，：) a 。进一步 的，对于任意，之厶， 因为 l m ( l ，) 鸠( ，厶) i j “ ，吐 2 若m ( ) 鸩( 蚀) 仙 = ( m ) ( 鸩) ： = ( m ) ( 鸩) 忱 = ( m 鸩) “ ， 所以，根据矩阵相等的定义得 (