International Journal of Myhill Nerode Theorem for Fuzzy Automata (Min-max Composition)

Abstract. In this paper, Myhill Nerode theorem of finite automaton has been extended to fuzzy automaton where the composition considered is min-max composition. In the case of max-min composition, it has already been proved that if L is a fuzzy regular language, then for any α ∈ [0, 1], Lα = L (Dα (M)) [3]. In the case of max-product composition Lα is only a subset of L (Dα (M)). But still Myhill Nerode theorem has been extended to max-product composition [4]. In the case of max-average composition, Lα is not even contained in L (Dα (M)). This lead to lots of challenges and we had to resort to splitting to prove the analogue of Myhill Nerode Theorem for max-average composition. In a similar line, an attempt has been made in this paper to study the behavior of fuzzy automata under min-max composition and to prove the analogue of Myhill Nerode Theorem for min- max composition. An algorithm to compute L(s) for any string s is also developed