基于完备剩余格值逻辑的下推自动机与上下文无关文法

彭家寅

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

发布日期:2019-05-09

作者简介:彭家寅(1962— ),男,博士,教授,研究方向为量子通信. E-mail:pengjiayin62226@163.com
基金资助:教育部与四川省数学与应用数学专业综合改革资助项目(ZG0464;01249);国家自然科学基金资助项目(11071178、11671284);四川省科技厅重大前沿资助项目(2017JY0197);四川省教育厅科研创新团队基金资助项目(15TD0027)

Pushdown automata and content-free grammars based on complete residuated lattice-valued logic

PENG Jia-yin

School of Mathematics and Information Science, Neijiang Normal University, Neijiang 641199, Sichuan, China

Published:2019-05-09

摘要/Abstract

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


PDF全文下载地址:

http://lxbwk.njournal.sdu.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3085