關(guān)于擬（h，k）階存貯線性有限自動機的研究.pdf

1、自動機理論是研究離散數(shù)字系統(tǒng)的功能、結(jié)構(gòu)及其兩者關(guān)系的數(shù)學(xué)理論，它旨在研究自動機的分析與綜合問題。分析就是分析一個給定的自動機的功能，綜合就是研制一個自動機來實現(xiàn)預(yù)定的功能。隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，自動機理論有了深入的發(fā)展和廣泛的應(yīng)用，它已經(jīng)成為許多學(xué)科的重要理論和基礎(chǔ)。 (h,k)階存貯線性有限自動機是一類典型的、易于實現(xiàn)的線性有限自動機，它的輸出由現(xiàn)在時刻的輸入和剛過去的h 位輸入以及k 位輸出決定。任何一個延遲r 步弱可逆

2、線性有限自動機的構(gòu)造問題都可以歸結(jié)為延遲r 步弱可逆有限階存貯線性有限自動機的構(gòu)造問題。對一個給定線性有限自動機，當(dāng)它滿足一定的條件時，它就可以等價嵌入一個有限階存貯線性有限自動機。這些都說明(h,k)階存貯線性有限自動機在自動機的研究中具有重要的地位。我國著名學(xué)者陶仁驥先生在中提出了擬(h,k)階存貯線性有限自動機的概念。擬(h,k)階存貯線性有限自動機的狀態(tài)變換方式與(h,k)階存貯線性有限自動機相同，但它的輸出僅僅是把當(dāng)前狀態(tài)的第

3、一位上的文字輸出來，因此它的輸出更容易得到和控制。但是人們對這類線性有限自動機研究不多。本文對擬(h,k)階存貯線性有限自動機這一特殊的自動機的結(jié)構(gòu)進行了一些討論，并對擬(r,r)階存貯線性有限自動機的可逆性問題進行了一些討論，還討論了如何利用弱可逆擬(r,r)階存貯線性有限自動機構(gòu)造前饋可逆有限自動機和前饋逆有限自動機的問題。由此可見對擬(r,r)階存貯線性有限自動機的研究和討論具有重要的理論和現(xiàn)實意義。自動機的分解問題涉及到一個復(fù)雜