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

摘要：

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

关键词： 自动机 加权正则文法 编程语言 赋值幺半群

作者: 赵菲 李永明

作者单位: 陕西师范大学数学与信息科学学院 陕西西安710119

会议类型: 国内会议

会议名称: 2015全国理论计算机科学学术年会

会议地点: 金华

会议语种:中文

页码: 1-13

在线出版日期: 2015-10-30（万方平台首次上网日期，不代表论文的发表时间）