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

• 作者: 李永明 赵菲
• 来源期刊: 计算机工程与科学
• 学科: 数学
• 关键词: 赋值幺半群 加权正则文法 加权自动机
• 年，卷（期）: 2016,（7）
• 所属期刊栏目: 软件工程
• 页码范围: 1405-1412
• 页数: 8页
• 分类号: O159
• 字数: 8969字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2016.07.016

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李永明	陕西师范大学数学与信息科学学院	165	505	12.0	16.0
2	赵菲	陕西师范大学数学与信息科学学院	4	11	1.0	3.0