（计算机软件与理论专业论文）基于半环代数理论的有限自动机的探讨.pdf

基于半环代数理论的有限自动机的探讨 中文摘要 在形式语言与自动机的经典理论中，由于所选用的数学工具的局限性，造成 了证明的繁杂性，降低了证明的可读性。本文利用半环方法来讨论有限自动机， 半环方法通过有限自动机与半环中的线性代数之间的联系，将有限自动机的研究 转化为半环上的线性方程的讨论，使得有限自动机的证明更加简洁，具有更好的 可读性。本文从以下几个方面进行相关讨论。 1 介绍了线性代数的基础知识。首先，从半环的概念特别是偏序半环引入 了本文所讨论的幂集半环，它是所有语言的集合。然后，逐步将半环及其相关的 性质扩展到矩阵半环上，得到幂集矩阵半环。最后，建立起幂集矩阵半环中的矩 阵与有限自动机的联系。 2 介绍半环上的有限自动机。首先，证明了半环上的有限自动机与不确定 的有限状态自动机识别语言的一致性。然后，用有限自动机的半环方法来证明有 限自动机的经典方法以及相关的结论，并且通过对比传统的证明方法来对正则语 言的性质的进行证明。 3 给出了半环上带有输出的有限自动机。为了与传统的带有输出的有限自 动机进行对比，首先介绍了m o o r e 机和m e a l y 机的工作原理，然后引入了半环 上的有理转换器。通过对有理转换器的讨论使得对半环上的有限自动机的讨论得 到了更进一步的发展。 关键字：半环；线性代数；有限自动机；正则语言 d i s c u s s i o no ff i n i t ea u t o m a t ab a s e do na l g e b r a i c 1 ，“ 。 1n e o r y0 t5 e m l r l n s g r a d u a t en a m e ：z h i q i a n gs u n m a jo r ：c o m p u t e rs o f t w a r ea n dt h e o r y d i r e c t e db y ：y a o j u nl i u a b s t r a c t i nt h ec l a s s i c a lt h e o r yo ff o r m a ll a n g u a g e sa n da u t o m a t a ，t h e c o m p l e xp r o o f sh a v e b e e nr e s u l t e d i nd u et ot h el i m i t a t i o n so f m a t h e m a t i ct o o l st h a tw e r es e l e c t e da n dt h er e a d a b i l i t yo ft h ep r o o f si s r e d u c e d i nt h i sn o t ef i n i t ea u t o m a t aw i l lb ed i s c u s s e db yt h em e t h o d so f s e m i r i n g s ，w h i c hw i l lt r a n s f o r mt h er e s e a r c ho ff m i t ea u t o m a t ai n t ot h e d i s c u s s i o no fl i n e a re q u a t i o n so fs e m i r i n g sb yt h el i n kb e t w e e nf i n i t e a u t o m a t aa n dl i n e a r a l g e b r ao fs e m i r i n g st om a k et h ep r o o f so ff i n i t e a u t u m a t am o r ec o n c i s ea n dr e a d a b l e t h en o t ec o n s i s t so ft h r e ep a r t sa s f o l l o w s 1 t h eb a s i ck n o w l e d g eo fl i n e a ra l g e b r aw i l lb ei n t r o d u c e d f i r s t l y ， t h ep o w e rs e ts e m i r i n gw i l lb ei n t r o d u c e df r o mt h ec o n c e p to fs e m i r i n g s i np a r t i c u l a rp a r t i a ls e m i r i n g s ，w h i c hi sa l s ot h ec o l l e c t i o no fl a n g u a g e s e c o n d l y ，s e m i r i n g sa n dc l o s e l yr e l a t e dp r o p e r t i e s w i l lb e g r a d u a l l y e x t e n d e dt om a t r i xs e m i r i n g sa n dt h ep o w e rs e tm a t r i xs e m i r i n g sw i l lb e o b t a i n e d f i n a l l y ，t h el i n kw i l lb ee s t a b l i s h e db e t w e e nt h ep o w e rs e t m a t r i xs e m i r i n g sa n df i n i t ea u t o m a t a 2 t h ef i n i t ea u t o m a t o nb a s e do ns e m i r i n g sw i l lb eg i v e n t ob e g i n w i t h ，t h ei d e n t i t yw i l lb ep r o v e db e t w e e nt h ef i n i t ea u t o m a t o nb a s e do n s e m i r i n g sa n dn o n d e t e r m i n i s t i cf i n i t ea u t o m a t o n m o r e o v e r ，t h ec l a s s i c a l m e t h o d sa n dc l o s e l yr e l a t e dt h e o r yw i l lb ep r o v e db yt h ef i n i t ea u t o m a t o n a n dt h ep r o p e r t i e so fr e g u l a rl a n g u a g ew i l lb ep r o v e db yc o m p a r i n gw i t h t h ec o n v e n t i o n a lm e t h o d s 3 t h ef i n i t ea u t o m a t o ne q u i p p e dw i t ha n o u t p u td e v i c ew i l lb e d i s c u s s e d i n o r d e rt o c o m p a r ew i t ht r a d i t io n a lf i n i t ea u t o m a t a ，t h e w o r k i n gp r i n c i p l eo ft h em o o r em a c h i n ea n dm e a l ym a c h i n ew i l lb e g i v e nb e f o r er a t i o n a lt r a n s d u c e r ，w h i c hw i l lb ed i s c u s s e dt om a k et h e d i s c u s s i o no ff i n i t ea u t o m a t af u r t h e rd e v e l o p m e n t k e y w o r d s ：s e m i r i n g s ；l i n e a ra l g e b r a ；f i n i t ea u t o m a t a ；r e g u l a rl a n g u a g e 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：驷幺二数 日期：乙愈口叶孓。ft 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：翻丝= 圣k 弋 日期： 导师签 j y ? 十 隰霉：兰：! 望! 第一章引言 第一章引言 自动机理论和形式语言是理论计算科学专论系列中最古老的学科之一，有限自 动机和正规语言的研究可追溯到2 0 世纪4 0 年代初，那时m c c u l l o c h 和p i t t s i l j 把有 限状态机器用做神经网络模型，此后正规语言开始被广泛的研究。例如，早期科学 研究的结果是k l e e n ，st h e o r e m 2 】建立起正则表达式和有限自动机的等价性，m e a l y 3 】 和m o o r e t 4 li 入了带有输出的自动机，r a b i n 和s c o t t 5 j 引入了不确定的有限状态自动 机以及m y h i l l 6 1 和n e r o d e 7 1 描述了有穷指数和正规语言的相容性。 1 1 有限自动机的模型 有限自动机是识别正则语言的模型。一台有限自动机用离散的步骤一个字母一 个字母的读取字母表中的字w 。它有有限个内部状态( 状态是组成自动机的仅 有的记忆装置) ，在每一时刻，它处于这些状态之一。下一时刻的状态依赖于这个 状态和当前时刻读入的字符。从这个意义上讲，字母的读入导致状态的转移。自动 机有一个特殊的初始状态和一个特殊的终状态集合。以在初始状态下读入w 的第 一个字母开始，产生一个状态转移序列，如果读完整个字w 后到达某个终状态， 则称w 被该自动机接收。所有被接收的字组成被自动机接收的语言。按照这个思 路，可以设计出如图1 1 所示的识别模型： l 口，a 2 a 3 q l a m jl if s c 图l 一1 有限状态自动机的物理模型 f i g 1 - 1p h y s i c a lm o d e lo f f i n i t es t a t ea u t o m a t a 首先，它有一个输入带。该输入带上有一系列的“带方格”，每个带方格可以 存放一个字符。为了不让输入带的存储容量影响对主要问题考虑，约定，输入串从 输入带的左端点开始存放，输入带的右端是无穷的。这就是说，从左端点的第1 个 带方格开始，输入带可以存放任意长度的输入字符串。其次，系统有一个有穷状态 控制器( 贮) ，该控制器的状态只有有限多个。f s c 控制一个读头，用来从输入 带上读入字符。每读入一个字符，就将读头指向下一个等待读入的字符。 1 基于半环代数理论的有限自动机的探讨 约定，系统的每一个动作由三个节拍构成：读入读头所指向的字符；根据当前 状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。 1 2 有限自动机的目的和意义 有限自动机和它所识别的正规语言8 。1 5 1 有着非常广泛的应用，它们已经大量的 用于程序设计语言的词法分析，用户界面的翻译【1 6 ，17 1 。其他显著的应用有电路的设 计【1 8 1 ，文本的编辑，模式匹配【1 9 】。近几年，它们进一步的应用到并行处理【2 0 - 2 2 1 ，图 像的生成和压缩【2 3 】。2 5 1 ，面向对象语言【2 6 1 的典型理论，以及d n a 2 7 , 2 8 】的计算等等。 1 3 当前国内外研究现状 当前国外的一些专著中，语言和自动机理论【2 9 。1 1 使用数学方法取得了许多成果， 这些数学方法有半环【3 2 斟】，形式幂级数，定点理论【3 5 1 和矩阵【3 6 - 3 8 1 等。从数学角度来 看，这些数学结构、定义、构造、解释以及证明等都非常令人满意。这些数学结构 的使用体现了很多的优势。 国内近年对于半环数学理论的研究取得了较多成果，同时自动机的研究也有较 多的研究成果发表，但是将半环与自动机两者进行结合的研究与国外存在很大差距。 相应的研究成果在国内刊物上较为罕见。 1 4 本文的工作 本文利用半环方法来讨论有限自动机，由于有限自动机的半环方法是建立在线 性代数的基础上的，所以首先从线性代数的知识入手，并且建立自动机与半环的联 系。 第二章，介绍线性代数基础。首先，介绍幺半群，半环，半模的概念，讨论了 特殊的半环偏序半环，引出了本文介绍的半环p ( ) ， 它是所有语言的集合。然 后，介绍了收敛，方程和恒等式。其次，介绍了矩阵和分块矩阵，然后把半环扩展 到矩阵半环上，把相关的概念如收敛，方程和恒等式等都扩展到矩阵上，逐步形成 了本文讨论的( p ( + ) ) 缈q 矩阵，并开始研究( p ( ) ) 。口矩阵上的恒等式，即矩 阵的星运算，以及方程的解。最后，介绍了同态，表示与替换【3 2 】的概念，这是半环 上有理转换剁3 2 , 3 叫2 1 的基础。 第三章，介绍了半环上的有限自动机3 2 1 。首先，给出半环上的有限自动机的定 义，证明了半环上的有限自动机与不确定的有限状态自动机识别语占的一致性4 3 1 。 2 第一章引言 其次，用半环上的有限自动机来讨论经典理论的证明，比如带有s 一转移的有限自 动机不增加有限自动机的能力，以及正则语言的性质并且和传统的组合理论【删的证 明方法进行了对比。最后，讨论半环上带有输出的有限自动机，通过和m o o r e 机【4 5 】 和m e a l y 机【4 5 】的对比，引入了半环方法中的有理转换器。有理转换映射是形式语言 理论中最为广泛的研究课题之一。 第四章，作为结束语，对论文所作的工作进行了总结，并对下一步的工作进行 了展望。 3 第二章线性代数 第二章线性代数 2 1 半环 2 1 1 幺半群 幺半群是一个三元组：一个非空集合m ，m 上的一个结合的二元运算， 和一个恒等元素1 ，使得对于任意的a 都有1 a = 口l 。如果对于任意的口，b m 都有a b = b o a ，则称幺半群为交换幺半群。二元运算符经常被省略，把二元 运算叫做乘法。通常把幺半群记为( m ，1 ) ， 如果二元运算符和恒等元是明显 的，则幺半群可记为m 。 形式语言与自动机中最重要的一类幺半群是由非空可数集生成的自由幺半 群+ ，其中是由所有形如：鼍，一的有限串( 也叫做字) 组成的集合， 两个串，w 2 的积是把字比接在字之后所形成的字心，单位元是不含 任何字母的字，称为空字，记为。 称为字母表，称中的元素为字母或符号。一般情况指为有限集。 称字w 中出现字母表中字母的个数( 重复出现的以出现的次数计算) 为字w 的长度，记为i w i ，由定义知，h = 0 。 设是有限字母表，称+ 的子集为上的语言。设厶，乞互+ ， 则语言 厶与厶的乘积定义为 厶厶= w 。w 2w l 厶，w 2 l 2 ) 设s 是一个集合，称s 所有的子集组成的集合为s 的幂集，记为v ( s ) 。 则p ( z + 1 是所有语言的集合。 幺半群m 到幺半群m 的同态是一个映射h ：m m ，此映射与m 和 m 中的恒等元与运算相容，即办( 1 ) = 1 ，其中1 和1 分别是m 和m 。中的 恒等元，h ( m , m ：) = 办( 铂) j l z ( ，z ：) ，其中玛，m ：是m 中的任意元素。 5 基丁- 半环代数理论的有限自动机的探讨 2 1 2 半习、 半环是带有两个二元运算+ 、和两个特殊元素0 、1 的集，使得 ( i ) ( 么，+ ，0 ) 是交换幺半群； ( i i ) ( 4 ，1 ) 是幺半群； ( i i i ) 分配律成立，即v a ，b ，c 么，口( 6 + c ) = 咖b + a c ，( 口+ 6 ) c = a c + b c ； ( i v ) v a a o a = a 0 = 0 。 如果对于任意口，b a ，都有a b = b a ，则称半环彳为交换半环。 半环通常记为( 4 ，+ ，0 ，1 ) ， 如果该半环的运算符和常值元素都是明显的，则 此半环简记为么。 半环彳到半环么的同态是一个映射h ：a 专么。，此映射与彳和么中的 常值元素和运算相容，即h ( o ) = o ，办( 1 ) = 1 ，其中0 ，1 和0 ，1 分别是a 和彳1 的恒等元，h ( a 。+ 呸) = h ( a ，) + 办( 口：) ，h ( a ，口：) = h ( a 。) 办( 口：) ，其中q ，呸是么中 的任意元素。 ( p ( + ) ，u ， s ) ) 是半环。 孽明：因为并运算满足结合律和交换律，且并的零元暑空集，所以( p ( + ) ，u ，。) 是交换幺半群。 因为乘法运算满足结合律，且乘法的零元是空字集，所以( p ( z ) ， ) ) 是幺 半群。 因为对于任意的厶，三：，厶p ( ) ，根据并和乘法的定义可得： 厶( 厶u 厶) = 厶厶ua ，( 厶ul 2 ) z = 厶厶u 厶厶， 所以乘法对并满足左右分配律。 对于任意的lep ( ) ，都有：= 三= 。 综上所述，( p ( z ) ，u ， ) 是半环。也简记为p ( ) 。 6 第二章线性代数 2 1 3 特殊半环 零和自由半环： 如果对于半环彳中任意两个元素a i , a ：，都有口l + a 2 = 0 蕴含口1 = a 2 = 0 ， 则称彳是零和自由的。 很明显，p ( + ) 是零和自由的。对于厶，i 2 p ( ) ，因为只有厶= 厶= 才 有厶+ 厶= ，所以p ( ) 是零和自由的。 偏序半环： 如果彳拥有偏序， 且对于么中任意元素口，a 。，a ：，都有 ( i ) 0 a ： ( i i ) 如果a i a 2 ，贝0 有a l + 口a 2 + 口； ( i i i ) 女口果a l 口2 ，贝0 有a l a a 2 a ，且a 口1 口a 2 ； 则称么是偏序的。 ( 如果彳上的二元关系对于么中任意元素口，a 。，a 2 都有 ( i ) a a ： ( i i ) 如果口l a 2 且a 2 a i ，贝0a i = a 2 ； ( i i i ) 女口果a i a 且a a 2 ，贝0a i a 2 ； 称是彳上的一个偏序。) p ( ) 是偏序半环。 证明：设厶厶，l ：p ( + ) ，因为三三， 因此是自反的。 如果厶g 厶且厶厶，则厶= 厶。因此是反对称的。 如果厶l 且三乞，则厶g 厶。因此是传递的。 综上所述， g 是p ( ) 上的一个偏序。 因为中三，所以是p ( + ) 中的最小元。 如果厶s 厶则有( 厶u ) s ( 厶u 三) 。 7 基于半环代数理论的有限自动机的探讨 如果厶sl 2 则有厶三厶且地互l 已。 综上所述，p ( ) 是偏序半环。 幂等半环： 如果在半环a 中，1 + 1 = 1 ，则称彳是幂等的。如果彳是幂等半环，那么 对于任意元素口a ，都有a + a = a ( 1 + 1 1 = a 。 p ( ) 是幂等半环。 i i e n ：设任意le t ( e + ) ，因为l u l = l ，所以p ( ) 是幂等半环。 2 1 4 半模 设a 是半环，( v ，+ ，0 ) 是交换幺半群， 是ax v 专a 的算子，如果 v a ，b a ，v v ，w v 都有 7 ( i ) ( a b ) v = a ( 6 v ) ； ( i i ) ( 口+ 6 ) v = 口v + b v ，a ( v + w ) = 口v + a w ； ( i i i ) 1 v = v ，0 v = 0 ； ( i v ) 口0 = 0 。 则称y 是彳半模。 由定义可知，每个半环彳是4 半模。 2 2 收敛、方程和恒等式 2 2 1 收敛 序列：称映射a ：n 专a 为彳中的序列。把a 中所有的序列组成的集合记 为a 。如果a a ，则记口= ( a ( 刀) ) 。 零序列0 定义为：对所有的，? 0 ，都有o ( 刀) = 0 。 单位序列r 定义为：对所有的刀0 ，都有o ( n ) = 1 。 设a a ，c a ，序列删定义为：对所有的n 0 ，都有( 阳) ( 行) = c a ( t ) 。 序列i x c 定义为：对所有的玎0 ， 都有( a c ) ( 门) = a ( 门) c 。 r 第二章线性代数 序列a 。定义为：a 。( 0 ) = f ， 对所有的，? 0 ， 都有a ，( 玎) = a ( n - 1 ) 。 设a l ，a 2 a ，a 1 + a 2 定义为：对所有的，? 0 ，都有 ( a 。+ a ：) ( 聆) = q 。( 玎) + 仅：( 刀) 。 a ，a ：定义为：对所有的力0 ，都有( a ，a ：) ( 行) = a ，( ”) a ：( 胛) 。 容易得到( a n , + ，0 ，7 7 ) 是半环。 收敛集：设d 璧a ，如果d 满足下列的条件( d 1 ) 一( d 3 ) ，则称d 是a 中的一个收敛集。 ( d 1 ) 7 7 d ； ( d 2 ) ( i ) 女口果a l ，a 2 d ，男b 么a 1 + 仅2 d ； ( i i ) 妻口果a d ，c a ，男巧么c 口d ，a t ：d ； ( d 3 ) 如果a d ，c a ， 那么a 。d 。 极限函数：设d 是么中的一个收敛集，l i m ：d - - - 9 a 是一个映射，如果l i m 满足如下条件( 1 i m l ) 一( 1 i m 3 ) ，则称l i m 是d 上的一个极限函数。 ( 1 i m l ) l i m r = 1 ： ( 1 i r a 2 ) ( i ) 如果a 】，a 2 d ， 那么 l i m ( a l + a 2 ) = l i m a l + l i m a 2 ； ( i i ) 如果a d ，c a ，那么 l i m ( c a ) = c l i i i l ( a ) ，l i m ( a c ) = t i r n ( a ) c ； ( 1 i m 3 ) 如果口d ，c a ，那么l i m ( a 。) = l i m a 。 最小收敛集仍a n 满足条件( d 1 ) 一( d 3 ) ， 且有 仍= a 彳i j o ，v k _ 0 ，a ( + 七) = a ( ) ) 。 离散收敛：定义映射l i m d ：见一a ，1 i m d ( a ) = 倪( ) ，则函数l i m d 满足条件 9 基于半环代数理论的有限自动机的探讨 ( 1 i m l ) 一( 1 i m 3 ) ，称引入收敛集仍和极限函数l i m d 的收敛叫做离散收敛。 且对于任意的收敛集d ，如果a 仍，则有l i m a = l i m d a 。 半环中元素的幂：设a 是半环彳中的元素，定义口o = l ， 对于玎1 ，定 义口”= 口口”。 准逆：设。是么的一个收敛集，口彳，如果( 喜口1 。，则称墼喜口， 为g 的准逆，记为a + 。即口+ = l i my 口j 。 ? t - - - o o _ 星：如果( 喜口 。，则称卿姜口7 为口的星，记为口。即口+ = 熙喜口。 如果口+ 存在，那么口存在，且口= a + + 1 = 1 + 口+ 。 如果a 存在，那么口+ 存在，且口+ = a a + = a * a 。 设口么，( 窆j = o 口1 。，如果( 窆j = o 口1 是离散收敛的，则必存在。，使 n + kn 得对一切k 0 ，都有ya j = y 。 j _ _ 一j _ _ - j = oj = o 设y 是彳半模，称映射a ：n v 为y 中的序列。把y 中所有的序列 组成的集合记为v 。如果a v ，则记a = ( a ( 玎) ) 。 如果a a n , v v ，定义a v v 对于所有刀0 ，( a v ) ( 玎) = a ( 疗) 1 ，。 如果a l , a 2 v ，定义a l + 口2 v 对于所有刀0 ， ( a 。+ a ：) ( 刀) = a 。( 刀) + a ：( ，z ) 。 设彳是半环，d 是么的收敛序列集，l i m 是d 上的一个极限函数，设 y 是一个么半模。如果 a f v f = f l y ，胛1 , a ，d ，v ，v y ， t = l 1 0 篁三至垡堡垡鍪 一 一_ 一 蕴含l h n ”a ，1 ，= v ， 则称么一半模y 与彳相容。 a 一半模a 与a 相容的。 证明：如果 a ，口，= 叩口， 那么 ，；1 秘吣) 铲喜i m ( a 一) - l i m x ，( q ) “m ( 叼口) 2 2 2 方程 设y 是彳一半模， y 与4 相容， 口a ， ge 矿，y 是变量，如果s y 且 j ：傩+ v ，称5 是方程y = a y + v 的一个解。 引理2 1 【3 2 】如果a 存在，则s = 口v 是方程y = a y + v 的一个解。若 l i r a 口n ：0 ，那么此解是唯一的。 设彳是半环，d 是么的收敛序列集，l i r a 是d 上的一个极限函数， 口，q ，a 2 ，口3 ，a 4 是半环么中的元素。 公式2 一l 【3 刁( 口。口：) + 存在当旦仅当a 2 a 1 ) + 。且在( a l c 2 ) 存在情况下， ( 口。口：) q = 口。( c 2 1 1 ) 。 公式2 2 【3 2 1 如果( a 。+ 口：) + ，q ，( 口：口1 + ) 存在，且。l i r a 。( 口十a z ) ”= o ， 那么 ( q + 呸) + = a l * ( 呸q ) = ( 口l a 2 ) 口。 公式2 3 3 2 1 如果( q + 呸) ，a t + , ( q + 口：口。口：) 存在，且 l i m a 。= 煅( q + 口z 口l 口z ) ”= o ， 那么 ( q + 口：) = ( q + 口2 q 。a 2 ) + 1 + a 2 a 。+ ) 。 2 2 4 偏序半环中的序列、方程和恒等式 如果么是偏序半环，对于任意a ，卢 a n , 仅卢的充分必要条件是对于所有 基于半环代数理论的有限自动机的探讨 的0 ，z ，都有a ( 疗) 卢( 挖) 。 假设彳是偏序半环，d 是彳中的收敛序列的集合，l i m ：d 寸a 是极限 函数。 如果对于任意的a ，卢d ，a 卢蕴含l i m a l i r a3 ， 称此极限函数l i m 与 彳上偏序相容。 对于任意偏序半环么，极限函数l i m d ：岛专彳与么上偏序相容。 证明：若a ，p 仍，由离散收敛知，存在0 聊， 使得 l i m d a = a ( 聊) ，l i m d 卢= 卢( m ) ， 如果a j e i ，由序列定义有a ( 聊) f l ( m ) ，即l i m d a l i m d 卢。 设方程 y = a y + 6 ，a ，b a 。 ( 木) 设s 是( 牢)的一个解，如果对于( 木)的任一解f ，都有j t ，则称 s 是( 木) 的极小解。 引理2 - 2 3 2 1 对于任意偏序半环彳，如果方程( 木) 有极小解，则极小解唯一。 如果a 存在，则a b 是方程的唯一极小解。 公式2 4 瞰1 对于任意偏序半环彳，如果( q + 口2 ) ，西，( 彳口：) + 存在， 那么 ( a l + 呸) = q ( 口：q ) + = ( a l * a 2 ) q 。 公式2 - 5 3 2 1 对于任意偏序半环彳，如果 ( c z 。+ c z ：) ，q ，( c z ：c z ：) ，( ( c c z ：) 2 ) + ，( c z 。+ c z ：c c ，：) 。 存在，那么 ( q + 口：) = ( 口l - 4 - a 2 q 呸) + ( 1 + a 2 a l * ) 。 2 2 5 强收敛 如果对于任意的a d 以及t t iea 使得( 口”) d 且舰口”= o ，都有 1 2 笙三至垡堡垡鏊 一一_ l _ 一一 滢k ( 舻歹) j d ，= o， 则称a 中的收敛为强收敛。 引理2 3 3 2 1 设么中的收敛是强收敛的，更进一步的假设( 口”) d 且 l i m 口”：0 ，则口存在，且对于任意的a d ，都有 l i m 善如( 州) “ 离散收敛是强收敛的。 证明：设彳是半环， ae4 ， 使得( 口”) 见且l i m d 口”= 0 。 设 仅仍，由1 i m d 口”= 0 知，存在r h 0 ，使得对于一切k o ，都有口啊= o ， 由a d d ，存在刀：0 ，使得对于一切k o ，都有 a ( n 2 + k ) = a ( n ：) ，熙a ( 刀) = a ( 玎z ) ， 对于序列f 窆口，a ( 玎一歹) ， 取咒，：+ n 2 - 1 o ， 则对于一切尼o ， ny3+k抛1t+肛肛”如(碍鸲-1+七一)=芝ajat ( 啊+ 他- 1 + 七一歹) 抛+ 七一，) = 乏口。c c ( 碍鸲一1 + 七一) 2 荟 ( 啊+ 他- 1 诎吖j ，_ 0 ，2 u j。 = a l a ( h 2 ) = a a ( n 2 ) 。 所以i 窆a j a ( 刀一歹) i 岛， 故岛是强收敛的。 y = 0 2 3 矩阵、方程和恒等式 2 3 1 矩阵 设，和，。是两个非空的可数指标集，称，到半环么的映射m 为矩 阵。设f j ，f j ，把( f ，f ) 在m 下的象记为m ，? ， 称之为矩阵m 的( f ，f ) 系数。把半环彳上的所有的l x j 矩阵组成的集合记为a 。 因为，和。是可数集，所以可以列举他们，设，= 乇，) ，= 乇，) ， 1 冀 基于半环代数理论的有限自动机的探讨 矩阵可以表示为： m = m m m 1 0 ，1 01 0 ，i1 0 ，匕 m m m j l ，z o1 l ，j l ，2 m ?m ?m ? 7 2 ，t 01 2 ，2 崆 矩阵m 的第i i 行为 ( m m “m 如) ， 矩阵m 的第i 。i 列为 m i o ，f m h t 7 m ，2 ， ： 如果和，是单点集，称m 是行或列向量。若，为含有玎个元素有 限集合 1 ，门) 或者i 为含有m 个元素有限集合 1 ，m ) ， 则把a 瓜7 记为 么州或者彳7 一。 如果j 和，都是有限集合，则称m 为有限矩阵。本文中有限自动机上的 矩阵是有限矩阵。因此后面的所有矩阵均指有限矩阵。 如果m ，鸠彳厶7 ，定义和m + 鸠彳a 7 ， 对于任意ie ，i ， ( m + 鸩) ，= ( m 。) - + ( m ：) 。 令0 是每个元素都是0 的矩阵，称之为零矩阵。 容易证明( 彳。，+ ，0 ) 是交换幺半群。 对于m 1 a l t 。1 2 , m 2 a 7 2 “，则定义积m l m 2 a 。厶为 ( m - 鸠) 仙= z ( m 。) 怕( m ：) 。 定义单位矩阵e a h 7 为： 1 4 笙三至垡堡垡垫 一 一 = 毛，匕= i i 。, ，i 毛i = 吩2 , 称瓦厶为炳n e c k e r 符号。则e 是矩阵乘法的单位元， o 是乘法的零元。 因此容易得到( 彳，+ ，o ，e ) 是半环。 彳“7 是么m 半模。 证明：因为( 彳，+ ，o ) 是交换幺半群，m ，4 川。中的加法定义为： ( m + ) l ，= ( m ) u + ( ) u ， 即矩阵加法对应于系数相加，所以按照遗传特性，( 彳m ，+ ，o ) 是一个交换幺半群。 依照矩阵乘法法则定义数量乘法：彳彳m 一彳m 。对于任意 a , b a i x i c ，d 么。x 。， 都有 a ( b c ) = ( 么口) c ， 彳( b c ) = ( 彳+ b ) c = 么c + b c ，么( c + d ) = 4 c + 4 d ， e c = c ， o m c = a o j 。= 0 j ，。 综上所述，彳灯是a 半模。 对于半环p ( ) ，( p ( + ) ) a 7 为半环p ( ) 上的所有j ，矩阵组成的集 厶 口。 设m ，m ：p ( ) 厶7 ， 对于任意f ，i 。j ， 定义和 ( m i + m ：) f ，= ( m ，) f ，u ( m z ) f ，f ， 即在p ( 1 j x 矩阵中两个元素的和是p ( + ) 半环中的并运算。对于i i f 2 ，f 3 ， 定义积运算： ( m - m ：) ，岛2 乏( m ) 一m z ) 纠 即矩阵的乘法是两个矩阵对应元素在半环p ( ) 上的乘法运算。 基于半环代数理论的有限自动机的探讨 定义0 矩阵： ( o ) g ，g = 。， 单位矩阵： c 伽“纠= 2 擘 则有( p ( + ) n 7 ，+ ，o ，e ) 是半环。 约定，由于半环中的加法是并运算，所以在本文中的求和符号和u 可通 用的，不再区别。 下面将收敛集和极限从半环彳扩展到矩阵半环彳a 7 上。 对于序列肛( 彳川) n ，序列j “的第n 个元素是“( 玎) 。对于任意f ， 形成一个系数序列 “，( 么) n ，“，( ”) = ( 门) u 。 定义设d 是半环彳的一个收敛集，如下定义a a 7 中的收敛集 喀( 彳m ) n ，j l f 喀 当且仅当 ( i ) 对于任意f ， 序列“，d ， ( i i ) 对于每个i ， 存在有限集合，( j l l ，i ) ， 使得对于所有 ，一i ( p ，i ) 都有= 0 。 直观的讲，有限矩阵的半环a 瓜7 中的序列j l l 是收敛的充分必要条件是对于 任意i i , j i ( p ，i ) 都有j l l u 在a 中收敛，且对于任意ie ，一1 ( 1 2 ，i ) 都 有= 0 。 按照收敛集的定义可以验证d r 是( a i i ) 上的收敛集。同样可以验证映射 l i m r ：喀专a l x l ( 1 i m r ) u = l i mp , ，j 是d r 上的极限函数。 下面将a 中的离散收敛集仍转换到矩阵半环a a 。上。 a 中的离散收敛集仍可以转换到矩阵半环a “7 上。表示为( 见) r ， 且 第二章线性代数 可以验证 l i m r ：( 见) r _ a i 。i ( 1 i m r 肛) u = l i m dp u 是彳h 7 上的强收敛。 下面将半环上的相容性扩展到矩阵半环上。 一 4 瓜7 关于l i m 尺是与a a 7 相容的半模。即心忍= r i p 蕴含着 2 3 2 矩阵的分块 ( 1 i m r 地) 只= 尸。 考虑在a 中的矩阵m 。1 段设存在非空可数指标集合j ，对于每个 ，是，的一个非空可数子集，使得u 可，且对于任意 ，五，工* j 2 ， j e j 都有。nl = ，则称 l j ：j f j 是，的一个划分。 的一个划分把，分 解为两两互不相交的非空子集的并。 矩阵的定义知m ：i ，一a 是一个映射，把映射的定义域限制在i j l 乞上 得到映射m ：i j l i j ：一么，按照矩阵的定义，这是小x 如中的一个矩阵，记为 m ( ，l ) ，称之为m 的( ，t ) 块。可知如果m 么m ， 则 m 心r l j 、棼、l ， 设m l ，m 2 a a 7 ， 对于任意五，j 2 j ， 块 m 。( 。，：) ，m ：( ，乙) 彳 止， 由a 小7 ：的矩阵与么协 中的两个矩阵之积是彳”厶中的矩阵知。对于任意 ，m 。( ，) 4 j l x j9 m ：( ，t ) 么弘止， 都有m ( ，- ) m ：( ，：) 彳 “。进一步的，对于任意毛，之厶， 因为 1 7 基丁半环代数理论的有限自动机的探讨 i k m ( 。，) 鸠( ，：) j 。若m ( 。，1 ) 鸠( 1 ，：) 怕2 若；( m ) ( 鸩) , j e j ，h 。h j j j jt ij = ( m ) ( 鸩) 饨= ( m 坞) 乜， 所以，根据矩阵相等的定义得 ( m ，m ：) ( l ，l ：) - - z m 。( 。，l ) m ：i j ，l j ：) 。 因此，可以用m 。和m ：的分块矩阵的乘法计算乘积m ，m ：的相应的块， 得到m i m 2 。 对于任意 m ，( ，乇) ，m ：( 。，：) 彳 。止，f l ，之屯， 因为 ( m ( ，l ) + 鸩( l ，厶) ) ：= m ，( l 。，l ：j t j 2 4 - m ：( l ，l ：) 仙2 ( m + m z ) 仙， 所以，根据矩阵相等的定义得 ( m 。+ m ：) ( l ，：) = m 。( l ，：) + m ：( ，：) 。 因此，可以用m l 和m 2 的分块矩阵的乘法计算乘积m 1 + m ：的相应的块， 得到m + 鸩。 对于a 川。的矩阵可做类似的分块。假设j ，以及是非空可数指标集， ：) ， t ：，j ) 分别，是的划分，即i = ui , ，。= u t ，且对于 j e j，e ， 文，j 2 j ，j 、j 2 ， 奄i h n l j 。= 固，j t ，j 2 j j ，j t t ，奄i j 弋n f 蠢= 固。 考虑a “。中的矩阵m 。m 是j xi 到a 的映射，将m 限制在j i j 上，得到映射：m ：l t 专彳，由矩阵的定义知，此限制映射为彳。中的矩阵， 称之为m 的( ，t ) 块，记为m ( ，t ) 。 设m i ，m 2 4 m 。， 都按指标集合 i j ：， ， t ：，) 分块，对于任意 ie 0 ，f t ，因为 第二章线性代数 ( m 1i ，1 ) + m ：i ，) ) = m 。i ，i ，) + m ：( l ，1 ) = ( m ，+ m ：) ， 所以，由矩阵相等的定义知 ( m 。+ 鸠) ( 1 ，1 ) = m 。( l ，1 ) + m ：( ，i j ) 。 因此，可以用m 和m 2 的分块矩阵的乘法计算乘积m + 鸠的相应的块， 得到m l + m 2 。 更进一步的，若m 是半环a “7 中的矩阵，尸是如上描述的a a 7 中的半 模的矩阵，则p 是，矩阵，如果，分别具有划分 ：，) ， t ：，) ， 则对于任意工，歹j ，f i j ，i f ， 因为 ( 吾m ( ，) 尸( ，t ) l = 若( m ( 。) p ( ，t 观屯= 若薹( m ) m ( 尸) 幻 = ( m ) 油( p ) 幻= ( 脚) “， 所以，根据矩阵相等的定义得 ( 脚) ( l ，) = m ( ，) 尸( ，t ) 。 因此，可以用m 和p 的分块矩阵的乘法计算乘积脚的相应的块，得到 m p 。 设m a “7 ，如果m ( f 】，f 2 ) = o ，之，f l f 2 ，则称m 是对角矩阵。 设mc a a 7 ，如果存在，的一个划分 ：j ) ，使得m ( 1 ，乇) = o ， 应， 则称m 是一个分块对角矩阵。 2 3 3 偏序半环中的矩阵、方程和恒等式 偏序半环a 向矩阵偏序半环彳 。的扩展。 引理2 - 4 3 2 】如果么是零和自由，偏序和