MP/MP*: Option Informatique
Devoir d'informatique à rendre le jeudi 6 janvier 2005
Mots synchronisants



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.