自动机理论是研究离散型数字系统的功能、结构及两者关系的数学理论,是对许多具体的离散数字系统的抽象;自动机理论是在开关网络理论和数理逻辑中图灵机理论的基础上发展起来的一门学科.概率有限自动机是自动机理论的一个分支,与非概率有限自动机不同之处是概率有限自动机的动作是随机的.概率有限自动机的主要研究内容与一般的自动机理论相平行,有概率图灵机、概率时序机、概率识别器等方面的研究工作.这些工作一方面是推广自动机已有的结果;另一方面也提出不少新的问题,丰富了自动机理论的内容.本文从代数的角度考虑,讨论概率有限自动机的代数结构问题,讨论了概率有限自动机的商自动机与概率有限自动机同态之间的关系,证明了同态分解定理,得到了一种概率有限自动机的分解;深入探讨了它们几种积之间的相互关系.本文分为五个部分,前面四个部分中每一个部分为一章,最后部分为结束语.第一章为引言.这部分简单介绍了概率有限自动机和确定有限自动机的基本情况.阐述了本文的思路,另外,对本文的基本概念和记号也做了介绍.第二章讨论了概率有限自动机的商自动机和概率有限自动机同态之间的关系,主要的结果有:命题2.1.4若M =< X , Q , Y ,P>是匀概率有限自动机, M是既约的当且仅当Q≤2.定理2.2.1设M =< X , Q , Y ,P>是概率有限自动机,π 1 ,π 2是M的有效划分,且π 1≤π₂,则定理2.2.6设M =< X , Q , Y ,P>是概率有限自动机,则在概率有限自动机同构的意义下M的商概率有限自动机和与M同态的概率有限自动机一一对应.定理2.2.7 （概率有限自动机的同态分解定理）设M₁ =< X , Q₁ , Y ,P1>, M₂ =< X , Q2 , Y ,P2>, M 3 =< X , Q₃ , Y ,P3>是概率有限自动机,M₂≤M1, M 3≤M1,?是M₁到M₂的同态,ψ是M1到M 3的同态,则存在M₂到M 3的同态θ使得ψ=θφ的充要条件为由同态φ诱导出的M₁的有效划分π 1与由同态ψ诱导出的M₁的有效划分π_满足π 1≤π_.定理2.2.8设M₁ =< X , Q₁ , Y ,P1> , M₂ =< X , Q2 , Y ,P2>是概率有限自动机, M₂≤M1,φ: Q₁→Q2是M₁到M₂的同态,若π 2 = { H ii = 1,2, L , n}是M₂的一个有效划分,则,Hi∈π₂是M₁的有效划分,且2 1（ H i ） = {q 1∈Q₁φ（ q1 ）∈H i }= Ki.第三章给出了概率有限自动机三种积的定义,并利用这些积对特殊的概率有限自动机进行分解.主要结果有:定理3.1.2设M₁ =< X , Q₁ , Y1 ,P1>, M₂ =< X , Q2 , Y2 ,P2> , N1 =< Z1 , R1 , U 1 ,P1′>和N 2 =< Z 2 , R2 , U 2 ,P2′>是概率有限自动机,若M₂≤wM1, N 2≤wN1,则有:ⅰ) M₂×N 2≤wM₁×N1;ⅱ)若M =< X , Q , Y ,P>,则M×N 2≤wM×N1.定理3.3.1设M =< X , Q , Y ,P>是匀概率有限自动机,则M可以分解为一个只有一个输出的匀概率有限自动机与一个马尔科夫链的串联积.定理3.3.4设M =< X , Q , Y ,P>是匀概率有限自动机,则M可以分解为一个随机编码源、一个伯努力过程和一些确定有限自动机的串联积.定理3.3.5设M t =< X t , Qt , Yt ,Pt> t = 1,2,是概率有限自动机, { }π 1 = H ii = 1,2, L ,n, { }π 2 = K jj = 1,2, L ,m分别是M₁与M₂的有效划分,则{ }π 1×π 2 = （ H i , K j ） H i∈π 1 ,Kj∈π₂是M₁×M2的有效划分,其中（ H i , K j ） = {（ qi , q j ） qi∈H i ,q j∈Kj},且M₁×M₂π 1×π₂φ1 21 2M Mπ_×π_.第四章给出自动机的几种积,重点讨论概率有限自动机积之间的同态关系,主要结果有:定理4.2.1设M₁ =< X 1 , Q₁ , Y1 ,P1>, M₂ =< X 2 , Q2 , Y2 ,P2> , M 3 =< X 3 , Q₃ , Y3 ,P3>是概率有限自动机,则以下几条成立ⅰ) （ M₁ω1 M₂ ）ω2 M 3φM₁ω3 （ M₂ω4 M3）,其中ω3 =ω1且为单射,ω4由ω1 ,ω2确定;ⅱ) （ M₁⊕M₂ ）⊕M 3φwM₁⊕（ M₂⊕M3）;ⅲ) （ M₁ o M₂ ） o M 3φwM₁ o （ M₂ o M3）;ⅳ) （ M₁ U M₂ ） U M 3 （?）M₁ U （ M₂ U M3）.定理4.2.2设M₁ =< X 1 , Q₁ , Y1 ,P1>,M₂ =< X 2 , Q2 , Y2 ,P2>是概率有限自动机,且满足对（?）q 2 ,q2′∈Q2, （?）x 2 ,x2′∈X2, y 2∈Y2,都有P2 （ q2 , x2 , q2′, y 2 ） = P2 （ q2 , x2′, q2′, y2）,即M₂的输入输出变换概率在状态一定时和输入无关时,则有M₁ωM₂≤wM₁ o M2.定理4.2.4若M =< X , Q , Y ,P>, M₁ =< X 1 , Q₁ , Y1 ,P1>, M₂ =< X 2 , Q2 , Y2 ,P2>是概率有限自动机, M₁≤wM2,则M o M₁≤wM o M2.最后部分为结束语,总结了本文的主要工作,阐述了这些工作的意义以及今后的工作.