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