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

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

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