取值于赋值幺半群的加权正则文法语言

计算机工程与科学

取值于赋值幺半群的加权正则文法语言

赵菲，李永明

（陕西师范大学数学与信息科学学院，陕西西安 710119 ）

收稿日期:2015-12-20 修回日期:2016-03-13 出版日期:2016-07-25 发布日期:2016-07-25
基金资助:
国家自然科学基金(11271237,61228305)

Weighted regular grammars over valuation monoid

ZHAO Fei，LI Yong-ming

（College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China）

Received:2015-12-20 Revised:2016-03-13 Online:2016-07-25 Published:2016-07-25

摘要/Abstract

摘要：

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义，讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机（WFA）的关系。证明了在赋值幺半群上，已知一个加权正则文法或加权类正则文法，分别存在一个WFA与之等价。定义了可分配的赋值幺半群，证明了在可分配的赋值幺半群上已知一个WFA，存在一个加权正则文法和加权类正则文法与之等价，即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价，并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。

关键词: 赋值幺半群, 加权正则文法, 加权自动机

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

赵菲，李永明. 取值于赋值幺半群的加权正则文法语言[J]. 计算机工程与科学.

ZHAO Fei，LI Yong-ming. Weighted regular grammars over valuation monoid [J]. Computer Engineering & Science.