| Computation theory is one of the basic contents of theoretical computer science,which includes automata theory,formal languages,computational complexity,etc.Fuzzy computation theory is a computation theory based on fuzzy logics and fuzzy sets.Fuzzy finite automata(fuzzy automata for short),fuzzy grammars and fuzzy Turing machines are models of fuzzy computation theory.The study of fuzzy languages and fuzzy automa-ta has attracted extensive attention as a means for bridging the gap between vagueness and imprecision,which are frequently encountered in the study of natural languages,and the precision of computer languages.For a fuzzy language,the existence of fuzzy automata which recognize this language is a basic and important problem.Taking fuzzy languages into consideration,they are ap-proximate descriptions of real systems and it is of considerable realistic significance to study the approximate implementation of fuzzy languages.Here,the approximate im-plementation of fuzzy languages means that for any string,the language accepted by a fuzzy automaton is very close to the assignment value of the given fuzzy language on this string.For studying properties of fuzzy languages which approximate fuzzy regular lan-guages,this thesis introduces a kind of fuzzy approximate regular languages and study the implementation of minimal deterministic fuzzy automata e-accepting them.For a fuzzy automaton,in order to combine equivalent states as many as possible to generate an aggre-gated fuzzy automaton with fewer states but with an approximate behavior,this thesis will introduce ?-approximate bisimulations and ?-similarity bisimulations for fuzzy automata,study the approximate minimization of fuzzy automata with ?-approximate bisimulations and ?-similarity bisimulations respectively and discuss their differences and connections.In the context of interval type-2 fuzzy languages,we give the notion of interval type-2 fuzzy weak regular languages and study their properties and minimization methods.The main results of this thesis are as follows:1.Introducing fuzzy approximate regular languages and giving the minimization implementation of them:Firstly,we introduce the notion of fuzzy ?-approximate reg-ular languages and compare different sets of fuzzy ?-approximate regular languages by taking different ? to get an infinite hierarchy of fuzzy languages.Then,we prove that the operations of union,intersection,complement,concatenation and Kleene closure of fuzzy languages are closed in the set of fuzzy ?-approximate regular languages,but the operations of Lukasiewicz addition,Lukasiewicz product and Lukasiewicz implication are not closed.Finally,we study the implementation of minimal deterministic fuzzy automata ?-accepting fuzzy ?-approximate regular languages.Especially,for a fuzzy reg-ular language,we give a polynomial-time algorithm to construct at least one minimal deterministic fuzzy automaton ?-accepting it.2.Studying approximate bisimulations for fuzzy automata and giving the approxi-mate minimization method of them:We define ?-approximate bisimulations between two fuzzy automata and study their properties.Using the notion of surjective functional ?-approximate bisimulations between two fuzzy automata,we define ?-approximate bisim-ulations for fuzzy automata and construct the corresponding aggregated fuzzy automata.We also prove that a fuzzy regular language accepted by an aggregated fuzzy automa-ton differs by a real number ? from the fuzzy regular language accepted by the original fuzzy automaton.An example is used to explain that there might not exist the greatest?-approximate bisimulation for a fuzzy automaton.And then,we provide a polynomial-time algorithm for computing all maximal ?-approximate bisimulations and discuss the conditions of the existence of the greatest ?-approximate bisimulation.3.Introducing similarity bisimulations for fuzzy automata and giving the approxi-mate minimization method of them:We introduce the notion of ?-similarity bisimulation-s for fuzzy automata by means of fuzzy similarity measures and study the approximate minimization of fuzzy automata with ?-similarity bisimulations.Comparing ?-similarity bisimulations for fuzzy automata with ?-approximate bisimulations,we can choose dif-ferent fuzzy similarity measures to obtain a-similarity bisimulations with different mean-ings.If and only if fuzzy similarity measures are induced by Godel implication,there exists the greatest ?-similarity bisimulation for a fuzzy automaton.If fuzzy similarity measures are induced by Lukasiewicz implication and ?-1-?,then ?-similarity bisim-ulations can be converted into ?-approximate bisimulations.However,as the methods of studying approximate minimization of fuzzy automata,?-approximate bisimulations for fuzzy automata are more accessible and applicable than ?-similarity bisimulations,and the aggregated fuzzy automata corresponding to ?-approximate bisimulations are more reasonable in structure than the aggregated fuzzy automata corresponding to ?-similarity bisimulations.4.Giving interval type-2 fuzzy weak regular languages and their minimization im-plementation:we define interval type-2 fuzzy weak regular languages and study their Pumping lemma and Myhill-Nerode theorem.With the help of Pumping lemma of inter-val type-2 fuzzy weak regular languages,we prove that the operation of complement of interval type-2 fuzzy languages is closed in the set of interval type-2 fuzzy weak regular languages,and others are not closed.For an interval type-2 fuzzy weak regular language,if it is weak-accepted by a given accessible deterministic interval type-2 fuzzy automaton,then we give a polynomial-time algorithm to construct a minimal deterministic interval type-2 fuzzy automaton weak-accepting it. |
PDF Full Text Request