Pumping lemma in automata theory based on complete residuated lattice-valued logic: A note

Automata theory based on complete residuated lattice-valued logic (called L-valued automata) was established in (Qiu, Automata theory based on completed residuated lattice-valued logic (I), Science in China (F) 44(6) (2001) 419–429; Qiu, Automata theory based on completed residuated lattice-valued logic (II), Science in China (F) 45(6) (2002) 442–452). In this note, we deal with the pumping lemma in L-valued automata theory. After recalling some preliminaries related to complete residuated lattices and L-valued automata, we define a number of L-valued accepting predicates. In particular, the pumping lemma for L-valued automata theory is set up. We show that if those related L-valued predicates are defined by using connective ∧ instead of &, then the pumping lemma may not hold again. Furthermore, we investigate the L-valued automata with ε-transitions, and present the equivalence between the L-valued automata without ε-transitions and those with ε-transitions. Finally, a number of related questions is addressed.