矩陣模型在有限自動(dòng)機(jī)上的應(yīng)用.pdf

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

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

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

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

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