（计算机软件与理论专业论文）下推自动机的半环方法.pdf

下推自动机的半环方法 中文摘要 当今自动机理论及其相关的形式语言的理论得到了高度的发展，由其衍生出的 知识也层出不穷。但经典自动机和语言理论也存在某方面的不足，特别是一些证明 从数学的角度看仍不够完美，一个典型的例子就是在自动机的理论中，自动机状态 转换的描述，仅仅是定义了状态转换，从数学运算的角度看还不够严密。本文在下 推自动机概念的基础上给出了其在半环上的定义，下推转换矩阵的引入，使下推自 动机的行为和半环代数理论上的等式建立了联系。从而使下推自动的讨论更加简洁。 首先，介绍了课题研究的对象下推自动机的概念、下推自动机的及时描述、下 推自动机所接受的语言等相关概念与半环、半模、收敛等概念。并重点讨论了偏序 半环和关于偏序半环上等式的一些性质。最后说明了课题实现的具体目标和意义。 接着，引入了与语言理论密切相关的形式幂级数的概念，并将半环的概念转换 到形式幂级数，同时在引入矩阵概念的基础上也将半环的概念转移到矩阵，重点证 明了布尔形式幂级数矩阵半环和形式幂级数布尔矩阵半环的子半环同构，进一步结 合形式幂级数布尔矩阵半环和分块矩阵的相关理论给出了：与矩阵星运算求解相关 的线性系统，并证明了线性系统与矩阵星运算相关的一些定理。 最后，提出了语言半环的概念，证明了它和布尔形式幂级数半环是同构的。在 语言半环到语言矩阵半环扩展的基础上定义了下推转移矩阵，进而定义了下推自动 机和下推自动机行为。特别是下推转换矩阵的引入，通过一系列矩阵半环同构将下 推自动机行为的研究转移到布尔形式幂级数矩阵半环上，最终使下推自动机的计算 转变为矩阵半环上下推转换矩阵的乘法和加法运算。 关键词：半环；线性代数；下推自动机；形式语言 t h es e m i r i n g sm e t h o d f o rp u s h d o w na u t o m a t a g r a d u a t en a m e ：y o n g ju nm a 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 a u t o m a t at h e o r ya n dt h ec l o s e l yr e l a t e dt h e o r yo ff o r m a ll a n g u a g e s f o r mn o w a d a y ss u c hh i g h l yd e v e l o p e da n dd i v e r s i f i e db o d yo fk n o w l e d g e c u s t o m a r ye x p o s i t i o n s o fa u t o m a t aa n d l a n g u a g et h e o r y a r eo f t e n u n s a t i s f a c t o r yi nt h es e n s et h a te n t i r e l yd i f f e r e n ta dh o cp r o o f sa r eg i v e ni n v e r ys i m i l a rs i t u a t i o n s ；m o r e o v e r , m a n yo fp r o o f ss t i l lr e m a i ni n a d e q u a t e f r o mt h em a t h e m a t i c a lp o i n to fv i e w at y p i c a le x a m p l eo ft h el a t t e rs t a t eo f a f f a i r si st h a to n ed e f i n e sac e r t a i nc o n s t r u c t i o na n dt h e ns i m p l yc l a i m s w i t h o u t p r o o ft h a tt h e c o n s t r u c t i o nw o r k sa si n t e n d e d t h ep u s h d o w n a u t o m a t aa r ei n t r o d u c e db yu s i n gt h em e t h o do fs e m i r i n g sa n dt h et o o l s f r o ml i n e a ra l g e b r a ，t h a tb u l i dt h ec o n n e c t i o nb e t w e e ns e m i r i n g sa l g e b r a i c s y s t e m so fe q u a t i o n s a n dt h ea u t o m a t a t h i sm a k e st h ed i s c u s s i o no f p u s h d o w n a u t o m a t am o r es i m p l y f i r s t g i v e s a ni n t r o d u c t i o nt or e s e a r c h o b j e c t s w h i c h i n c u l d i n g p u s h d o w na u t o m a t aa n ds e m i r i n g sa n dp r o v i d e sab a c k g r o u n da n dam o t i v e f o ro u rs t u d y t h e nd i s c u s s e st h ec o n c e p to ff o r m a lp o w e rs e r i e s ，a n dc o n v e r tt h e c o n c e p to fs e m i r i n g st of o r m a lp o w e rs e r i e s t h e nt r a n s f e r ss e m i r i n g si n t o m a t r i xi nt h ef o u n d a t i o nfo ft h ec o n c e p to f m a t r i x f i n a l l yg i v e st h el i n e a r s y s t e mt h a tr e l a t e ss o l u t i o no f m a t r i xs t a r l a t e r p r o o f sl a n g u a g es e m i r i n g sa n db o o l e a nf o r m a lp o w e rs e r i e s s e m i r i n g sa r ei s o m o r p h i c o nt h eb a s i so ft r a n s f e r i n gl a n g u a g es e m i r i n g s i i i s e m i r i n g si n t ol a n g u a g em a t r i xs e m r i n g sd e f i n e st h ep u s h d o w nt r a n s i t i o n m a t r i xt h e nd e f i n ep u s h d o w na u t o m a t aa n dt h eb e h a v i o ro ft h ep u s h d o w n a u t o m a t ai nm a t r i xs e m m n g s k e yw 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 ；p u s h d o w na u t o m a t a ；f o r m a ll a n g u a g e 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：壹夏至 日期： 、力口气每s 鞫| 穹8 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：应应至： 日期： 兰! ! z 量翌! 呈璺 导师签名日期i 第一章引言 第一章引言 1 1 选题背景和国内外研究现状 1 1 1 下推自动机理论 有穷自动机识别正则语言，下推自动机识别上下文无关语言。众所周知，对于 任意的上下文无关文法c f g = ( v ，t ，p ，s ) ，( 其中y 是中间变量的非空有穷集，丁 是终结符的非空有穷集，尸是产生式的非空有穷集，s t 是开始符号。) ，都存 在与其等价的g n f ( g r e i b a c hn o r m a lf o r m ) ( 即文法中所有的产生式形如么j 缎， 其中a v ，口t ，a v ) 。这样通过实施最左派生，可以保证句型中的中间变 量构成的子串作为句型的后缀出现。由于后缀的长度是不定的，所以要想用有穷个 状态来表示表示这些后缀不一定总是可行的，但是注意到中间变量的种类是有限 的，这时按照最左派生来考虑句子的分析，就可以用一个栈来存放这个后缀，因为 要最先分析最左边的变量，所以放在栈的顶部，而最右边的变量最后分析，所以放 在栈的底部。按照这样的思路，可以设计出如图1 1 所示的识别模型： 图l 一1 下推自动机的物理模型 f i g 1 - 1p h y s i c a lm o d e lo f p u s h d o w na u t o m a t a 从图1 - 1 口1 可以看出，识别c f l 的模型有3 个基本结构：存放输入符号串的输入带、 存放文法符号的栈、有穷状态控制器( 殿c ) 。模型在有穷状态控制器的控制下根据 控制器的当前状态、栈顶符号以及输入符号作出相应的动作。有时不需要考虑输入 符号。一般将该模型的动作分成两类： ( 1 ) 根据有穷状态控制器的当前状态、栈顶符号以及当前的输入符号选择动作： 将状态改变为新的状态：修改栈顶有新的语法符号串代替当前的栈顶符号；向 右移动读头，使读头指向下一个输入符号。 卜推自动机的半环方法 ( 2 ) 根据有穷状态控制器的当前状态、栈项符号选择动作：将状态改变为新 的状态；修改栈顶用新的语法符号串代替当前的栈顶符号。这种动作( 1 ) 类 似，只是不移动读头，也称作读头的一次空移动( 占移动) 。 下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个 长度不受限制的存储栈；下推自动机的状态转变不但要参考状态部分，也要参照栈 顶符号；转移不但包括状态的转变，还包括栈的出栈或入栈过程。 下推自动机的定义：下推自动机口3p 是一个七元组p = ( q ，f ，6 ，q 。，z o ，f ) ， 其中 ( 1 ) q 是状态的非空有穷集合。v q q ，称q 为p 的状态。 ( 2 ) 是有穷字母表，要求p的输入字符串都是上的字符串。常用字 母表中比较靠前的小写字母表示输入符号，靠后的小写字母表示输入符号串。 ( 3 ) f 是有穷栈符号表，v a f ，把彳叫做栈符号。常用大写的英文字母 表示栈符号，而用希腊字母表示栈符号串。 ( 4 ) 6 是状态转移函数或者移动函数，6 ：q u ) x f 专f p ( q x f ) ，其中 f p ( o f 1 是o x f 的所有有穷子集的集合。 f i ( q ，a ，z ) = ( g 。，) ，。) ，( g ：，y ：) ，( g 。，y 。) 表示p 在状态为珂，栈顶符号为z ，读入符号为a 的情况下，状态变 为g ，其中f = 1 ，2 ，m 并将栈顶符号z 弹出，将y ，中的符号从右到左 依次压入栈，然后读头向右移指向输入字符串的下一个字符。r 是r 的 克林闭包：r = f ou r uf 2uf 3u ，这里f o = s 。 ( 5 ) g 。称作p 的初始状态且q o q 。 ( 6 ) z n 称作栈底符号且z o f ，它是p 启动时栈内唯一的一个符号。 ( 7 ) f 是p 的终态集且f q 。 为了后面的叙述和理解方便，如下约定使用符号：英文字母表较为前面的小写 字母，如a , b ，c 等表示输入符号；英文字母表较为后面的小写字母，如x , y , z 等表 示输入字符串；英文字母表的大写字母表示栈符号；希腊字母a ，卢，y 等表示栈符 号串。 移动函数的计算定义1 ： 对于任何p d am = ( q ，f ，6 ，吼，z o ，f ) ，计算路径是一个关于3 元组的序列： ( q l0 1 ，q ) ( 9 2 ，仅2 ，哆) ( g 。，a 。，( - o n ) ，q ，q ，哆，仗，r + ，n 0 ， 满足如下条件： 2 第一章引言 ( i ) ( g 川，a 川) 6 ( g ，a ，口，) 对于i = 1 ，2 ，n - 1 ，这里的q u 且w “ 是w 的后缀。 ( i i ) 3 a o ，a l ，a 2 ，a 3 , - - , a 。使得a ，= 4 + i p f ，a ，+ 1 = y ，+ 1 卢，卢，r 。 结合上面两点，表示自动机p 在状态吼，栈顶符号为4 “，读入字符为 哆，将状态变成仍+ l ，并将栈项符号4 q 弹出，将a ，q 中的符号从右向左依 次压入栈，然后再读取输入字符串的下一个字符。从上面的定义看，p d a 在计算 过程中任何一点上都面对着多种可能性：状态是否发生变化，从栈顶读一个符号 并把它替代为另一个符号串，从栈顶读一个符号并删除它而不替换，所有这些用 等式来表示为：a ，= 4 + 。尼和a = y p ，。a ，是紧接在第i + 1 次移动之前的 栈内容，而4 + 。是要从栈顶弹出的符号。a 川是紧接在第i + 1 次转移移动之后 栈内容，而y 川是在第i + 1 次移动期间要增加压入栈的符号串。再结合状态髟 r 一 和q ，的变化来来支配：如果4 + 。o 而y o ， q l + 1 _ | ! 。则p d a 从栈读一 l q , + l q 个符号并把它替代为另一个符号串，上者状态不变，下则反之。如果- 4 + 。0 而 y i + i ：0 ， g m2 吼则p d a 从栈读一个符号并删除它而不替换，上者状态不变， 【毋+ 1 9 7 下则反之。注意当n = o 时，计算路径就是单元素集合( 吼，乙，) 。 移动函数的计算定义2 ： 对于任何输入w = a o a l 口2 a 3 o m , 肌0 ，p 接受w ，如果存在计算路径 使得： ( ，磊，w o ) ( q 。，a 。z 0 ，) ( g ：，a ：z o ，) ( ，a 。z o ，) ， ( 1 ) 以( g o ，z o ，w ) 开始到结束的三元组属于f x f + x e ) ，则称运算是成功的， 字w 如果它的运算是成功的，则称字w 被自动机p 识别。被自动机p 用 终态接受的语言定义为： 丁( p ) = 卜，w ，z o ) j ( s ，卢) ，q ，f ) ； 3 下推自动机的半环方法 ( 2 ) 以( g 。，z o ，w ) 开始，到结束的三元组属于q s s ) ，则称运算是成 功的，一个字w + 如果它的运算是成功的，则称字w 被p 识别。被p 用 空栈接受的定义为： ( p ) = w + ，w ，z o ) j ( 彬，s ) ) ( 3 ) 以( 吼，z o ，) 开始，到结束的三元组属于f x s ) s ，则称运算是成 功的，字w + 如果它的运算是成功的，则称字w 被p 识别。被自动机p 用 空栈接受和终态共同接收的语言定义为： 三( p ) = w + i ( g o ，w ，z 。) j ( 阶叩) ，q f f 。 即时描述n 3 ：三元组( g ，w ，y ) ( q ，f ) 也称为p 的即时描述，结合关系合 成的意义：( q l ，卢。) 山( 吼，卢。) ，表示p从( q l ，屈) 出发，利用n - 1 次 移动函数变成( 吼，心，卢。) 。即存在即时描述序列： ( g 。，w 1 ，屈) ，( q 2w 2 ，殷) ，( 吼，卢。) ， 满足： ( g 。，w l ，卢。) 专( q 2 ，卢：) 专一( 吼，卢。) 。 ( g ，w ，仅) j ( p ，x ，p ) 表示p 从( 鸟，w ，仅) ，经过”0 移动函数变成 ( p ，x ，卢) ( g ，w ，a ) j ( p ，x ，卢) ，表示p 从( g ，w ，a ) ，经过胛1 移动函数变成 ( p ，x ，p ) 。 可以看到上面自动机理论对自动机状态转换的描述，是利用状态转换函数来定 义的，状态间的转换没有与数学运算建立起足够的联系。而下推自动机的半环方法 就能很好的解决这个问题。 1 1 3 国内外研究现状 下推自动机的理论在计算机高级语言相关的句法分析，文法推断；模式识别领 域的广泛的应用；生物学相关的细胞下推自动机；d n a 分子计算，量子计算方面； 智能仿真等等方面都取得了丰硕的成果。半环代数理论是较为活跃的代数学研究领 域之一，在半环半模畴模，半环的星结构，半环在矩阵代数以及同构等研究领域中 也取得了丰硕的成果下推自动机的移动函数等相关介绍参考了文献 3 到 7 ，形式 幂级数的相关讨论参考了文献 8 到 1 2 ，半环的相关讨论参考了文献 1 3 到 1 5 ， 半环向形式幂级数和矩阵上的转移参考了文献 1 6 。国外利用形式幂级数半环对形 4 第一章引言 式语言和自动机的研究成果可见参考文献 1 7 到 2 6 。而国内对半环的研究成果大 多是在数学理论方面，而与自动机结合进行研究的成果却比较罕见。本文正是在半 环和下推自动机理论的基础上，提出了半环下推自动机。其中下推转换矩阵的引入 主要参考了文献 1 6 以及 2 7 到 3 6 3 。 1 2 本文的主要研究内容 传统下推自动机状态转换的描述，仅仅是利用转移函数定义了状态间转换，从 数学运算的角度看还不够严密。本文在半环代数理论的基础上讨论了下推自动机， 给出了其在半环上的定义，将转移函数改为下推转换矩阵，从而使下推自动机的运 算转换为矩阵半环代数理论上的下推转移矩阵的乘法和加法运算，也就是使下推自 动机的计算更符合数学的角度。 首先证明了布尔形式幂级数矩阵半环和形式幂级数布尔矩阵半环的子半环同 构，进一步结合形式幂级数布尔矩阵半环和分块矩阵的相关理论给出了：与矩阵星 运算求解相关的线性系统，并证明了线性系统与矩阵星运算相关的一些定理。 接着提出了语言半环的概念，证明了语言半环和布尔形式幂级数半环的同构。 在语言半环到语言矩阵半环转换的基础上定义了下推转移矩阵，最终定义了下推自 动机和下推自动机行为。通过语言半环和布尔形式幂级数半环的同构将下推自动机 行为的研究转移到布尔形式幂级数矩阵半环上，证明了下推转换矩阵星的存在性， 并将下推转换矩阵星的求解和半环代数理论上的线性系统建立了联系。 1 3 研究下推自动机半环方法的目的和意义 传统的自动机和语言理论存在某方面的不足，特别是一些证明从数学的角度看 仍不够完美，一个典型的例子就是在自动机的经典理论中，自动机状态转换的描述， 仅仅是定义了状态间转换，而没有与数学运算建立足够的联系。本文在半环代数理 论的基础上讨论了下推自动机，给出了其在半环上的定义，主要是将转移函数改为 下推转换矩阵，从而使下推自动机的行为和矩阵半环代数理论上的线性系统建立了 联系，从而使下推自动机的计算更符合数学角度。 1 4 本论文的组织结构如下 第二章先是介绍了半环的相关概念以及与语言理论密切相关的形式幂级数的概 念，并将半环的概念转换到形式幂级数上，同时给出了矩阵的概念也将半环的理论 转移到矩阵上，并在矩阵半环的基础上给出了下推转移矩阵星运算求解相关的 线性系统以及线性系统的相关定理。 s 卜推自动机的半环方法 第三章在语言半环的基础上给出了半环下推自动机和半环下推自动机行为的概 念，特别是下推转换矩阵的引入，结合前面结论通过半环同构将下推自动机的研究 通过同构转移到布尔形式幂级数矩阵半环上来，从而使使下推自动机的行为和半环 代数理论上的等式建立了联系，使下推自动机的计算更符合数学的角度。 第四章作为结束语，对论文所做的工作进行了总结，并对下一步的工作进行了展 望 6 第二章形式幂级数和矩阵半环 第二章形式幂级数和矩阵半环 2 1 半环理论 2 1 1 幺半群 幺半群m 是一个三元组满足：集合m ， ( 1 ) m 上满足结合律的二元运算， ( 2 ) 恒等元( 或单位元) 为l ，对于任意的口m 都有口1 = 1 口= l t l 。二元 运算也叫作乘法，通常省略，如口b 记为a b 。幺半群m 记为( m ，1 ) ， 如果乘法运算和单位元明显也简记作m 。 交换幺半群m ：对任意口，b m ，都有口o b = b 口。 如果m 。c m ，且( m ，+ ，0 ) 是幺半群，则称( m ，+ ，0 ) 是幺半群m 的子 幺半群。 幺半群m 到幺半群m 的同态：映射h ：m m 满足： ( 1 ) 保持单位元：h ( 1 肼) = 1 肼， ( 2 ) 保持乘法运算：h ( 铂m 2 ) = h ( m 。) 办( 朋2 ) ，( v ，m 2 m ) 。 2 1 2 半环 半环：集合么两个二元运算+ ，两个恒等元( 即单位元) 0 ，1 满足下 列的条件： ( 1 ) ( 么，+ ，0 ) 是交换幺半群， ( 2 ) ( 么，1 ) 是幺半群， ( 3 ) 适合左右分配律： v a ，b ，c 4 ，口( b + c ) = 口o b + 口c ，( 口+ 6 ) c = 口c + 6 c ， ( 4 ) v a 彳，0 - 以= a 0 = 0 ，0 也称作乘法的零元。 半环记作：( 彳，+ ，0 ，1 ) 如果该半环中的运算和单位元都很明显，也简记为a 。 交换半环彳：v a ，b aa b = b a 。 如果彳彳，且( 彳，+ ，0 ，1 ) 是半坏，则称( 彳，+ ，0 ，1 ) 是半环4 的子半 环。 几类特殊的半环：半环彳称作偏序半环，当且仅当对任意的口，q ，呸么， 符合： ( 】)a 0 。 7 下推自动机的半环方法 ( 2 ) q a 2 蕴含a + a l 毋+ a ， ( 3 ) a l a 2 蕴含a l a a 2 a 和a a l a a 2 。 半环彳称作幂等半环，当且仅当1 + 1 = 1 。 半环加上减法运算就是带单位元的环，也说明带单位元的环一定是半环。自然 数集关于加法和乘法构成半环。在语言理论中，布尔半环是一类重要的半环， b = o ，1 ) ，o 是加法运算的恒等元，1 是乘法运算的恒等元。设任意的口，b ，c 1 8 8 由0 是加法运算的恒等元可知，若日，b ，c中有一个为0 ，自然有 ( 口+ 6 ) + c = 口+ ( 6 + c ) ，当三个都是l ，因为1 + 1 = 1 所以也有( 口+ 6 ) + c = a + f f + c ) ， 因此( 璐，+ ，0 ) 是幺半群，又因为加法运算适合交换律，因此( 1 8 8 ，+ ，0 ) 是交换幺半 群。由1 是加法运算的恒等元可知，若口，b ，c中有一个为1 ，自然有 ( a b ) c = a ( b c ) ，当三个都是0 时，因为0 0 0 = 0 ，所以也有( 口6 ) c = a ( b c ) ，因此 ( 1 8 8 ，1 ) 是幺半群。由乘法运算可以看出。是乘法的零元。当口= 0 时， a ( b + c 1 = a b + 韶= 0 ；由l 是乘法运算的恒等元可知，当 a = 1 时 a ( b + c ) = a b + a c = 6 + c ，同理可证( b + c ) a = b a + c a 。总之可得，乘法对加法适 合左右分配律。综上所述，( b ，+ ，o ，1 ) 是半环。特别地可以验证布尔半环既是偏 序半环也是幂等半环。 半环么到半环4 。的同态是一个映射h ：a a ，此映射满足： ( 1 ) 保持单位元：h ( o ) = 0 ，h ( 1 ) = 1 ，其中0 ，1 是半环a 的单位元，0 ， 1 是半环么。的单位元， ( 2 ) 保持加法和乘法运算：h ( a l + a 2 ) = h ( a 。) + 办( 口：) h ( a l a 2 ) = h ( a 。) z ( 口：) ， 其中a l ，0 2 是彳中的任意元。 双射的幺半群同态( 或者半环) 同态称作幺半群同构( 半环同构) 。 彳半模：半环么交换幺半群 ( 矿，+ ，0 ) 运算a v a 的算子表示为 对v a ，b a ，v v ，w v满足 ( 1 ) ( a b ) e v = ao ( b y ) ， ( 2 ) ( 口+ 6 ) v = a v + b v ，a ( v + w ) = a e v + a e w ， ( 3 ) 1 v = ，1 = v 0 v = v 0 = 0 ， ( 4 ) 0 a = a 0 = 0 ， 就称y 是彳半模。 由上面的定义可以验证半环彳是么半模。 序列收敛：同上设么是半环，称映射a ：nja 为a 上的序列。把彳上 8 第一二章形式幂级数和矩阵半环 所有序列组成的集记为a 。& a ，记做口= ( a ( 刀) ) ，刀0 。 零序列。定义为：对所有，? 0 ，都有o ( n 1 = 0 。 单位序列7 7 定义为：对所有胛0 ，都有叩( ，2 ) = l 。 a ，a l ，a 2 a n , c a ，序列a c 定义为：对所有刀0 ，都有( a c ) ( ”) = a ( 胛) c ， 同理序列c a 定义为：对所有玎0 ，都有( c a ) ( n ) = 伽( ，z ) 。 序列的加法：对所有刀0 ，都有( 口+ 口：) ( ，z ) = 口。( 胛) + a ：( n ) 。 序列的乘法：对所有刀0 ，都有( a l a ：) ( 胛) = a 。( 力) a ：( 甩) 。 由上面的定义可以看出么1 中的加法和乘法都是对应分量在半环彳上的计 算，从而半环a 可以扩展到序列半环( 么。，+ ，0 ，叼) 。 设d a ，如果d 满足下面的条件( d 1 ) 一( d 3 ) ，则称d 是么中的一个 收敛集： ( d 1 ) 7 7 d ， ( d 2 1 ) 如果a l ，a 2 d ，那么a l + a 2 d ， ( d 2 2 ) 女口果a d ，c a ，习b 么c 口d ，a c d ， ( d 3 ) 如果a d ，c a ，勇墨么口。d 。 设d 是彳上的一个收敛集，l i m ：d 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 m 2 ) 如果a l ，a 2 d ，那么l i m ( a i + 口2 ) = l i m a l + l i m a 2 ， 女口果a d ，c a ，另b 么l i m ( c a ) = c l i m a ，l i m ( a c ) = l i m ( a ) c ， ( 1 i m 3 ) 女口果a 仨d ，c a ，另巧么l i m ( a 。) = l i m a 。 因为收敛序列必有极限，所以l i m a 也经常表示为l i m a ( ”) 。 最小收敛集：岛= a 彳1 v3 n 。o ， o k o ，a ( + 尼) = 0 ( ) ，见上的极限 函数：l i m d ：见专a ，也就有l i m j ( a ) = 口( ) 。也称见为离散收敛集，1 i m d 为 离散收敛函数。 半环元素的幂：设口是半环彳中的元素，定义a o = l ， - 7 1 ，a ”= c l a ”1 。 准逆与星：设d 是a 的一个收敛集，口么，如果( 口，) d ，则称 百 li。ra。口7为口的准逆，记为d+。如果(口7)d11，则称舰口7 为口星，一。：月 。= ，= l，= u，= u 9 下推自动机的半环方法 记为口。 因为布尔半环中的元素无限和是有极限的，结合上面的定义可知布尔半环中所 有元素的星存在且为：对所有刀0 ，都有0 = 1 = l = r ( n ) ，即0 + = r = 1 。 ，= o j = 0 半模与半环的相容性：设4 是半环，矿是4 半模，同彳半环的序列一 致，称映射a ：n v 为矿中的序列。把矿中所有序列组成的集记为y l v ，且 如果a a ，v v ，a v v ，d 是么上的收敛序列集，l i r a 是d 上的一 个极限函数。如果a ，p = q r ，这里a ，d ，v ，v 蕴含( 1 i m a ，) v = v 则 ，= lt = l 称4 半模y 与彳相容。这是因为： ( t i m a ，) ，= l i m ( c ，v ，) = l i m e ( a ，v ，) = l i m r v = v 。 l = l，= l j = l 半环中的方程1 6 3 ：设么是半环，d 是么上的收敛集合，d 上的极限函数 为l i m ，口，( 2 1 ，( 1 2 ，a 3 ，a 。a ，方程y = a y + 6 ，y 是变量b v ，a 半模y 关于 l i m 与彳相容，方程的解j 称作极小解，当且仅当对方程的所有解f ，都有 5 。 定理1 若4 半环是偏序半环，则上面的方程有唯一的极小解a b 。 定理2 若a 半环是偏序半环，q ，以：么若彳，( 口：以：) ，( q + 呸) + 存在，则 ( q + 哆) = ( 口：呸) 。彳= 西( 呸口i ) 。 定理3 若么半环是偏序半环，如果订4 ，口+ 和( a 2 ) + 存在，则 ( 口2 ) + ( 1 + 口) = 口。 定理4 若彳半环是偏序半环，q ，口：么如果( q - 4 = a 2 ) + ，彳，( q + d ：彳口：) + ， ( 口：a ：) ，( ( 口：口：) 2 ) + 存在，那么 ( 口，+ 呸) = ( q + 哆彳口) ( 1 + 订：彳) + 。 1 0 第二章形式幂级数和矩阵半环 2 2 形式幂级数半环 为一个非空有穷集合，也称作字母表，称中的元素为字母或符号。一 般情况指为有限集。设。，：是两个字母表，与：字母表的乘积： 。：= a b a 。，b ：) 。 的疗次幂定义为： ( 1 ) o = s ， ( 2 ) ”= ”1 ， 力1 ， 其中s 是由中的0 个字符组成，称作空字。的正闭包： + = u 2u 3u 。 的克林闭包： = ou 1u 2u 。 由上面的定义可知+ 和它的乘法构成了幺半群，也称作自由幺半群。先约定非空 集合么，么可以是幺半群、半环、半模，通常是半环。 2 2 1 形式幂级数 形式幂级数是一个映射： ，：+ 一彳，在w + 处的值记为( 厂，w ) ，也把 ( ，w ) 称为，的系数。映射，记为：，= ( ，w ) w ，称，为变量在中的形 式幂级数。所有形式幂级数的集合记为彳( ( ) ) 。 形式幂级数的支撑：，彳( ( ) ) ，称 w i ( ，w ) 0 为，的支撑，记为 s u p p ( r ) 。把具有有限支撑的所有幂级数组成的集合记为彳 ，称具有有限支 撑的幂级数为多项式。 零多项式： v w + ，( o ，w ) = 0 ，支撑集为。 克洛奈克多项式： v w , w + ，( w ，w 7 ) = ：，w w ，- - w w ，支撑集为 w ) 。 2 2 2 半环向形式幂级数半环的转换 若厂彳( ( ) ) ，w 则( ，w ) 么依据它就可以由a 半环向彳( ( + ) ) 下推自动机的半环方法 半环进行转换： 设任意口彳，彳( ( ) ) ，w + ，引入形式幂级数的如 下运算：彳( ( ) ) 中的加法： ( _ + r 2 ，w ) = ( 1 ，w ) 4 - ( r 24 - w ) ， 因( ( ，w ) + ( 眨+ w ) ) 4 则由w 的任意性可知 + 吃爿( ( + ) ) 。因而： ( o + r ，w ) = ( o ，w ) + ( 尸，w ) = 0 + ( r ，w ) = ( r ，w ) ， 即o + 尸= r 同理r + 0 = ，也就说明0 是加法的恒等元。结合律的验证： ( ( + 眨) + 吩，w ) = ( _ + r 2 ，w ) + ( 吩，w ) = ( ，w ) + ( 眨，w ) + ( 吩，w ) = ( ，w ) + ( r 2 - 4 - r 3 ，w ) = ( + ( 吃+ 巧) ，w ) 综之说明( 么( ( ) ) ，+ ，o ) 是加法幺半群，且如果彳是交换幺半群，则彳( ( ) ) 也是交换幺半群。彳( ( ) ) 中乘法： ( ，；恐，w ) = 1 2 ( ，) ( 吒，心) ， w 。1 4 w 2 根据半环 彳中乘法和加法的封闭性可知 1 2 ( ，w 1 ) ( 吃，心) a ，则 w m w l w 2 彳( ( + ) ) 。结合律的验证： ( ( 巧吃) 巧，w ) = ( 巧吃，w i ：) ( 吩，比) = 【瓴，m ) ( 吃，) 】( 为，) 1 4 m w l 2 w - tw 2 ”1 2 ”，h 22 w 1 w 2 = ( 娥，w 1 ) ( 砭，) ) ( 吩，) w 2 h2 w 3w 1 2 2w l w 2 = ( ，i w ) ( 吃w 2 ) ( 吃w 3 ) w = w i w 2 w 3 同理可得： ( ( 眨玛) ，w ) - - 1 2 ( _ ) ( 眨w 2 ) ( 吩比) w = w 1 w 3 从而结合律满足。又因为： ( 厂s ，w ) = ( 厂，w 1 ) ( s ，心) = ( ，w ) ( s ，s ) = ( ，w ) w f f i w l w 2 1 2 第二章形式幂级数和矩阵半环 即陀= ，同理可证s ，= ，从而说明g 是乘法的单位元。 综上( 彳( ( ) ) ，s ) 是幺半群。乘法对加法的左右分配律： f i r , + 匕) 吩，w ) = f i r , + 乞) 嵋) ( 吩w 2 ) = ( 吒w l + 吃w 1 ) ( 玛) = ( 嵋吩心+ r 2 w l r 3 w 2 ) = ，；弓+ r 2 w l r 3 w 2 = ( r , r 3 w ) + ( r 2 r 3 w ) w 2 ”i ”2w l w 2 = ( ( 吩+ 眨吩) ，w ) 同理可证( 吩( + ，2 ) ，”= ( ( 吩，i + r 3 r 2 ) ，w ) 从而说明分配律满足。零元的验证： ( o ，们= ( o ，w 1 ) ( ，w 2 ) = o ， w 。w i w 2 ( r o ，w ) = ( ，w 1 ) ( o ，w 2 ) = o w 2 w i w 2 综上所述，( 4 ( ( ) ) ，+ ，o ，s ) 是一个半环结构。同理若矿是彳半模，则 矿( ( ) ) 是彳( ( + ) ) 半模。 偏序半环4 到么( ( + ) ) 的转移，j ，吃么( ( ) ) ，吒 o 从而有： r = u f ，c = u f 。 有了上面的定义就可以得到v ( z 1 关于语言的运算实则构成了p ( z ) 半 环。下面来验证( p ( + ) ，u ， s ) ) 是半环。 证明：按照半环的定义逐一验证： ( p ( z ) ，u ，) 是交换幺半群，因为并运算满足结合律和交换律，且并的零元是空集。 ( p ( z ) ， s ) ) 是幺半群，乘法运算满足结合律，且乘法的零元是空字集。 乘法对并的左右分配律：设任意的厶，厶，l 3 p ( + ) 根据并和乘法的定义可得： 厶( 上：u 厶 ) = 厶厶u 厶厶，( 厶u 厶) 厶= 厶厶u 厶厶， 对于任意的l p ( z 4 ) ，都有： l = l = ， 故综上所述，( p ( z + ) ，u ， s ) ) 是半环，简记为p ( + ) 。 2 7 下推自动机的半环方法 3 _ 2 语言半环和布尔形式幂级数半环的关系 ( p ( + ) ，u ，$ ， ) ) 和( b ( ( ) ) ，+ ，o ，s ) 这两个半环同构。 证明：设映射： c h a r ：p ( z ) 一b ( ( + ) ) ， 对任意的l p ( z + ) 映射也表示为l c h a r ( l ) ，其中c h a r ( l ) 也称作特征函 数，它表示为： ( c h a r ( l 胁诧是 则 砌( ) = 0 ，砌( ) ) = s ， 即说明映射保持恒等元。对于任意的厶，厶p ( ) ，都有： c h a r ( z ，u 乞) = c h a r ( 厶) + c h a r ( l 2 ) ，c h a r ( 厶l z ) = c h a r ( 1 1 ) c h a r ( l 2 ) ， 即w 厶u 厶时，可知( c h a r ( hu 厶) ，- , ) - - 1 ，也进一步表明( c h a r ( l 1 ) ，w ) = 1 或 者( c h a r ( l 2 ) ，w ) = 1 ，由布尔运算可知： ( c h a r ( l 2 ) ，w ) + ( 是甜( 厶) ，w ) = 1 ， 当w 诺厶u 厶时，可知 ( c h a r ( l lu 厶) ，w ) = o ， g 进- - n - n n ( c h a r ( 厶) ，w ) = o 且( c h a r ( z z ) ，w ) = o ，有： ( c h a r ( l 2 ) ，w ) + ( c 办甜( 厶) ，w ) = 0 ， 从而说明p ( z + ) 中的并与b ( ( ) ) 中的加保持一致。当w = w ，w 2 时，其中 厶，心厶，( c h a r ( 厶厶) ，w ) = 1 ，说明( c h a r ( 1 1 ) ，w 1 ) = 1 且( c h a r ( l ：) ，) = 1 ， 从而有： ( c h a r ( l 2 ) ，w 2 ) ( c h a r ( i - q ) ，w 1 ) = 1 ， 当w w 2 时，说明( c h a r ( l ) ，) = o 或( c h a r ( l 2 ) ，w 2 ) = o ，从而有 ( c h a r ( l 2 ) ，w 2 ) ( c h a r ( i n ) ，) = o ， 说明p ( z ) 中的乘法和b ( ( ) ) 中的乘法保持一致。 c h a r ( l ) 的逆映射为： 第三章下推自动机的半环方法 s u p p ( c 乃秽( ) ) = ( w p ( ) l ( c h a r ( l ) ，w ) = 1 ) ， 即表明该映射为双射。综上所述可知这两个半环同构，这样利用同构对语言的研究 就可以转到形式幂级数b ( ( + ) ) 半环。 3 3 下推自动机的半环方法 结合第2 章的内容，设半环a 代表的半环就是p ( + ) 半环，设j ，是 两个非空的可数指标集，称映射m ：，p ( e ) 为矩阵，把( f ，i ) 在m 下的 像记为哆，p ( ) ，称为矩阵的元素。i xi 映射到p ( + ) 的所有矩阵的集合 记为： p ( + ) 以7 ，设m ，鸠p ( ) h 。矩阵的和运算： ( m + m z ) f ，= ( m ，u ( m t ， 即矩阵的和是两个矩阵对应元素在尹( ) 中的并运算。在介绍矩阵的乘法运 算之前，也是先给出行有限矩阵和列有限矩阵以及行列有限矩阵的概念：对于任意 的涎几如果集合r ( f ) 2 川m 0 弩芊有限哆，则称该矩阵m 为行有限矩 阵