Un mot m est synchronisant pour un automate fini déterministe complet A si l'état q.m dans lequel on se trouve après lecture du mot m ne dépend pas de l'état q dans lequel on commence cette lecture.
Cette notion n'est pas que de pure théorie: lorsque l'on démarre un ordinateur, celui-ci se place dans un état particulier, toujours le même: ceci nous semble évident, mais pose des problèmes pratiques sérieux.
Nous étudierons quelques propriétés de l'ensemble des mots synchronisants d'un a.f.d.c.
En 1969, Cerny a émis la conjecture suivante: si un a.f.d.c. à n états possède un mot synchronisant, alors il en possède un de longueur au plus (n-1)^2. Nous prouverons cette conjecture dans un cas particulier.
Les idées essentielles de ce sujet proviennent de l'article de Jean-Eric Pin intitulé Algèbre linéaire et automates finis.