We focus here on the search for sequences in finite state machines. Such a machine contains states and transitions between states. Each transition is associated with an input symbol and an output symbol (observation). At each iteration, the machine is in a state s, it reads an input symbol x and use the transition leaving s containing the input symbol x. We can then observe the output symbol of the transition. For instance, on the machine on the right, if we start in the state D, and if the input word is 11001, then we obseve 11110.
We are particularly interested in synchronizing and distinguishing sequences. A sequence is synchronizing if, whatever the initial state is, the final state is the same. In the example, the word 111 is synchronizing as, whatever the initial state is, the final state is always A. A sequence is distinguishing if, given the output observation, we can deduce the initial state in which were the machine. In the example, the word 111 i distinguishing as the observation is distinct for every initial state : A (word 111), B (word 011), C (word 101) and D (word 110)