有限自動(dòng)機(jī)的化合與等價(jià)于(輸入)存貯線性有限自動(dòng)機(jī)問(wèn)題.pdf

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

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

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

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

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

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

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