The Remaining Fuzzy Finite Automata

Automata are simple mathematical models of computation. They play an im-portant role in computer science. The minimization of finite automata is one of the most important research fields in automata theory. Some effective algorithms have been obtained about the minimization of deterministic finite automata(DFA), but the minimization of non-deterministic finite automata(NFA) is a hard problem in computation theory. Residual finite automata(RFA) is a special class of NFA based on Myhill-Nerode theorem, RFA plays a very important role in the process of the minimization of NFA, and get a new way to study the minimization of automata.The concept of fuzzy sets was introduced by Zadeh in1965, and was applied to automata theory by Wee in1967. Since then, fuzzy automata have been extensively studied. Fuzzy finite automata can be considered as an extended model which contains some kind of fuzzy and inaccurate concept, such as "about"、"high" or "low", which are often used in natural language. Similar to classical automata, the minimization of fuzzy finite automata is still one of the most important problems. Although the minimization of deterministic fuzzy finite automata has got some very good results, the minimization problem of non-deterministic fuzzy finite automata still needs to be studied.Since residual automata play a very important role in the study of the min-imization of classical automata, we consider the minimization of fuzzy automata by using similar methods. This paper define an important type of fuzzy finite automata(LFA)-fuzzy residual finite automata(LRFA). LRFAs are special LFAs, DFAs are special LRFAs. The main works of this paper are as follows:1. We introduce the concept of fuzzy residual language(LRL), discuss the basic operation and basic properties of LRL, give the method to construct the minimal DLFA by LRL. And then, we define the LRFA combined with the definition of LRL, discuss some important properties of LRFA. Moreover, we connect the LRFA with the RFA by A-cut, i.e., the λ-cut set of an LRFA is a RFA.2. We discuss the minimization problem of LRFA. First, we give the notions of saturation and reduction operator of LFA, discuss some important properties of two operators. In particular, we give a method to get an LRFA from an LRFA by saturation or reduction operator. Second, we define the standard LRFA based on above two operators, prove that the canonical LRFA has a minimal number of states. Finally, we prove that the canonical LRFA have fewer number of states than that of the minimal DLFA, discuss the relationship among DLFA、LRFA and LFA, give a algorithm to translate an LFA into an LRFA based on the method which translate an LFA into a DLFA.