Congruence With The Grid Value Of The Weighted Moore Moore Machine Is Reduced

The theory of automata describes and provides a reliable mathematical model of calculation, and it is also based on algorithm description and analysis, complexity theory of computational, computability theory and so on. The weighted automata is a type of undetermined automata with weights. These weights can represent the operating expenses, resource consumption, time, and the probability of successful operation. And the weighted automata has shown great point of theoretical and practical on computer science, including algebra processing of classic automata, natural language processing, speech recognition and image compression. This pa-per is based on weighted automata theory, studying and discussing the congruence and minimization of weighted Moore machine and lattice-valued Moore machine in details. The main ideas of the paper as follows:1. On the basis of weighted automata theory, the paper studies some important properties of weighted Moore machine. Using algebra theory method, T.Petkovic in [1] studies the congruence and homomorphism of fuzzy finite automata. As an ex-tension of Ref.[1], firstly, it gives the definition of the congruence and homomorphism of weighted Moore machine, the homomorphism theorem in which congruence and homomorphism will be connected. secondly, it proofs the congruence relation form a complete lattice in weighted Moore machine. and finally, it gives the factor Moore machine of weighted Moore machine and the algorithm to find out the minimum states under the congruence relation.2. It shows the formal definition of the Moore machine (lattice-valued Moore machine for short) on the basis of complete residue lattice, discusses a series of properties of the lattice-valued Moore machine. And it gives the condition that a lattice-valued Moore machine is equivalence with its factor Moore machine. Then, it defines right invariant fuzzy equivalence over a lattice-valued Moore machine, in which the congruence of a lattice-valued Moore machine is a special case of right invariant fuzzy equivalence, and discusses that right invariant fuzzy equivalences of a lattice-valued Moore machine form a complete lattice. So there is the greatest right invariant fuzzy equivalence in each lattice-valued Moore machine and it become a theory basis for the minimization of lattice-valued Moore machine. At last, It further gives the algorithm and examples to find out the greatest right invariant fuzzy equivalence.Analogously, we have the left invariant fuzzy equivalence and the algorithm to find out the greatest left invariant fuzzy equivalence. For a lattice-valued Moore machine, if it is right reduced, then we can't continue the reduction of number of states, but it can be left reduced. A lattice-valued Moore machine will be in a minimization state after alternated reductions for limited steps. Finally, it illustrates that right-left alternated reduction is different with left-right alternated reduction, and the length of alternate reduction is also different.