有限自動機的化合與等價于(輸入)存貯線性有限自動機問題.pdf

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

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

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

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

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

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

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