自动机理论[1]是研究离散数字系统的功能、结构及两者关系的数学理论,随着数字计算机、数字通信及自动化等新技术的出现和发展,自动机理论已成为许多学科的重要理论和应用基础.有限自动机理论是自动机理论的一个重要的分支,它在控制理论、对象程序测试、神经网络、保密学等众多学科中有着重要的作用,而非线性有限自动机理论在数字系统和通信等时序领域建模过程中有着非常广泛的应用.在有限自动机初始状态等价类识别,数字电路中的“置0”,以及对有限自动机模型的一致性测试中,试验序列起到了非常重要的作用,因此有限自动机的试验序列有着非常重要的现实意义.一个延迟τ步弱可逆的有限自动机M = X , Y , S ,δ,λ,当X = Y = n> 1,且WτMs= 1对?s∈S成立,则M可分解为一个延迟0步弱可逆的有限自动机M 0和一个τ阶延迟元,即（ ）M ? C M 0 , Mτd.而弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径,从而Mτd及C （ M , Mτd）在有限自动机的分解中起到非常重要的作用.本文讨论了Mτd这类有限自动机及其积的试验序列,另外由两个或多个有限自动机的积可以构造出结构相对单个有限自动机结构复杂的一些有限自动机,而利用简单有限自动机的性质推导复杂有限自动机的性质是自动机理论研究的一个常用手段.本文还讨论了有限自动机的两种积的试验序列.主要结论有:1结合有限自动机的化合运算性质对C （ M , M d）和C （ M , M nd）的初（末）态试验序列、同步序列、UIO序列及D序列进行了讨论,由此得出了它们的一系列性质.2结合有限自动机的完全直积运算性质对M×Md和M×Mnd的初（末）态试验序列、同步序列、UIO序列及D序列进行了讨论,由此得出了它们的一系列性质.3联系有限自动机完全直积运算与限制直积运算之间的联系与区别,得到了M∧Md和M∧Mnd的初（末）态试验序列、同步序列、UIO序列及D序列的性质及其这些试验序列之间的联系与区别.4当两个有限自动机之间分别具有等价、弱同构、同构、强于关系时,对具有这些关系的两个有限自动机的试验序列进行了讨论,得到了具有这些关系的两个有限自动机的试验序列分别具有的联系和区别.全文共分为四章:第一章介绍了有限自动机理论的背景以及研究有限自动机试验序列的现状,同时给出了有限自动机以及试验序列的一些基本概念和记号.第二章应用有限自动机化合的运算性质给出了C （ M , M d）和C （ M , M nd）的初（末）态试验序列、同步序列、UIO序列及D序列的性质及其最短试验序列个数的判定.主要结果有:定理2.2.2若β= x1 x2 xk∈X?是M的初（末）态试验序列,则对?x∈X都有α=βx = x1 x2 xk x是C （ M , M d）的初（末）态试验序列,从而由β可以产生X个不同的C （ M , M d）的初（末）态试验序列.定理2.3.1设β= x1 x2 xm,则β是C （ M , M nd）的一个同步序列的充要条件是β≥n,β是M的一个同步序列且?s 1 ,s 2∈S都有（ （ ）） （ （ ）） （ （ ））δs1 , L ? n,β～R ? m ?n,βδs2 , L ?n,β.这里R （ ? n,β）和L （ ? n,β）分别表示去掉字β的左端和右端n位所得的字.第三章应用有限自动机完全（限制）直积的运算性质给出了M×Md, M×Mnd,M∧Md及M∧Mnd的初（末）态试验序列、同步序列、UIO序列及D序列的性质及最短试验序列个数的判定.主要结果有:定理3.2.2设对任意的α∈X?且α≥n,则α是M nd = X , X , X n,δnd ,λnd的初（末）态试验序列、同步序列和D序列,且最短试验序列的长度是n,个数是n n.此外（ ）? x1 , x2 , , xn∈Xn都有（ （ ））αλn d x1 , x2 , , xn,α是Mn d的一个UIO序列.定理3.4.1设α∈X?,则α是M∧Mnd的初（末）态试验序列、同步序列、D序列的充分必要条件是α是M的初（末）态试验序列、同步序列、D序列且α≥n.第四章应用有限自动机等价、弱同构、同构、强于的性质给出了两个有限自动机之间当分别具有等价、弱同构、同构、强于时它们之间试验序列的关系及性质.主要结果有:定理4.2.2设M = X , Y , S ,δ,λ和M′= X′, Y′, S′,δ′,λ′是两个有限自动机,其中M′为极小有限自动机,且M～M′,则下列结论成立:（1）若α∈X?是M的同步序列,则α是M′的同步序列;（2）若α∈X?是M的D序列,则α是M′的D序列;（3）若αλ（ s,α）是M的一个UIO序列,则αλ′（ s′,α）是M′的一个UIO序列.这里s∈S ,s′∈S′,且s～s′.定理4.2.3设M 1 = X 1 , Y1 , S1 ,δ1 ,λ1 , M 2 = X 2 , Y2 , S2 ,δ2 ,λ2都是有限自动机,且M 1与M 2弱同构,则下列结论成立:（1）α∈X₁^*是M 1的初态试验序列,当且仅当φX（α）是M 2的初态试验序列;（2）α∈X₁^*是M 1的末态试验序列,当且仅当φX（α）是M 2的末态试验序列;（3）α∈X₁^*是M 1的同步序列,当且仅当φX（α）是M 2的同步序列;（4）α∈X₁^*是M 1的D序列,当且仅当φX（α）是M 2的D序列;（5）是M 1的一个UIO序列,当且仅当, Xα是M 2的一个UIO序列.这里（ ）s′= Ss.