Fuzzy automata with ɛ-moves compute fuzzy measures between strings

This paper introduces fuzzy automata with transitions by empty string (ɛ-moves), and shows their relationship with other classes of classical fuzzy automata. The ɛ-move represents a state change of the automaton without consuming any symbol of the input string. In approximate string matching, ɛ-moves allow to model the effect of the insertion of a symbol (one of the possible edit operations). We provide a fuzzy measure between strings based on the concepts of string alignments and fuzzy edit operations. The main contribution of this paper is to prove that a particular class of fuzzy automata with ɛ-moves computes those fuzzy measures without restricting the number of errors between the strings. Given a fuzzy measure, a building method for constructing the fuzzy automaton with ɛ-moves that computes it, is also proposed.