On the Identification of a Finite Automaton by Its Input and Output Sequences in Case of Distortions

A method is proposed for checking whether a pair of observed distorted sequences can correspond to the true input and output sequences of a reference automaton, provided that the initial state of the automaton is unknown, and the proportion of deletions, insertions, and replacements of symbols is small. An example of applying the method for the case of a generalized shift register is given. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.