\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}\SimpleEtoile
Montrez 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}\DoubleEtoile
Avec 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