Dans ce sujet, on s’intéresse à un problème de recherche de séquence particulière dans un automate à états fini. Un tel automate est constitué d’états et de transitions entre ces états. Chaque transition est associée à un symbole de lecture et un symbole observé. À chaque itération, la machine est dans un certain états. Elle lit un symbole x sur une bande en entrée, utilise la transition quittant s ayant le symbole de lecture x et on observe alors le second symbole de cette transition. Si on considère l'automate ci-contre, si l’automate est dans l’état D et si la bande en entrée contient le mot 11001 alors en suivant les transitions, on se retrouve dans l’état A et on observe le mot 11110.
Entre autres, on s’intéresse aux séquences synchronisantes et aux séquences distinctives. Un mot est synchronisant s’il permet de déterminer, à l’issue de la lecture du mot de la bande en entrée, dans quel état se trouve la machine, quel que soit l’état dans lequel elle se trouvait initialement. Par exemple, dans l’automate ci-dessus, le mot 111 est synchronisant car quel que soit l’état de départ, l’automate se retrouve dans l’état A. Un mot est distinctif s’il permet, à l’aide de l’observation associée, de dire dans quel état se trouvait la machine avant la lecture du mot. Par exemple, ci-dessus, le mot 111 est également distinctif. Car le mot observé sera différent selon qu’on est parti de l’état A (mot 111), B (mot 011), C (mot 101) ou D (mot 110).