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

计算机工程与科学

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

赵菲，李永明

（陕西师范大学数学与信息科学学院，陕西西安 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.

参考文献［3］

［1］	Schutzenberger M P. On the difinition of a family of automata［J］. Journal of Symbolic Logic, 1969,34（2）:245-270．
［2］	Hopcroft J E, Motwani R, Ullman J D. Automata theory, languages and computation［M］. Beijing: China Machine Press,2008．(in Chinese)
［3］	Li Yong-Ming. Lattice-valued automata and their language［J］.Journal of Shaanxi Normal University,2003，31（4）:1-6.(in Chinese)
［4］	Li Y M, Pedrycz W. Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids［J］.Fuzzy Sets and Systems,2005, 156(1):68-92．
［5］	Li Y M. Regular expressions with truth values in lattice-ordered monoid and their languages［C］∥Proc of IEEE 2004 9th Annual Meeting, 2004:572-577．
［6］	Sheng L,Li Y M. Regular grammars with truth values in lattice-ordered monoid and their languages［J］. Soft Comput, 2006,10(2):79-86.
［7］	Droste M,Kuich W,Vogler H. Handbook of weighted automata［M］. Berlin Heidelberg:Springer-Verlag,2009:313-330．
［8］	Chatterjee K, Doyen L, Henzinger T A. Quantitative langauaes［J］.ACM Transactions on Computational Logic, 2010,11(4):1．
［9］	Droste M, Meinecke I. Weighted automata and regular expressions over valuation monoid［J］.International Journal of Foundations of Computer Science, 2011,22（8） :1829-1844．
	附中文参考文献：
［2］	Hopcroft J E,Motwani R,Ullman J D. 自动机理论、语言、计算导论［J］.北京:机械工程出版社,2008．
［3］	李永明. 格值自动机与语言［J］.陕西师范大学学报,2003,31(4):1-6．