Computer Engineering & Science
Previous Articles Next Articles
ZHAO Fei,LI Yong-ming
Received:
Revised:
Online:
Published:
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
ZHAO Fei,LI Yong-ming. Weighted regular grammars over valuation monoid [J]. Computer Engineering & Science.
0 / / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://joces.nudt.edu.cn/EN/
http://joces.nudt.edu.cn/EN/Y2016/V38/I07/1405