10.3969/j.issn.1007-130X.2016.07.016
取值于赋值幺半群的加权正则文法语言
正则文法是研究自动机的重要工具.引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系.证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价.定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件.
赋值幺半群、加权正则文法、加权自动机
38
O159(代数、数论、组合理论)
国家自然科学基金11271237,61228305
2016-08-30(万方平台首次上网日期,不代表论文的发表时间)
共8页
1405-1412