\section{Mots synchronisants, automates synchronisables}\begin{panneau}Dans tout le problme, $\Alphabet$ est un alphabet contenant au moins deux lettres. Soit ${\cal A} = (Q,\delta)$ un a.f.d.c. dont nous ne spŽcifions ni l'Žtat initial, ni l'ensemble des Žtats finals; nous noterons $q \cdot m$ pour $\delta^*(q,m)$. Au mot $m\in\Alphabet^*$, nous associons la fonction $\mmm : q\in Q \mapsto q \cdot m$; le \emph{rang} de $m$ est $\rho(m) = |\mmm(Q)|$. \end{panneau}\begin{question}Existe-t-il des mots de rang nul?\end{question}\begin{question}Soient $m_1$ et $m_2$ deux mots; notons $m = m_1 m_2$. Quelle relation existe-t-il entre les fonctions $\mmm_1$, $\mmm_2$ et $\mmm$?\end{question}\begin{question}Soient $u$, $v$ et $m$ trois mots. Montrez que $\rho(umw) ˛ \rho(m)$.\end{question}\begin{panneau}Soit $m\in\Alphabet^*$. Nous dirons que $m$ est un mot \emph{synchronisant} de ${\cal A}$ s'il est de rang~1, ce qui revient ˆ dire que la fonction $\mmm$ est constante. ${\cal A}$ est \emph{synchronisable} s'il admet au moins un mot synchronisant. Illustrons ces dŽfinitions par un exemple: \begin{figure}[h]\begin{center}\setlength{\unitlength}{1.7pt}\begin{picture}(50,35)(0,0)\thinlines\letvertex A=(5,8)\letvertex B=(45,8)\drawstate(A){$1$}\drawstate(B){$2$}\drawloop[t](A){$b$}\drawcurvededge(A,B){$a$}\drawcurvededge(B,A){$a,b$}\end{picture}\caption{l'automate ${\cal A}_2$}\label{automate-synchronisable-deux}\end{center}\end{figure}\noindent$b$ est un mot synchronisant de l'automate ${\cal A}_2$; c'est d'ailleurs le plus court. Nous noterons $\Sync({\cal A})$ l'ensemble des mots synchronisants de l'automate ${\cal A}$.\end{panneau}\begin{question}DŽterminez $\Sync({\cal A}_2)$.\end{question}\begin{panneau}Soient ${\cal A}$ un automate et $m$ un mot; nous dirons que $m$ est injectif pour ${\cal A}$ lorsque la fonction $\mmm$ l'est; ceci revient ˆ dire que $\rho(m) = n$. Clairement, $\mv$ est injectif. Pour l'automate ${\cal A}_2$, la lettre $a$ est injective et la lettre $b$ ne l'est pas.\end{panneau}\begin{question}Soient ${\cal A}$ un automate synchronisable et $m$ un mot synchronisant de ${\cal A}$, de longueur minimale. Montrez que ni la premire lettre, ni la dernire lettre de $m$ ne sont injectives pour ${\cal A}$.\end{question}\begin{question}Quels sont les mots injectifs pour l'automate ${\cal A}_3$ ci-dessous ?\begin{figure}[h]\begin{center}\setlength{\unitlength}{1.7pt}\begin{picture}(50,60)(0,0)\thinlines\letvertex A=(5,8)\letvertex B=(25,35)\letvertex C=(45,8)\drawstate(A){$1$}\drawstate(B){$2$}\drawstate(C){$3$}\drawloop[l](A){$b$}\drawloop[t](B){$b$}\drawcurvededge(A,B){$a$}\drawcurvededge(B,C){$a$}\drawcurvededge(C,A){$a,b$}\end{picture}\caption{l'automate ${\cal A}_3$}\label{automate-synchronisable-trois}\end{center}\end{figure}\end{question}\begin{question}Montrez que l'automate ${\cal A}_3$ est synchronisable; vous dŽterminez le(s) mot(s) synchronisants de longueur minimale de cet automate.\end{question}\begin{question}\label{sync-ideal} Montrez que $\Sync({\cal A}) = \Alphabet^* \Sync({\cal A}) \Alphabet^*$.\end{question}\begin{question}Soient $s$ et $t$ deux Žtats de ${\cal A}$. Notons $L_{s \to t}$ le langage contituŽ des mot $m$ tels que $s \cdot m = t$. Rappelez brivement pourquoi $L_{s \to t}$ est rationnel.\end{question}\begin{question}\SimpleEtoileMontrez que $\Sync({\cal A})$ est rationnel.\end{question}\begin{question}Supposons $\Sync({\cal A})$ synchronisable. En observant l'action de $\mmm$ sur $Q^n$, montrez qu'il existe un mot synchronisant de longueur strictement infŽrieure ˆ $n^n$.\end{question}\begin{question}\DoubleEtoileAvec une autre action, amŽliorez le rŽsultat prŽcŽdent en montrant qu'il existe un mot synchronisant de longueur strictement infŽrieure ˆ $2^n-n$.\end{question}\endinput