山东大学学报(理学版)

作者：彭家寅

单位：内江师范学院数学与信息科学学院, 四川 内江 641199

关键词：完备剩余格值逻辑,L-值下推自动机,L-值上下文无关文法,L-值上下文无关语言,

基金：教育部与四川省数学与应用数学专业综合改革资助项目(ZG0464;01249);国家自然科学基金资助项目(11071178、11671284);四川省科技厅重大前沿资助项目(2017JY0197);四川省教育厅科研创新团队基金资助项目(15TD0027)

引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。

来源：2019年第5期

《山东大学学报(理学版)》期刊编辑部

查看山东大学学报(理学版)杂志2019年第5期