Fuzzy pushdown automata based on complete residuated lattices: variants and computing powers

In this paper, we discuss fuzzy pushdown automata based on complete residuated lattices L with a fuzzy initial state, called L-valued pushdown automata. A concise proof of the equivalence between L-PDAs accepting fuzzy languages by final state (L-PDA(F)s) and by empty stack (L-PDA(sic)s) is given. The several types of L-PDA(F)s and L-PDA(sic)s with respect to initial and final states being crisp or not are classified. It's shown that those variants have same computing power. Next, we introduce the notion of fuzzy pushdown automata without epsilon-moves (L-PDA(-epsilon)s). We show that L-PDAs and L-PDA(sic)(-epsilon)s are equivalent as the acceptors of fuzzy languages except the empty string e. Finally, we study the relationships of L-PDAF(-epsilon)s and L-PDA(sic)(-epsilon)s.