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

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

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

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

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

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