矩陣模型在有限自動機上的應用.pdf

1、廣西師范大學碩士學位論文矩陣模型在有限自動機上的應用姓名：楊楠申請學位級別：碩士專業(yè)：基礎(chǔ)數(shù)學指導教師：易忠20070401II步序列的充要條件， 并且構(gòu)造出了判斷一個線性有限自動機是否有同步序列的算法. 3 利用矩陣模型方法對兩個有限自動機的限制直積進行討論，在此基礎(chǔ)上構(gòu)造了限制直積的狀態(tài)映射矩陣和輸出映射矩陣， 并進行了研究， 得出了它們的一些性質(zhì): 關(guān)于狀態(tài)轉(zhuǎn)移函數(shù)運算的兩個結(jié)果和輸出函數(shù)的兩個結(jié)果. 4 利用矩陣模型對兩個有限自

2、動機的級聯(lián)積進行了討論，在此基礎(chǔ)上構(gòu)造了級聯(lián)積的狀態(tài)映射矩陣和輸出映射矩陣， 并進行了研究， 得出了它們的一些性質(zhì): 級聯(lián)積的映射矩陣的一些性質(zhì), 級聯(lián)積的狀態(tài)轉(zhuǎn)移函數(shù)運算的兩個結(jié)果, 級聯(lián)積的輸出函數(shù)的一些性質(zhì)及其運算的兩個結(jié)果. 全文共分為五章: 第一章 介紹了自動機理論的背景以及用矩陣模型方法研究自動機的現(xiàn)狀,同時給出了有限自動機以及矩陣模型的一些基本概念和記號. 第二章 應用矩陣模型方法在有限自動機弱可逆上,所得的結(jié)果可以判斷有

3、限自動機和線性有限自動機是否具有弱可逆性,若具有弱可逆性,延遲幾步弱可逆. 主要結(jié)果有： 定 理 定 理 2.2.4 : 設 , , , , M I O S δ λ ? 是 線 性 有 限 自 動 機 ， 矩 陣 模 型 為 ：( )( )Z A x QQ B x Q= × ? ? = × ?， x X ∈ ，則 M 延遲τ 步弱可逆的充分必要條件是：對任意1 0 ( ) x x ≠ ， 若存在 2, , x x

4、X τ ∈ ? ， 使得 1 1 ( ) ( ) ( ) h h A x B x B x ? × × × ? (1 ) h τ ≤ ≤ 的第一列的第一個元素為 1，若此時 1 ( ) ( ) B x B x τ × × ? 的第一列的不為零的元素為第 k 行，則 1 ( ) 0 k a x = . 第三章 應用矩陣模型方法在試驗序列上, 所得的結(jié)果可以求一個極小線性有限自動機的最短初態(tài)試

5、驗序列，并且判斷一個輸入序列是否是（線性）有限自動機的同步序列，若一個線性有限自動機有同步序列,利用所得的結(jié)果可以求出最短同步序列. 主要結(jié)果有： 定理 定理3.2.1：設 , , , , M I O S δ λ ? 是有限自動機， I ，O 和 S 的布爾量表示為 , X Z 和Q ， 矩陣模型為： ( )( )Z A x QQ B x Q= × ? ? = × ?，x X ∈ ，則 1 k x x X α ? =