A Weighted Regular Grammar Language Study Of Valued Semigroups

Automata theory is a simple mathematical model of computation theory, and it is the basis of studying the problems such as computation, the algorithm descrip-tion and analysis, and computational complexity theory. In the theory of automata, an important research topic is the relationship between automata and grammars. In classical automata theory, deterministic finite automata, nondeterministic finite automata, regular grammars, regular expressions are equivalent. Weighted finite automata are the generalization of classical automata, and they have the weight of distance, cost, resource consumption, and so on, which form the algebraic structure-semiring. In 2011, M.Droste, I.Meinecke put forward the concept of valuation monoid, which generalizes the concept of semiring, and researched the problems of weighted automata on a valuation monoid.In this paper, we study the relationship between weighted automata and weighted regular grammars. We introduce the notions of weighted regular grammars and weighted similar regular grammars over valuation monoid, discuss the relationships of weighted regular grammar, weighted similar regular grammar and weighted finite automaton, the main work is as follows:1. We give the concepts of distributable valuation monoid, weighted regular grammars, and weighted similar regular grammars over valuation monoid, show the equivalence of the weighted regular grammar and weighted automaton. We prove that, on a valuation monoid, for a given weighted regular grammar or a weighted similar regular grammar, their is a weighted automaton which is equivalent to the weighted regular grammar or the weighted similar regular grammar, we also prove that on a distributable valuation monoid, for a given weighted automaton, their is a weighted regular grammar or a weighted similar regular grammar such that they generate the same languages, then we get the equivalence of weighted regular grammar, weighted similar regular grammar and weighted automaton on a distributable valuation monoid. Furthermore, we give examples to show that distributivity is not necessary for the equivalence of weighted regular grammar, weighted similar regular grammar and weighted automaton.2. We define the valuation monoid which has an unit element, and give the difinitions of weighted deterministic finite automata, deterministic weighted regular grammars, deterministic weighted similar regular grammars. By using the method of construction, constructing, we prove that on a valuation monoid which has an unit element, deterministic weighted regular grammars and weighted deterministic finite automata are equivalent, deterministic weighted similar regular grammars and weighted deterministic finite automata are equivalent.