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

doi:10.6040/j.issn.1671-9352.0.2018.060

摘要/Abstract

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

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

Abstract: 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.

Key words: complete residuated lattice-valued logic, L-valued pushdown automata, L-valued context free grammar, L-valued context free language

中图分类号:

TP301.1

彭家寅. 基于完备剩余格值逻辑的下推自动机与上下文无关文法[J]. 《山东大学学报(理学版)》, 2019, 54(5): 112-126.

PENG Jia-yin. Pushdown automata and content-free grammars based on complete residuated lattice-valued logic[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(5): 112-126.

参考文献

[1] HOPCROFT J E, ULLMAN J D. Introduction to automata theory, language, and computation[M]. New Yrok: Addison-Wesley, 1979.
[2] ALON N, DEWDNEY A, OTT T. Efficient simulation of finite automata by neural nets[J]. J Assoc Comput Mach, 1991, 38(2):498-514.
[3] 沈恩绍. 模型论逻辑与理论计算机科学[J]. 数学进展,1996,25(3):193-202. SHEN Enshao. Model theoretic logic and theoretical computer science[J]. Advance in Mathematics, 1996,25(3):193-202.
[4] BOOCH G, RUMBAUGH J, JACOBSON J. The unified modeling language user guide[M]. New York: Addison-Wesley, 1999.
[5] HOPCROFT J E, ULLMAN J D. Decidable and undecidable questions about automata[J]. Journal of the ACM, 1968, 15(2):317-324.
[6] WEE W G. On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification[M]. USA: Purdue University,1967.
[7] KANDEL A, LEE S C. Fuzzy switching and automata: theory and applications[M]. London: Grane Russak, 1980: 171-262.
[8] 付雯静, 韩召伟. 量化上下文无关语言的代数性质[J]. 计算机科学, 2017, 44(7):57-60. FU Wenjing, HAN Zhaowei. Algebraic properties of quantized context free languages[J]. Computer Science, 2017, 44(7):57-60.
[9] 彭家寅. 扰动值模糊有限自动机及其语言[J]. 模式识别与人工智能, 2016, 29(4):298-312. PENG Jiayin. Disturbing-valued fuzzy finite-state automata and their languages[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(4):298-312.
[10] 薛倩倩, 李永明. 格值模糊自动机及对应语言的分级[J]. 陕西师范大学学报(自然科学版), 2014,42(3):10-14. XUE Qianqian, LI Yongming. Classification of lattice valued fuzzy automata and corresponding languages[J]. Journal of Shaanxi Normal University(Natural Science Edition), 2014, 42(3):10-14.
[11] LEE E T, ZADEH L A. Note on fuzzy languages[J]. Information Sciences, 2015, 1(4):421-434.
[12] 付雯静, 韩召伟. 取值于赋值幺半群的加权下推自动机的代数性质[J]. 陕西师范大学学报(自然科学版), 2017, 45(3):9-16. FU Wenjing, HAN Zhaowei. Algebraic properties of weighted pushdown automata over valuation monoid[J]. Journal of Shaanxi Normal University(Natural Science Edition), 2017, 45(3):9-16.
[13] 王月, 李永明. 取值于赋值幺半群的加权上下文无关文法及其语言[J]. 模糊系统与数学, 2017,31(1):165-173. WANG Yue, LI Yongming. Weighted context free grammars over valuation monoid and their languages[J]. Fuzzy Systems and Mathematics, 2017, 31(1):165-173.
[14] 范艳焕, 耿生玲, 李永明. Pebble模糊有穷自动机和传递闭包逻辑[J]. 模糊系统与数学, 2015, 29(4):38-44. FAN Yanhuan, GENG Shengling, LI Yongming. Pebble fuzzy finite automata and transitive closure logic[J]. Fuzzy Systems and Mathematics, 2015, 29(4):38-44.
[15] 赵菲, 李永明. 取值于赋值幺半群的加权正则文法语言[J]. 计算机工程与科学, 2016, 38(7):1405-1412. ZHAO Fei, LI Yongming. Weighted regular grammars over valuation monoid[J]. Computer Engineering & Science, 2016, 38(7):1405-1412.
[16] SHU L. The relation between fuzzy 3 grammars and fuzzy finite automata[J]. Mathematical Application, 1989, 2(1):111-112.
[17] 柏明强. Fuzzy树自动机的等价性[J]. 四川师范大学学报(自然科学版),2009,32(1):13-16. BAI Mingqiang. The equivalence on two kinds of fuzzy tree automata[J]. Journal of Sichuan Normal University(Natural Science Edition), 2009, 32(1):13-16.
[18] 莫智文,彭家寅.模糊极小自动机与约简模糊自动机[J].四川师范大学(自然科学版),2002,25(6):585-587. MO Zhiwen, PENG Jiayin. Fuzzy minimal automaton and reduced fuzzy automaton[J]. Journal of Sichuan Normal University, 2002, 25(6):585-587.
[19] 邱道文. 基于完备剩余格值逻辑的自动机理论——I.拓扑刻画[J]. 中国科学(E辑:技术科学),2003, 33(2):137-146. QIU Daowen. Automata theory based on complete residuated lattice—valued logic I[J]. Science in China(Series E: Technologica), 2003, 33(2):137-146.
[20] 邱道文. 基于完备剩余格值逻辑的自动机理论——II.可逆性及同态[J]. 中国科学(E辑:技术科学),2003, 33(4):340-349. QIU Daowen. Automata theory based on complete residuated lattice—valued logic II[J]. Science in China(Series E: Technologica), 2003, 33(4):340-349.
[21] 彭家寅. 基于完备剩余格值逻辑的自动机与文法理论[J]. 模式识别与人工智能,2011,24(5):610-618. PENG Jiayin. Automata and grammars theory based on complete residuated lattice-valued logic[J]. Pattern Recognition and Artificial Intelligence, 2011, 24(5):610-618.
[22] 李永明. 格值自动机与语言[J]. 陕西师范大学学报(自然科学版),2003,31(4):1-6. LI Yongming. Lattice-valued automata and their languages[J]. Journal of Shaanxi Normal University(Natural Science Edition), 2003, 31(4):1-6.
[23] YING Mingsheng. Automata theory based on quantum logic I[J]. International Journal of Theoretical Physics, 2000, 39(4):985-995.
[24] YING Mingsheng. Automata theory based on quantum logic II[J]. International Journal of Theoretical Physics, 2000, 39(11):985-995.
[25] QIU Daowen. Automata theory based on quantum logic: some characterizations[J]. Information and Computation, 2004, 190(2):179-195.
[26] 李永明. 基于量子逻辑的有穷自动机与单体二阶量子逻辑[J]. 中国科学(F辑:信息科学),2009, 39(11):1135-1145. LI Yongming. Finite automata based on quantum logic and monadic second-order quantum logic[J]. Science in China(Series F: Information Sciences), 2009, 39(11):1135-1145.
[27] SHANG Y, LU X, LU R Q. Automata theory based on unsharp quantum logic[J]. Mathematical Structures in Computer Science, 2009, 19(4):737-756.
[28] 彭家寅. 基于Unsharp量子逻辑的自动机与文法理论[J]. 计算机工程与应用,2012, 48(28):57-60. PENG Jiayin. Automata and grammars theory based on unsharp quantum logic[J]. Computer Engineering and Applications, 2012, 48(28):57-60.
[29] KHOUSSAINOV B, NRRODE A. Automata theory and its applications[M]. Boston: Birkauser, 2001.
[30] 舒兰.识别Fuzzy上下文无关语言的下推自动机[J].电子科技大学学报,1992, 21(2):188-190. SHU Lan. Pushdown automata accepted Fuzzy context-free language[J]. Journal of UEST of China, 1992, 21(2):188-190.
[31] 彭家寅. Fuzzy下推自动机与Fuzzy上下文无关语言的关系[J]. 四川师范大学学报(自然科学版),2000, 23(1):27-30. PENG Jiayin. The relation between fuzzy pushdown automata and fuzzy context-free languages[J]. Journal of Sichuan Normal University(Natural Science), 2000, 23(1):27-30.
[32] 韩召伟,李永明. 基于量子逻辑的下推自动机与上下文无关文法[J]. 软件学报,2010, 21(9):2107-2117. HAN Zhaowei, LI Yongming. Pushdown automata and context-free grammars based on quantum logic[J]. Journal of Software, 2010, 21(9):2107-2117.
[33] 彭家寅. 格值下推自动机与格值上下文无关文法[J]. 计算机工程与应用,2011,47(25):34-38. PENG Jiayin. Lattice-valued pushdown automata and lattice-valued context-free grammars[J]. Computer Engineering and Applications, 2011, 47(25):34-38.
[34] PAVELKA J. On fuzzy logic I: many-valued rules of inferences[J]. Z Math Logik Grundlagen Math,1979, 25:45-52.
[35] PAVELKA J. On fuzzy logic II: enriched residuated lattices and semantics of propositional calcui[J]. Z Math Logik Grundlagen Math, 1979, 25:119-134.
[36] PAVELKA J. On fuzzy logic III: semantical completeness of some many-valued propositional calculi[J]. Z Math Logik Grundlagen Math, 1979, 25:447-464.
[37] LI Y M, LI Z H. Free semilattices and strongly free semilattices generated by partially ordered sets[J]. Northeastern Mathematical Journal, 1993, 9(3):395-366.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed