【作者】 汤恒琦；

【导师】 易忠；

【作者基本信息】 广西师范大学 ， 应用数学， 2008， 硕士

【摘要】 模糊自动机是自动机研究领域的一个重要方向,它在自动控制、计算机科学等许多领域均有广泛的应用.目前人们主要基于代数拓扑、多值逻辑、剩余逻辑、模糊逻辑及格半群意义下来研究模糊自动机.本文主要采用代数的方法研究了模糊识别器与有穷自动机的等价性,幺半环上的模糊有限状态机在同态下的交换性质、连通性、分离性,幺半环上几类模糊自动机的关系以及幺半环上一类有限自动机的约简性.本文分为六个部分,第一部分是引言,第二至第五部分中每一部分为一章,是本文的核心,最后部分是结束语.引言部分主要介绍本文的研究背景、研究依据、理论来源和研究的意义以及本文的主要研究成果.第一章针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间在识别语言功能上的等价性.主要结果有:定理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等价.最后部分为结束语,总结了本文的主要工作,阐述了与本文相关研究的一些课题,并对下一步的继续研究工作做了设想.更多还原

【Abstract】 Fuzzy automata is an important direction in the research field of automata, it is widely used in the fields such as automatic control technology and computer sciences etc. In the present, people study fuzzy automata by the methods based on algebraic topology, multi-valued logic, remaining logic, fuzzy logic and under the sence of lattice-monoid. In the paper, equivalence between fuzzy recognizers and finite automata, the exchange property, connectivity and separability under the homomorphism between two fuzzy finite state machines over unitary semirings, relationships among several types of fuzzy automata over unitary semirings, and reduction of fuzzy finite-state automata over unitary semirings are studied through applying algebraic methods.This paper is composed of six parts. The first part is the introduction, the second to the fifth parts are the core of this paper.Part I, i.e. Introduction, some of the research background, theory and research sources, the significance of this paper and the main results of the study are introduced.Part II, i.e. Chapter one, the relationship of fuzzy recognizers and finite automata is discussed. When the same input alphabet is given, the conclusion is proved that given any fuzzy recognizer, inevitably there is a finite automata, the acceptable language of which is the same as the behavior of the fuzzy recognizer, and conversely, given any finite automata, there exists a fuzzy recognizer, the behavior of which is the same as the acceptable language of the finite automata. Thus, the equivalence on the function of language recognition between them is obtained. The main results are as following:Theorem 1.2.3 Let L ?Σ?,then the following statements are equivalent:(ⅰ) L is a regular language;(ⅱ) There exists a deterministic finite automata (for short DFA) A 1, such that A1 = L;(ⅲ) There exists a nondeterministic finite automata (for short NFA ) A 2, such that A2 = L;(ⅳ) There exists a nondeterministic finite automata withε? move (for shortε? NFA) A 3, such that A3 = L;(ⅴ) There exists a fuzzyΣ?recognizers M , such that M = L.Part III, i.e. Chapter two, the concept of fuzzy finite state machines over unitary semirings is given, the statewise equivalence of fuzzy finite state machines over unitary semirings is defined, and the notion of homomorphism between two fuzzy finite state machines over unitary semirings is introduced. Homomorphism Theorem and Epimorphism Decomposition Theorem are obtained, and the exchange property, connectivity and separability of submachines of fuzzy finite state machines over unitary semirings under homomorphism are discussed. The main results are as following:Theorem 2.2.1(Homomorphism Theorem)Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two fuzzy finite state machines over unitary semirings (for short RFM ). If (α,β): M→M’ is an epimorphism, then an RFM M is induced by the epimorphism (α,β): M→M’ and such that M ? M’.Theorem 2.2.2( Epimorphism Decomposition Theorem)Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two RFMs and (α,β): M→M’ an epimorphism. Suppose thatπαis the partition defined byαon Q ,πis a partition on Q satisfying the conditionπ≤πα,πβis the partition defined byβonΣand thatτis also a partition onΣsatisfying the conditionτ≤πβ,then(ⅰ) an RFM M ’’ is induced byπandτ, and there exists an epimorphism (απ,βτ): M→M’’;(ⅱ) there exists an epimorphism (λ,μ): M ’’→M’ such that the following diagram of homomorphisms (Fig 2-1) is commutative:Theorem 2.2.3 Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two RFMs . Suppose that (α,β): M→M’ an epimorphism, then M satisfies the exchange property if and only if M ’ satisfies the exchange property.Theorem 2.2.4 Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two RFMs . Suppose that (α,β): M→M’ is an epimorphism and Q ’ > 1, then M is strongly connected iff M ’ is strongly connected.Theorem 2.2.6 Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two RFMs .(ⅰ) Suppose that (α,β): M→M’ is an epimorphism and N = (T ,Σ,η)is a separated submachine of M , thenN ’ =α(T ),Σ’,δ’α( T) is a separated submachine of M ’. (ⅱ) Suppose that (α,β): M→M’ is a homomorphism, N ’ = (T ’,Σ’,η) is a separated submachine of M ’, andα?1 (T ’)≠? , then ( )11Nα(T ’), ,δα( T’)?= ?Σis a separated submachine of M .Theorem 2.2.7 Let M = (Q ,Σ,δ) and M ’ = (Q ’,Σ’,δ’) be two RFMs and (α,β) : M→M’ an epimorphism. If M is connected, then M ’ is also connected. Conversely, the conclusion is not true.Part IV, i.e. Chapter three, the definitions of the four types of nondeterministic fuzzy automata and the four types of deterministic fuzzy automata over unitary semirings and their languages are given. The equivalence among the former three types of nondeterministic fuzzy automata and the equivalence among the former three types of deterministic fuzzy automata over unitary semirings are proved. The relationships between the fourth type of nondeterministic fuzzy automata over unitary semirings and the other former types nondeterministic fuzzy automata over unitary semirings are studied, and the relationships between nondeterministic fuzzy automata and deterministic fuzzy automata over unitary semirings are also discussed. The main results are as following:Theorem 3.2.1 For an R ?language f onΣ, the following statements are equivalent:(ⅰ) f can be accepted by a 1? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 1);(ⅱ) f can be accepted by a 2 ?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 2);(ⅲ) f can be accepted by a 3? type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 3).Theorem 3.2.2 LetΣbe a nonempty finite set and R a unitary semirings. For an R ?language f onΣ, if it can be accepted by a 4?type of nondeterministic fuzzy automata over unitary semirings (for short NRA? 4), then it can also be accepted by some NRA? 1.On the contrary, suppose that f can be accepted by a NRA? 1,then there exists some NRA? 4M4 such that 4f M( x ) = f ( x) for any x∈Σ+.Theorem 3.3.1 For an R ?language f onΣ, the following statements are equivalent:(ⅰ) f can be accepted by an 1? type of deterministic fuzzy automata over unitary semirings (for short DRA? 1);(ⅱ) f can be accepted by a 2 ? type of deterministic fuzzy automata over unitary semirings (for short DRA? 2);(ⅲ) f can be accepted by a 3? type of deterministic fuzzy automata over unitary semirings (for short DRA? 3).Theorem 3.4.1 Let f be an R ?language onΣ. Suppose that f can be accepted by a DRA, then it can be also accepted by some NRA , but conversely, the conclusion is not true.Part V, i.e. Chapter four, the notion of equivalence between two states of deterministic finite-state automata over unitary semirings is defined, reduction of the kind of automata is discussed, and a computing algorithm on reduction of the type of automata is given. The main result are as following:Theorem 4.2.2 Let M = (Q ,Σ,δ,σ0 ,σ1) be a deterministic finite-state automata over unitary semirings (for short DRSA). Then there must exist a reductive DRSA such that it and M are equivalent.Part VI is concluding remarks, the main work of this paper is summarized, some subjects corresponding to this paper are simply illustrated, and the idea to the next phase of work to continue to study is roughly envisaged.更多还原