The paper deals with the problem of synthesizing detection tests for discrete devices with memory represented by a mathematical model of fuzzy automaton. In previously published works methods for solving a similar problem for two types of fuzzy automata (linear and with finite memory) were proposed. These methods were based on the use of their peculiarity that is their function law linearity. In contrast to “linear” automata, this paper considers arbitrary fuzzy automata defined in the form of fuzzy graphs and in tabular form. It is assumed that the fuzzy functioning of the automaton is manifested in the necessity of choosing alternative trajectories of motion at some automaton state transitions. The concept of test construction methods for arbitrary fuzzy automata based on the transformation of the model of a given automaton in the form of a fuzzy graph into a crisp graph is proposed. Such transformation is performed by the algorithm proposed in the paper. It is proved that any fault-detecting test in the resulting crisp graph (automaton) detects unambiguously its corresponding fault in the given fuzzy graph (automaton).