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

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

作　　者：彭家寅[1] PENG Jia-yin(School of Mathematics and Information Science,Neijiang Normal University,Neijiang 641199,Sichuan,China)

机构地区：[1]内江师范学院数学与信息科学学院

出　　处：《山东大学学报（理学版）》2019年第5期112-126,共15页Journal of Shandong University(Natural Science)

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

摘　　要：引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。The concept of L-valued pushdown automation is introduced. The equivalence that an L-valued language can be accepted by L-valued pushdown automata in two different ways. It is pointed out that the L-valued regular language can be recognized by L-valued pushdown automata. Using the method of general subset-construction, we prove the fact that an L-valued pushdown automation can accept the same L-valued language by final states and by another L-valued pushdown automation, with crisp transition relation and L-valued final states at the same time. According to this equivalence, some algebraic level charac-terizations of L-valued context-free languages are established, and the closed properties of these L-valued languages are also proved in details under standard operative conditions. In addition, the concept of L-valued context free-grammar is proposed. An L-valued context free grammar with a classical start symbol is given, which is equivalent to the general L-valued context free grammar. Using this equivalence relation, we discuss that an arbitrary L-valued context free grammar are mutually equivalently constructed with an L-valued pushdown automation, respectively, and present that in the sense of complete residuated lattice-valued logic. We can use any of the leftmost derivation, rightmost derivation, Chomsky paradigm, and Greibach paradigm to generate an L-valued context free language.

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

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构] O153.1[自动化与计算机技术—计算机科学与技术]