论文部分内容阅读
模糊自动机是自动机研究领域的一个重要方向,它在自动控制、计算机科学等许多领域均有广泛的应用.目前人们主要基于代数拓扑、多值逻辑、剩余逻辑、模糊逻辑及格半群意义下来研究模糊自动机.本文主要采用代数的方法研究了模糊识别器与有穷自动机的等价性,幺半环上的模糊有限状态机在同态下的交换性质、连通性、分离性,幺半环上几类模糊自动机的关系以及幺半环上一类有限自动机的约简性.本文分为六个部分,第一部分是引言,第二至第五部分中每一部分为一章,是本文的核心,最后部分是结束语.引言部分主要介绍本文的研究背景、研究依据、理论来源和研究的意义以及本文的主要研究成果.第一章针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间在识别语言功能上的等价性.主要结果有:定理1.2.3设L ?Σ?,则下列陈述等价:(ⅰ)L是正则语言;(ⅱ)存在一个DFA A 1,使得A1 = L;(ⅲ)存在一个NFA A 2,使得A2 = L;(ⅳ)存在一个ε? NFAA 3,使得A3 = L;(ⅴ)存在一个模糊Σ?识别器M ,使得M = L.第二章给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性,主要结果有:定理2.2.1(同态定理)设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM ,若(α,β): M→M’是一个满同态,则由满同态(α,β): M→M’可导出一个RFM M ,且M ? M’.定理2.2.2(满同态分解定理)设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM , (α,β): M→M’是一个满同态,由α决定Q上的划分为πα,由β决定Σ上的划分为πβ,若π是Q上的一个划分且π≤πα,τ是Σ上的一个划分且τ≤πβ,则(ⅰ)由π,τ导出一个RFM M ’’,且存在一个满同态(απ,βτ): M→M’’;(ⅱ)存在满同态(λ,μ): M ’’→M’,使下面的同态图表(图2-1)交换.定理2.2.3设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM ,若(α,β): M→M’是一个满同态,则M满足交换性质的充分必要条件是M ’满足交换性质.定理2.2.4设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM ,若(α,β): M→M’是一个满同态,且Q ’ > 1,则M是强连通的充分必要条件是M ’是强连通的.定理2.2.6设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM ,则:(ⅰ)若(α,β): M→M’是一个满同态,且N = (T ,Σ,η)是M的一个可分离的子状态机,则( )N ’ =α(T ),Σ’,δ’α( T)是M ’的可分离的子状态机.(ⅱ)若(α,β): M→M’是一个同态, N ’ = (T ’,Σ’,η)是M ’的一个可分离的子状态机,且α?1 (T ’)≠?,则( )11Nα(T ’), ,δα( T’)?= ?Σ是M的可分离的子状态机.定理2.2.7设M = (Q ,Σ,δ), M ’ = (Q ’,Σ’,δ’)是RFM ,且(α,β): M→M’是一个满同态,若M是连通的,则M ’也是连通的;反之不一定成立.第三章给出了幺半环上四类非确定的模糊自动机和四类确定的模糊自动机及其语言的定义,证明了幺半环上前三类非确定的模糊自动机间的等价性和前三类确定的模糊自动机间的等价性,讨论了幺半环上前三类非确定的模糊自动机和第四类非确定的模糊自动机之间的关系,以及幺半环上非确定的模糊自动机和确定的模糊自动机之间的关系.主要结果有:定理3.2.1对Σ上的一个R?语言f ,下列陈述等价:(ⅰ) f能被一个NRA? 1接受;(ⅱ) f能被一个NRA? 2接受;(ⅲ) f能被一个NRA? 3接受.定理3.2.2设Σ是一个非空有限集合,R是一个幺半环,对Σ上的一个R?语言f ,如果f能被一个NRA? 4所接受,则它也能被一个NRA? 1接受;反之,如果f能被一个NRA?1所接受,则存在一个NRA? 4M 4,使得?x≠ε,4f M( x ) = f ( x).定理3.3.1对Σ上的一个R?语言f ,下列陈述等价:(ⅰ) f能被一个DRA? 1接受;(ⅱ) f能被一个DRA? 2接受;(ⅲ) f能被一个DRA? 3接受.定理3.4.1设f是Σ上的一个R?语言,若f能被一个DRA接受,则f也能被一个NRA接受,但反之不一定成立.第四章给出了幺半环上确定型有限状态自动机的状态的等价定义,对幺半环上确定型有限状态自动机的约简性进行了讨论,并给出了一个算法.主要结果有:定理4.2.2设M = (Q ,Σ,δ,σ0 ,σ1)是一个DRSA,则必然存在一个约简的DRSA与M等价.最后部分为结束语,总结了本文的主要工作,阐述了与本文相关研究的一些课题,并对下一步的继续研究工作做了设想.