Lattice-valued pushdown automata and lattice-valued context-free grammars
Peng Jia-yin · Computer Engineering and Applications Journal · 2011
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.