自动机理论是研究离散数字系统的功能、结构及两者关系的数学理论.它旨在研究自动机的分析与综合问题.有限自动机是自动机理论的一个分支,随着数字计算机,数字通信和自动化等科学技术的出现和发展,自动机理论在理论和实践中发挥着越来越重要的作用.有限识别器可用于辨别或接受有限状态语言,它在结构模式识别中起着十分重要的作用.利用自动机进行模式识别一直是人们研究的问题.本文讨论了有限识别器的状态等价、状态化简,有限识别器的极小化,并且利用矩阵模型对有限识别器和偏限自动机的性质进行了讨论.本文分为四部分,前三部分中每个部分为一章,最后部分为结束语.第一章讨论了有限识别器的状态等价、状态化简,有限识别器的极小化.得出了状态等价、状态化简的一些结果,并给出了有限识别器的极小化的方法.主要结果有:定理1.2.2设( )M =M , i0 ,T和都是可分有限识别器,其中M = ( I , S ,δ), M′= ( I′, S′,δ′).若M～M ’且M = M ’,则M与M ’同构.定理1.2.3对任何有限识别器M ,在同构意义下唯一存在一个可分有限识别器M ’,使得M ’～M ,并且M ’=M .定理1.2.4设( )M =M , i0 ,T是一个有限识别器,其中M = ( I , S ,δ), A = M .若M可达,则M A与M ’同构.第二章讨论了利用矩阵模型研究有限识别器的状态等价、状态化简,有限识别器的极小化等性质.主要结果有:定理2.1.2对于给定的1×n布尔函数矩阵I 0( x ),任何m0×n布尔函数矩阵T ( x )和n×n布尔函数矩阵B ( x ),(其中1≤m0≤n),只要B ( x )满足性质2.1.2和性质2.1.3,则有有限识别器M存在,使M的矩阵模型为:其中布尔函数矩阵T ( x )是布尔函数矩阵B ( x )的块,而{ }X = ( a1 , a 2, al ) | ai = 0,1, i = 1,2, , l,这里假设x = ( x1 , x2 , , xl)为l维布尔向量,而Q = (Q 1 , Q2 , , Qn)T ,这里“T”表示矩阵的转置变换.定理2.2.1设δ(Q i , x1 x2 xk )= Qp,δ(Q j , x1 x2 xk )= Qq,k∈N*,? x i∈X,i = 1, ,k;则Qi～k Q j?1≤p≤m0当且仅当1≤q≤m0.其中m0是M的终结状态集的状态数.第三章讨论了利用矩阵模型研究偏有限自动机性质.主要结果有:定理3.2.2通过偏有限自动机Μ定义的Μc反映Μc输入一个布尔变量变换情况的矩阵模型为那么,关于( )Αc x和( )Βc x,还有以下性质:的最后一列(第( n + 1)列)的前n行元素为的第i行第j列(1≤i , j≤n)元素等于的第i行第j列元素.(3)最后一列(即第n + 1列)的前n行元素为0;(4) )的第i行第j列(1≤j≤n ,1≤i≤p)的元素等于的第i行第j列的元素.定理3.2.3反映偏有限自动机Μ输入一个布尔变量后变换情况的矩阵模型为那么,反映偏有限自动机Μ输入m ( m∈N*)个布尔变量后变换情况的矩阵模型(矩阵方程组)为