《种线性有限自动机的线性τ弱逆》由会员分享，可在线阅读，更多相关《种线性有限自动机的线性τ弱逆（42页珍藏版）》请在金锄头文库上搜索。
1、广西师范大学 硕士学位论文 种线性有限自动机的线性-弱逆 姓名：郭崇泉 申请学位级别：硕士 专业：基础数学 指导教师：邓培民 20090401 I 三种线性有限自动机的线性三种线性有限自动机的线性弱逆弱逆 研究生：郭崇泉 导师：邓培民 教授 专业：基础数学 方向：代数及其应用 年级：2006 摘 要 摘 要 自动机理论是研究离散数字系统的功能、结构及两者关系的数学理论. 线性有限 自动机是自动机理论的重要组成部分.随着通信技术和网络技术的高速蓬勃发展和广 泛应用，越来越多的信息在网络上传输，信息的安全与保护问题就显得尤为重要，线 性有限自动机理论在信息的安全与保护问题中发挥着越来越重要的作用.
2、 本文讨论了戴宗铎先生等人定义的 F z 模的结构及其性质；以 F z 模为工具， 对三种线性有限自动机的线性弱逆进行研究，得到了一些较好的结果. 本文分为四个部分，四个部分中每个部分为一章. 第一章为引言.这部分简单阐述了本文的思路和主要内容，并对有限自动机的基本 概念和记号做了说明 . 第二章讨论 F z 模的结构及其性质. 第三章讨论多项式矩阵作成的 F z 模. 第四章讨论了三种线性有限自动机的线性弱逆，给出了这三种线性有限自动机 一定弱可逆的充分条件，构成它们弱逆线性有限自动机的充要条件以及弱逆 线性有限自动机自由响应模的最小维数.主要结果有： 定理 4.2.1 定理 4.2.1 设
3、 () , , lmn MFFF =(),l m n均为正整数是线性有限自动机，其结 构矩阵为, ,A B C D，其中C为()m n阶的零矩阵，简写0,CD=有左逆矩阵，则线性 有限自动机M一定延迟()0步弱可逆. 定理 4.2.2 定理 4.2.2 设 () , , n MF F F =()n为正整数是线性有限自动机， 其结构矩阵为 , ,A B C D，其中C为()1 n阶的零矩阵，简写0,CD=为F上的非零元素，给定 ()HM，那么对 () 1, s GMF z ，存在F上的线性有限自动机M，使M (),G H且M为M的一个弱逆()1的充分必要条件是 1 F zGG =. 定理 4.2
4、.3 定理 4.2.3 设 () , , n MF F F =()n为正整数是线性有限自动机， 其结构矩阵为 II , ,A B C D，其中C为()1 n阶的零矩阵，简写0,CD=有左逆元，给定()HM,那 么对 () 1, s GMF z ，(),MG H且M为M的一个弱逆()1，则M的 ()1弱逆的自由响应模G的最小F维数为. 定理 4.2.4 定理 4.2.4 设 () , , n MF F F =()n为正整数是一个线性移位寄存器， 其结构矩 阵为, ,A B C D，其中 01221 01000 00100 00001 nn A aaaaa = L L MMMMMM L L ， 1
5、 2 n b b B b = M ， () 12n Cccc=L，,1,2, ii b cF in=L ，0Dd=，dF， 则M 一定延迟()0 步弱可逆. 定理 4.2.5 定理 4.2.5 设 () , , n MF F F =()n为正整数是一个线性移位寄存器， 其结构矩 阵为, ,A B C D，其中 01000 00100 00001 00000 A = L L MMMMMM L L ， 1 2 n b b B b = M ，() 12 0 n Cccc=L， ,1,2, ii b cF in=L ，0Dd=，dF，给定()HM,那么对 () 1, s GMF z ， 存在 F 上的
6、一个线性有限自动机M ，使(),MG H且M 为 M 的一个弱逆 ()1的充分必要条件是 （1） 当0B=时，存在 () 1, ,deg, n F TMF zTTH GGGL且 1 i i + 为单模，0,1,2,in=L，所以左 Fz-模 n 的长度为1n+. （2）左 F z 模 n 的子模 i （0,1,2,1in=L）有严格降链为： 10 0 ii =L且 1 k k + 为单模，0,1,2,ki=L，所以左 F z模的 子模 i 的长度为1i+. 2.3 商环2.3 商环 SF z的自然嵌入的自然嵌入 令 SF z表示域F上的一元多项式 F z,在其质理想( )z处的局部化， 其中
7、( ) ( ) ( )( ) , 1 S f z F zf zg zF z zg z = + . 令 ( ) ( ) ( )( )( )()( )() 0, ,degdeg C f z F zaFaf zg zF zf zg z azg z = + 且，显 然它是商环 SF z的一个子环. 命题 2.3.1 命题 2.3.1 是一个对应关系： 是一个对应关系： S F zF z ( ) ( ) ( )()( ) 1f z azg zf z azg z =+ + , 0a 则是一个单映射. 证明 若 ( ) ( ) ( ) ( ) 12 12 1122 ,0 S fzfz F za a azgz
8、azgz = + 所以存在( )0 uSF zz=,使得( )( )()( )( )() 122211 0u fzazgzfzazgz+= ， 又由于 SF z是整环，0u ，因此( )( )()( )( )() 122211 0fzazgzfzazgz+=， 11 由引理 2.1.1 知，当 12 ,0a a 时，( ) 11 azgz+与( )() 22 azgz+是 F z中的单位， 所以( )()( )( )()( ) 11 111222 azgzfzazgzfz +，因此是一个映射. 若 ( ) ( ) ( ) ( ) 12 12 1122 ,0 S fzfz F za a azgz
9、azgz = + ， 则( )()( )( )()( ) 11 111222 azgzfzazgzfz +，即 ( ) ( ) ( ) ( ) 12 1122 fzfz azgzazgz + ， 所以是单射. 命题 2.3.2 命题 2.3.2 商环 SF z按照上述定义的映射可以自然的嵌入形式幂级数环 F z中，即作成它的子环. 由命题 2.3.1 和命题 2.3.2 可以得到环 CF z作成形式幂级数环 F z的一个子 环. 12 第三章 多项式矩阵生成的左第三章 多项式矩阵生成的左 F z模 模 由线性有限自动机M，可产生两个 SF z上的矩阵,G H，由G生成的 F z模称 为M的自由
10、响应模，它们都是反映出M的特征和性质.本章利用第二章中得到的关于 F z 模的结论讨论 SF z上()m n阶多项式矩阵生成的左 F z 模， 特别讨论了()1n 阶多项式矩阵生成的左 F z 模. 3.1 一些预备知识 3.1 一些预备知识 SF z的表示与2.3 中的一样，用() , s m n F z表示模 SF z上的所有()mn阶矩阵 所作成的集合. 记 m s F z为m个左 F z模 SF z的直 15 和. 定义 定义 3.1.1 域F上的一元多项式环 F z与左 F z 模 SF z上()m n阶矩阵G 之间的乘法“ ”为： 对任意的 11121 21222 12 n n m
11、mmn ggg ggg G ggg = L L MMMM L () , s m n F z，任意的( ) f zF z，有 ( ) 11121 21222 12 n n mmmn ggg ggg f z ggg L L MMMM L ( )( )( ) ( )( )( ) ( )( )( ) 11121 21222 12 n n mmmn f zgf zgf zg f zgf zgf zg f zgf zgf zg = L L MMMM L . 由商环 SF z上mn阶矩阵() 12n Gggg=L的列 1 2 , i i iji s mi g g ggF z g = M ； 1,2, ;1,
12、2,in jm=LL，在 m s F z中生成的 F z模和F子空间，分别记, F GG， 即 1 n iii i Gfg fF z = = ， 1 n iii F i Gag aF = = . 13 当()() 12 1, , n n Gg ggF z=L时，( ) degmax deg1,2, i GgzF z in=L. 3.2 主要结果 3.2 主要结果 定理 3.2.1 定理 3.2.1 对任意的G()1, n F z，degGk=，k为正整数，则 k F GG=，其 中 () 2 1, , k k Gz zz=L，即 k F GG=的F维数为1k+. 证明 首先证 k F GG，
13、因为 1 ,1,2, n iiii k i Gfg gF zfF z in = = L，又有degGk=， 所以对每个i，1,2,in=L，()0deg ii fgk或0 ii fg=， 从而 01 1 ,1,2, n k iiiiki k i fg gF zfF zaa za z aF ik = += LL， 即 k F GG 01 ,1,2, k ki aa za z aF ik=+=LL. 其次证 k F GG， 对任意的 k F G，0degpk=，由定理 2.2.3 的证明过程知， 存在 , ii p fF zgF z，deg i gp= ，1,2,inL，使得 ii fg=， 从而有 1 n ii i fg = G=，其中 0,1,2, jj fgjni=L， 因此 k F GG=，其中 () 2 1, , k k Gz zz=L. 综之， k F GG=，由于 () 2 1, , k k Gz zz=L，所以作为F空间 k F G的维数是 1k+，即 k F GG=的F维数为1k+. 定理 3.2.2 定理 3.2.2 01 kk kk F Gzbb zb z=+L，其中 () 2 1, , k k Gz zz=L， ,1,2
