1、　　自動機理論是研究離散數字系統(tǒng)的功能、結構及其兩者關系的數學理論。五十年代,在開關網絡理論和數理邏輯中圖靈機理論的基礎上,形成了自動機理論這一數學分支學科。目前,根據自動機的應用情況,主要集中在可逆自動機、線性自動機和循環(huán)自動機的研究上。我國學者陶仁驥于1985年首先提出了有限自動機公開鑰密碼體制(FAPKC),由于這一理論在構造單鑰、雙鑰和基于身份的密碼體制等密碼學重要分支中都有良好的應用,并具有很大的應用潛力,進一步激發(fā)了人們的研

2、究興趣。在雙鑰和基于身份的密碼體制的構造中,有限自動機的化合成為一種基本手段。就我所知,除文獻[3~5]對兩個有限自動機化合前后的可逆性及RaRb變換之間的關系進行了深入的研究外,還沒有其它研究化合性質的文章。本人對有限自動機化合前后的嚴格延遲步數,弱逆,極小性和線性性等的關系作了一系列研究,獲得的結果對于在密碼體制構造中構造具有所需性質的自動機具有重要的指導意義。主要結論有：1.關于嚴格延遲步數：Mi是X上嚴格延遲(i步弱可逆的,i=

3、1,2,則M1(M2是延遲(1+(2步弱可逆的[12],若設其嚴格延遲步數為(,則有(1((((1+(2；若(1=0,則M1(M2與M2(M1都是嚴格延遲(2步弱可逆的；對一般情形,給出M1(M2是嚴格延遲(1+(2步弱可逆的一個充要條件。2.關于弱逆：1) 如果M1’是M1的延遲(步弱逆,M2’是M2的延遲0步弱逆,則M2’(M1’是M1(M2的延遲(步弱逆；2) 如果M1’是M1的延遲(步逆,M2’是M2的延遲(’步弱逆, 給出M2

4、’(M1’是M1(M2的延遲(+(’步弱逆的一個充分條件。
　　3.關于極小性：化合后的有限自動機極小必然要求化合前的兩個有限自動機均極小。例證兩個極小有限自動機的化合未必極小。4.關于線性性：線性有限自動機的化合仍為線性有限自動機,并給出它們<；WP=3>；之間的結構矩陣、自由響應生成矩陣和傳輸函數矩陣的顯式關系式。此外,自動機理論中最重要的一個問題是技術實現(xiàn)問題,所以對一般自動機都是研究線性實現(xiàn)問題,而(輸入)存貯線性

5、有限自動機是一類典型的、易于實現(xiàn)的且結構簡單的線性有限自動機。文獻[33]中給出了等價嵌入于存貯線性有限自動機的一組充要條件以及一個可等價嵌入的充分條件和一個不可等價嵌入的充分條件。"嵌入于"意味著后者的功能強于前者,并可能強于前者許多,這就是說后者雖然能實現(xiàn)前者的功能,但可能會有一些"浪費"。什么樣的線性有限自動機剛好與一個(輸入)存貯線性有限自動機功能等價,或者說(輸入)存貯線性有限自動機能夠實現(xiàn)的功能最強線性有限自動機是哪一類線性

6、有限自動機？本人運用文獻[33]提出的模的思想方法研究(輸入)存貯線性有限自動機的功能等價問題,回答了上述問題,從而對于將一類復雜的線性有限自動機化簡為易于實現(xiàn)的(輸入)存貯線性有限自動機具有重要的理論和現(xiàn)實意義。主要結論有：1.可等價嵌入于一個輸入存貯線性有限自動機,則必然等價于這個輸入存貯線性有限自動機。并給出一組等價于輸入存貯線性有限自動機的充要條件和一個充分條件。2.給出等價于存貯線性有限自動機的一個充要條件。3.兩個(輸入)存

7、貯線性有限自動機的化合,必存在它的一個子線性有限自動機與一個(輸入)存貯線性有限自動機等價。全文分為三章： 介紹自動機理論的歷史背景與發(fā)展現(xiàn)狀和本人的研究內容與主要結果,并將文中涉及到的一些基本概念和記號作了系統(tǒng)的介紹。 對有限自動機化合前后的嚴格延遲步數、弱逆、極小性以及線性性等的關系進行研究,給出所獲得的結果。 運用文獻[33]提出的模的思想方法研究(輸入)存貯線性有限自動機功能等價問題,解決了什么樣的線性有限自動機剛好與一個