格值下推自动机与格值上下文无关文法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (25): 34-38.

格值下推自动机与格值上下文无关文法

彭家寅1，2

1.四川省高等学校数值仿真重点实验室，四川内江 641100
2.内江师范学院数学与信息科学学院，四川内江 641100

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-09-01 发布日期:2011-09-01

Lattice-valued pushdown automata and lattice-valued context-free grammars

PENG Jiayin1，2

1.Key Laboratory of Numerical Simulation of Sichuan Province，Neijiang，Sichuan 641100，China
2.School of Mathematics and Information Science，Neijiang Normal University，Neijiang，Sichuan 641100，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-09-01 Published:2011-09-01

摘要/Abstract

摘要： 引入了格值下推自动机、格值上下文无关文法及它们的语言的概念，证明了格值下推自动机以两种不同方式接受的语言类的等价性，研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件，揭示了在一定条件下，格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性，证明了有理格值语言均被格值下推自动机识别。

关键词: 格半群, 格值下推自动机, 格值上下文无关文法, 格值语言, 格值Chomsky范式文法

Abstract: The concepts of lattice-valued pushdown automata，lattice-valued context-free grammars and their languages are proposed.The equivalent relation which a lattice-valued language can be accepted by lattice-valued pushdown automata in two different ways is proved.The equivalent conditions of three kinds of lattice-valued languages generated by lattice-valued Chomsky normal form grammar and lattice-valued context-free grammars and derivations of lattice-valued context-free grammars are investigated.It is revealed that under certain conditions the language accepted by lattice-valued pushdown automata is equivalent to that generated by a lattice-valued context-free grammar.It is indicated that each rational lattice-valued language is recognized by a lattice-valued pushdown automaton.

Key words: lattice-ordered monoid, lattice-valued pushdown automata, lattice-valued context-free grammar, lattice-valued language, Chomsky normal form grammar

彭家寅1，2. 格值下推自动机与格值上下文无关文法[J]. 计算机工程与应用, 2011, 47(25): 34-38.

PENG Jiayin1，2. Lattice-valued pushdown automata and lattice-valued context-free grammars[J]. Computer Engineering and Applications, 2011, 47(25): 34-38.

[1]	李斌，舒兰. 确定型格值有限自动机的最小化[J]. 计算机工程与应用, 2010, 46(32): 52-54.
[2]	雷红轩. 格值有限状态自动机的半群[J]. 计算机工程与应用, 2010, 46(25): 49-50.
[3]	冯甄玲. 一类格值自动机的极小化[J]. 计算机工程与应用, 2007, 43(34): 65-70.