| 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. |
PDF Full Text Request