Abstract:

Regular grammars are necessary tools for the analysis of automata.  We introduce the concepts of weighted regular grammars and weighted similar regular grammars over valuation monoid, discuss the relationships among weighted regular grammar, weighted similar regular grammar and weighted finite automata (WFA). We show that for a given weighted regular grammar or a weighted similar regular grammar, their there is a WFA which is equivalent to the weighted regular grammar or the weighted similar regular grammar.  We define the concept of distributable valuation monoids  and prove that on a distributable valuation monoid  for a given WFA  there is a weighted regular grammar or a weighted similar regular grammar, and they generate the same languages. Examples show that the distributivity of valuation monoid is not a given WFA  and we can find a weighted regular grammar or a weighted similar regular grammar which is equivalent to the WFA.

Key words: valuation monoid, weighted regular grammar, weighted finite automata