有限識別器的狀態(tài)等價與矩陣模型的應(yīng)用.pdf

1、自動機理論是研究離散數(shù)字系統(tǒng)的功能、結(jié)構(gòu)及兩者關(guān)系的數(shù)學(xué)理論。它旨在研究自動機的分析與綜合問題。有限自動機是自動機理論的一個分支，隨著數(shù)字計算機，數(shù)字通信和自動化等科學(xué)技術(shù)的出現(xiàn)和發(fā)展，自動機理論在理論和實踐中發(fā)揮著越來越重要的作用。有限識別器可用于辨別或接受有限狀態(tài)語言，它在結(jié)構(gòu)模式識別中起著十分重要的作用。利用自動機進行模式識別一直是人們研究的問題。 本文討論了有限識別器的狀態(tài)等價、狀態(tài)化簡，有限識別器的極小化，并且利用矩陣

2、模型對有限識別器和偏限自動機的性質(zhì)進行了討論。 第一章討論了有限識別器的狀態(tài)等價、狀態(tài)化簡，有限識別器的極小化．得出了狀態(tài)等價、狀態(tài)化簡的一些結(jié)果，并給出了有限識別器的極小化的方法.主要結(jié)果有： 定理1.2.2 設(shè)m=(M,i0,T)和m'=(M',i0',T')都是可分有限識別器，其中M=(I,S,δ),M'=(I',S',δ').若m～m'且|m|=|m'|，則m與m'同構(gòu)。 定理1.2.3 對任何有限識別器

3、M,在同構(gòu)意義下唯一存在一個可分有限識別器m',使得m'～m,并且|m'|=|m|。 定理1.2.4 設(shè)m=(M,i0,T)是一個有限識別器,其中M=(I,S,δ),A=|M|.若M可達,則mA與m'同構(gòu)。 第二章討論了利用矩陣模型研究有限識別器的狀態(tài)等價、狀態(tài)化簡，有限識別器的極小化等性。主要結(jié)果有： 定理2.1.2 對于給定的1×n布爾函數(shù)矩陣I0(x)，任何m0×n布爾函數(shù)矩陣T(x)和n×n布爾函數(shù)矩陣B

4、(x)，(其中1≤m0≤n)，只要B(x)滿足性質(zhì)2.1.2和性質(zhì)2.1.3，則有有限識別器m存在，使m的矩陣模型為： {i0=I0(x)×QT=T(x)×QQ=B(x)×Q(x∈X)其中布爾函數(shù)矩陣T(x)是布爾函數(shù)矩陣B(x)的塊，而X={(a1,a2,…al)|ai=0,1,I=0,1,I=1,2,…,l},這里假設(shè)x=(x1,x2,…,xl)為l維布爾向量，而Q=(Q1,Q2,…,Qn)T,這里“T”表示矩陣的轉(zhuǎn)置變換。

5、 定理2.2.1 設(shè)δ(Q1,x1x2…xk)=Qp,δ(Qf,x1x2…xk)=Qq，k∈N*,(A)xi∈X，I=1,…,k；則Qi～kQf(←→)1≤p≤m0 當(dāng)且僅當(dāng)1≤q≤m0.其中m0是m的終結(jié)狀態(tài)集的狀態(tài)數(shù)。 第三章討論了利用矩陣模型研究偏有限自動機性質(zhì)。主要結(jié)果有： 定理3.2.2 通過偏有限自動機M定義的Mc反映Mc輸入一個布爾變量變換情況的矩陣模型為{Z'=Ac(x)×Q'；Q'=Bc(x)×

6、Q'；(x∈X)。 那么，關(guān)于Ac(x)和Bc(x)，還有以下性質(zhì)： （1）[Bc(x)]m的最后一列（第(n+1)列）的前n行元素為0。 （2）[Bc(x)]m(n+1)(n=1)的第I行第j列(1≤I,j≤n)元素等于[B(x)]m n×n的第I行第j列元素。 （3）Ac(x)[Bc(x)]m最后一列（即第n+1列）的前n行元素為0。 （4）Ac(x)[Bc(x)]m(n+1)(n+1)的第I