付雯静, 韩召伟*
(陕西师范大学 数学与信息科学学院, 陕西 西安 710119)
韩召伟,男,副教授。E-mail:hanzw888@snnu.edu.cn
摘要:
引入取值于赋值幺半群的加权下推自动机、标准型加权下推自动机的定义,证明了在双幺赋值幺半群框架下,加权下推自动机与标准型加权下推自动机相互等价,且以终态方式与以空栈方式识别语言的加权下推自动机能够识别相同的形式幂级数;在Cauchy双幺赋值幺半群上,加权上下文无关语言对于和、连接、正克林闭包运算封闭。结果表明加权下推自动机的诸多性质并不依赖于赋值幺半群的分配律和结合律。
关键词:
赋值幺半群; 双幺赋值幺半群; 加权下推自动机; 加权上下文无关语言
文章编号:
1672-4291(2017)03-0009-08doi:10.15983/j.cnki.jsnu.2017.03.133
基金项目:
国家自然科学基金(11401361,11226266);中央高校基本科研业务费专项资金(GK201402002);陕西省教育厅自然科学专项科研计划(16JK1373)