\begin{panneau}Deux automates finis ${\cal A}$ et ${\cal A}'$ (dŽterministes ou non) sont Žquivalents s'ils reconnaissent le m�me langage. S'ils ne sont pas Žquivalents, alors il existe des mots qui sont reconnus par l'un et pas par l'autre; un tel mot est un \emph{sŽparateur} de ${\cal A}$ et ${\cal A}'$. La longueur discriminante de ${\cal A}$ et ${\cal A}'$ est la longueur minimale d'un sŽparateur. L'objet de ce probl�me est d'Žvaluer, par deux mŽthodes, un majorant de la longueur discriminante de ${\cal A}$ et ${\cal A}'$ en fonction des nombres d'Žtats de ${\cal A}$ et ${\cal A}'$.\end{panneau}\begin{panneau}Rappelons que tout automate ayant $n$ Žtats est Žquivalent ˆ un automate dŽterministe complet ayant au plus $2^n$ Žtats. \end{panneau}\subsection*{Approche na•ve}\begin{question}Soit ${\cal A}$ un automate, dŽterministe ou non dŽterministe, avec $n$ Žtats. Montrez que $L(A)$ est vide si et seulement s'il ne contient aucun mot de longueur infŽrieure ou Žgale ˆ $n-1$. \end{question}\begin{question}Soit ${\cal A}$ un automate dŽterministe complet ayant $n$ Žtats. Donnez un automate ayant aussi $n$ Žtats qui reconna”t le complŽmentaire $\overline{L(A)}$ de $L(A)$ dans $\Alphabet^*$. Vous justifierez votre rŽponse.\end{question}\begin{question}Soient ${\cal A}$ et ${\cal A}'$ deux automates utilisant le m�me alphabet $\Alphabet$ avec respectivement $n$ et $n'$ Žtats. Donnez un automate ayant $n \times n'$ Žtats qui reconna”t $L(A) \cap L(A')$.Vous justifierez votre rŽponse.\end{question}\begin{question}Soient ${\cal A}$ et ${\cal A}'$ deux automates dŽterministes complets utilisant le m�me alphabet $\Alphabet$ avec respectivement $n$ et $n'$ Žtats. Montrez que si ${\cal A}$ et ${\cal A}'$ ne sont pas Žquivalents, il existe un mot de longueur au plus $n \times n' - 1$ qui est reconnu par l'un et non par l'autre, i.e. la longueur discriminante de ${\cal A}$ et ${\cal A}'$ est infŽrieure ou Žgale ˆ $n \times n' - 1$. \end{question}\begin{question}En dŽduire un majorant pour la longueur discriminante de deux automates non Žquivalents quelconques avec $n$ et $n'$ Žtats respectivement.\end{question}\begin{panneau}L'objectif de cette partie est de dŽmontrer que la longueur discriminante de deux automates dŽterministes non Žquivalents, ayant respectivement $n$ et $n'$ Žtats, est infŽrieure ou Žgale ˆ $n+n'-1$. \end{panneau}\begin{question}Montrez sur un exemple, avec un alphabet ˆ une seule lettre, qu'il existe des automates dŽterministes ${\cal A}$ et ${\cal A}'$ non Žquivalents et qui reconnaissent les m�mes mots de longueur strictement infŽrieure ˆ $n+n'-1$, o� $n$ (resp. $n'$) dŽsigne le nombre d'Žtats de ${\cal A}$ (resp. de ${\cal A}'$). Indication: les automates sont dŽterministes, mais rien ne les oblige ˆ �tre complets!\end{question}\subsection*{Approche plus fine} \begin{panneau}Soit $A = (\Alphabet,Q,\delta,i,F)$ un automate dŽterministe ˆ $n$ Žtats. Sans perte de gŽnŽralitŽ, nous supposons que $Q = \IntervalleDiscret{1}{n}$ et $i = 1$. Notons $(e_1,e_2,\ldots,e_n)$ la base canonique de l'espace vectoriel $\R^n$. Pour $i\in\IntervalleDiscret{1}{n}$, le vecteur $e_j$ est donc le vecteur de $\R^n$ dont toutes les composantes sont nulles sauf la $j$-ime qui vaut 1. Notons $\0$ le vecteur nul de $\R^n$. Pour chaque lettre $a$ de l'alphabet $\Alphabet$, dŽfinissons une application linŽaire $\varphi_a$ de $\R^n$ dans $\R^n$ comme suit: pour $j$ et $k$ appartenant ˆ $\IntervalleDiscret{1}{n}$, $\varphi_a(e_j) = e_k$ si $\delta(j,a) = k$; et $\varphi_a(e_j) = \0$ sinon. L'existence et l'unicitŽ de l'application $\varphi_a$ dŽcoulent du fait que ${\cal A}$ est dŽterministe et de la linŽaritŽ de $\varphi_a$. Soit $m = a_1 a_2 \ldots ak$ est un mot non vide de $\Alphabet^*$; nous noterons $\varphi_m =  \varphi_{a_k} \circ \ldots \circ \varphi_{a_1}$. En particulier, $\varphi_\mv$ est l'identitŽ de $\R^n$. Nous noterons $\displaystyle z = \sum_{f\in F} e_f$. Enfin, le produit scalaire des deux vecteurs $u$ et $v$ de $\R^n$ sera notŽ $u \cdot v$.\end{panneau}\begin{figure}[h]\begin{center}\setlength{\unitlength}{1.7pt}\begin{picture}(80,65)(0,0)\thinlines\letvertex A=(5,8)\letvertex B=(75,8)\letvertex C=(40,45)\drawinitialstate(A){$1$}\drawfinalstate(B){$2$}\drawfinalstate(C){$3$}\drawloop[t](C){$a$}\drawcurvededge(A,B){$a$}\drawcurvededge(B,A){$b$}\drawedge(A,C){$b$}\drawedge(C,B){$b$}\end{picture}\end{center}\end{figure}\begin{panneau}Sur l'exemple de la figure, nous avons $\varphi_a(e_1) = e_2$, $\varphi_a(e_2) = \0$, $\varphi_a(e_3) = e_3$, $\varphi_b(e_1) = e_3$, $\varphi_b(e_2) = e_1$, $\varphi_b(e_3) = e_2$ et $z = (0, 1, 1)$. Nous avons (entr'autres) les ŽgalitŽs $\varphi_{abb}(e_1) = e_3$, $\varphi_{ba}(e_3) = \0$ et $\varphi_{ba}(e_2) = e_2$.\end{panneau}\begin{question}Soient $m\in\Alphabet^*$ et $j,k\in\IntervalleDiscret{1}{n}$. Montrez qu'il existe un calcul d'origine $j$, d'extrŽmitŽ $k$ et d'Žtiquette $m$ si et seulement si $\varphi_m(e_j) = e_k$. \end{question}\begin{question}Soit $m\in\Alphabet^*$. Donnez les valeurs possibles du produit scalaire $\varphi_m(e_1) \cdot z$ et indiquez une condition nŽcessaire et suffisante portant sur ce produit scalaire pour que $m$ soit un mot reconnu par ${\cal A}$. \end{question}\begin{panneau}Dans la suite du probl�me, nous considŽrons, en plus de ${\cal A}$, un deuxi�me automate dŽterministe ${\cal A}' = (Q',\delta',i',F')$; $n'$ est le nombre d'Žtats de ${\cal A}'$; les vecteurs de la base canonique de $\R^{n'}$ sont notŽs $e'_j$; la fonction $\varphi_m'$ est dŽfinie comme $\varphi_m$, en rempla�ant les $e_j$ par les $e'_j$; et $\displaystyle z' = \sum_{f\in F'} e'_f$. \end{panneau}\begin{panneau}Soient $u$ et $v$ deux vecteurs appartenant respectivement ˆ $\R^n$ et $\R^{n'}$. Nous noterons $(u;v)$ le vecteur $w$ de $\R^{n+n'}$ obtenu en concatŽnant $u$ et $v$; plus prŽcisŽment, le vecteur $w$ est dŽfini par $w_i = u_i$ si $1²i²n$ et $w_i = v_{i-n}$ si $n+1²i²n+n'$. Par exemple, si $u = (0,1,0)$ et $v = (1,2)$, alors $(u;v)$ est le vecteur $(0,1,0,1,2)$. Nous noterons $E = (e_1; -e'_1)$; notez bien le signe ÇmoinsÈ. \end{panneau}\begin{panneau}Ë tout mot $m\in\Alphabet^*$, nous associons l'application linŽaire $\Phi_m$ de $\R^n$ dans $\R^n$ dŽfinie par $\Phi_ m \bigl( u;u' \bigr) = \bigl( \varphi_m(u);\varphi'_m(u') \bigr)$ pour tout $u \in \R^n$ et pour tout $u' \in \R^{n'}$; nous admettrons la linŽaritŽ de $\Phi_m$. Nous noterons $Z = (z;z')$.\end{panneau}\begin{question}Soit $m\in\Alphabet^*$; indiquez les valeurs possibles du produit scalaire $\Phi_m(E) \cdot Z$ et, selon ces valeurs, prŽcisez l'appartenance de $m$ ˆ $L(A)$ et $L(A')$. \end{question}\begin{panneau}Soit $k\in \N$; nous notons $V_k$ le sous-espace vectoriel de $\R^{n+n'}$ engendrŽ par la famille des vecteurs $\Phi_m(E)$ o� $m$ dŽcrit l'ensemble des mots de longueur au plus $k$ sur l'alphabet $\Alphabet$. En particulier, $V_0$ est engendrŽ par le vecteur $(e_1; -e'_1)$. \end{panneau}\begin{question}Pour $k³0$, montrez que $V_k$ est contenu dans $V_{k+1}$. \end{question}\begin{question}Soient $m\in\Alphabet^*$ et $a\in\Alphabet$. Montrez l'ŽgalitŽ $\Phi_{ma} = \Phi_a \circ \Phi_m$. \end{question}\begin{question}Soit $w \in V_k$ et $a \in \Alphabet$; montrez que $\Phi_a(w)$ appartient ˆ $V_{k+1}$. \end{question}\begin{question}Supposons qu'il existe $k³0$ tel que $V_k = V_{k+1}$; montrez l'ŽgalitŽ $V_{k+2} = V_{k+1}$. \end{question}\begin{question}Montrez qu'il existe un entier $h²n+n'-1$ tel que $V_k = V_h$ pour tout $k³h$. \end{question}\begin{question}Montrez que si ${\cal A}$ et ${\cal A}'$ ne sont pas Žquivalents, il existe un mot de longueur infŽrieure ou Žgale ˆ $n+n'-1$ qui est acceptŽ par l'un et pas par l'autre. Ceci prouve que $n+n'-1$ est un majorant de la longueur discriminante de ${\cal A}$ et ${\cal A}'$.\end{question}\begin{question}En dŽduire un majorant de la longueur discriminante de deux automates quelconques ayant $n$ et $n'$ Žtats respectivement.\end{question}\endinputNotations et terminologie Un alphabet $\Alphabet$ est un ensemble fini d'ŽlŽments appelŽs lettres. Un mot sur $\Alphabet$ est une suite finie de lettres de $\Alphabet$; le mot vide est not $\mv$. On dsigne par $\Alphabet^*$ l'ensemble des mots sur $\Alphabet$, y compris le mot vide. La longueur d'un mot $m$, notŽe $|m|$, est le nombre de lettres qui le composent. Un langage est une partie de $\Alphabet^*$. Un automate ${\cal A}$ est dŽcrit par une structure $(\Alphabet,Q,T,I,F$, o�:  $\Alphabet$ est un alphabet; $Q$ est un ensemble fini et non vide appelŽ ensemble des Žtats de ${\cal A}$; $T\subset Q \times \Alphabet \times Q$ est appelŽ l'ensemble des transitions; Žtant donnŽ une transition $(p, a, q) \in T$, on dit qu'elle va de l'Žtat $p$ ˆ l'Žtat $q$ et qu'elle est d'Žtiquette $a$; on pourra la noter $p \donne q$; $I\subset Q$ est l'ensemble des Žtats initiaux de ${\cal A}$; $F\subset Q$ est l'ensemble des Žtats finals de ${\cal A}$.On reprŽsente graphiquement l'automate ${\cal A}$ ainsi:  un tat $p$ est figur par un cercle marqu en son centre par p; si p appartient  I, cela est figur par une flche entrante sans origine; si un tat q appartient  F, cela est figur par une flche sortante sans but;  une transition $(p, a, q) \in T$ est figure par une flche allant de l'Žtat p vers l'Žtat q et tiquete par la lettre a.Un calcul $c$ de ${\cal A}$ est un chemin de la forme $p0 \to p1 2 \to p2 \ldots \to pk$, avec $pi 1 \to pi \in T$ pour $1  i  k$;  $p0$ est l'origine du calcul, $pk$ son extrŽmitŽ. L'Žtiquette de c est le mot form par la suite des Žtiquettes des transitions successives du chemin.Un calcul de ${\cal A}$ d'origine $p$, d'extrŽmitŽ $q$ et d'Žtiquette $m$ est dit russi si on a $p \in I$ et $q \in F$. Un mot $m\in\Alphabet^*$ est reconnu par ${\cal A}$ s'il est l'Žtiquette d'un calcul rŽussi. Le langage reconnu par ${\cal A}$, notŽ $L(A)$, est l'ensemble des mots reconnus par ${\cal A}$. Deux automates ${\cal A}$ et ${\cal A}'$ sont dits Žquivalents si on a $L(A ) = L(A')$. L'automate ${\cal A}$ est dit dŽterministe si $I$ ne contient qu'un ŽlŽment et si, pour tout $(p, a) \in Q \times \Alphabet$, il existe au plus un Žtat $q \in Q$ avec $(p, a, q) \in T$. L'automate ${\cal A}$ est dit complet si et seulement si, pour tout $p \in Q$ et tout $a\in\Alphabet$, il existe $q \in Q$ avec $(p,a,q) \in T$.