论文部分内容阅读
本文主要研究素数阶循环自动机和3,4-状态极端同步自动机,给出了素数阶循环自动机可扩张状态集的一些性质,定义了亏损字母和置换字母,并且通过讨论这两种字母在极端同步自动机中的存在情况,找出了包括现有的八种极端必要同步自动机在内的27种3,4-状态极端同步自动机.本文共分三章,具体内容如下:第一章:引言与预备知识.第二章:利用线性表示的方法简单地证明了n-状态循环自动机中所含状态数与n互素的子状态集都是n-可扩张的,并给出其最短同步字的一个具体形式,应用所得结论可以直接获得Pin关于素数阶同步循环自动机的结果.主要结论如下:定理2.2.1设A=(Q,∑,δ)是一个n-状态循环自动机,a是A的一个循环字母,&是A的一个亏损字母,P是Q的一个m阶非空真子集.如果(m,n)=1,那么P有一个形如bai(0≤i≤n-1)的扩张字.第三章:研究了3,4-状态极端同步自动机.对于3,4-状态极端同步自动机,首先分别给出了它们的部分公共特征,然后再根据所含置换字母的轨道数由少到多依次分析,最终得出了包括8种极端必要同步自动机在内的27种极端同步自动机.主要结论如下:定理3.2.1在同构意义下,3-状态极端同步自动机共有15个,其中有Fig.1中给出的4个极端必要同步自动机和Fig.1中未给出的11个极端非必要同步自动机.引理3.2.2设A=(Q,∑,δ)是一个3-状态极端同步自动机,且其中,∑1是所有置换字母的集合,∑2是所有1-亏损字母的集合,∑3是所有2-亏损字母的集合.则有以下结论成立:(1) ∑3 =(?), ∑2≠(?);(2)对任意的b∈∑2,有Qb2=Qb;(3) A有唯一的亏损状态;Q = {1,2,3}, E=∑1∪∑2∪E3,∑1 = {a1,a2,··· ,al}, ∑2={b1,b2,…,bm},∑3 ={c1,c2,· · ·,c?}.(4) ∑1≠(?).定理3.3.1在同构意义下,4-状态极端同步自动机共有12个,其中有Fig.1中给出的2个极端必要同步自动机和Fig.1中未给出的10个极端非必要同步自动机.引理3.3.2设A=(Q,∑,δ)是一个4-状态极端同步自动机,且其中,∑1是所有置换字母的集合,∑2是所有1-亏损字母的集合,∑3是所有2-亏损字母的集合,∑4是所有3-亏损字母的集合.则有以下结论成立:(1) ∑3 =(?), ∑4 =(?), ∑2≠(?);(2)对任意的b∈∑;2,有Qb2=Qb;(3) A有唯一的亏损状态;(4) ∑1≠(?).