一類有限自動機及其積的試驗序列.pdf

1、自動機理論是研究離散數字系統(tǒng)的功能、結構及兩者關系的數學理論,隨著數字計算機、數字通信及自動化等新技術的出現和發(fā)展,自動機理論已成為許多學科的重要理論和應用基礎.有限自動機理論是自動機理論的一個重要的分支,它在控制理論、對象程序測試、神經網絡、保密學等眾多學科中有著重要的作用,而非線性有限自動機理論在數字系統(tǒng)和通信等時序領域建模過程中有著非常廣泛的應用.在有限自動機初始狀態(tài)等價類識別,數字電路中的“置0 ”,以及對有限自動機模型的一致性

2、測試中,試驗序列起到了非常重要的作用,因此有限自動機的試驗序列有著非常重要的現實意義. 一個延遲τ步弱可逆的有限自動機M=(X,Y,S，δ，λ)，當∣X∣=∣Y∣=n>1,且∣WMτs∣=1對As ∈S成立,則M 可分解為一個延遲0 步弱可逆的有限自動機 M0和一個τ階延遲元,即M

3、自動機的分解中起到非常重要的作用.本文討論了 M τd 這類有限自動機及其積的試驗序列，另外由兩個或多個有限自動機的積可以構造出結構相對單個有限自動機結構復雜的一些有限自動機,而利用簡單有限自動機的性質推導復雜有限自動機的性質是自動機理論研究的一個常用手段.本文還討論了有限自動機的兩種積的試驗序列. 主要結論有： 1、結合有限自動機的化合運算性質對C,(M,Md)和C(M,Mnd)的初(末)態(tài)試驗序列、同步序列、UIO序

4、列及D序列進行了討論,由此得出了它們的一系列性質. 2、結合有限自動機的完全直積運算性質對M ×Md和 M ×Mnd的初(末)態(tài)試驗序列、同步序列、UIO序列及D序列進行了討論,由此得出了它們的一系列性質. 3、聯系有限自動機完全直積運算與限制直積運算之間的聯系與區(qū)別,得到了 M ∧Md和 M ∧ Mnd的初(末)態(tài)試驗序列、同步序列、UIO序列及D序列的性質及其這些試驗序列之間的聯系與區(qū)別. 4、當兩個有限自動

5、機之間分別具有等價、弱同構、同構、強于關系時,對具有這些關系的兩個有限自動機的試驗序列進行了討論,得到了具有這些關系的兩個有限自動機的試驗序列分別具有的聯系和區(qū)別. 全文共分為四章： 第一章介紹了有限自動機理論的背景以及研究有限自動機試驗序列的現狀,同時給出了有限自動機以及試驗序列的一些基本概念和記號. 第二章應用有限自動機化合的運算性質給出了C(M,Md)和C(M,Mnd)的初(末)態(tài)試驗序列、同步序列、UIO