一類有限自動機(jī)及其積的試驗(yàn)序列.pdf

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

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

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

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

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