\begin{question}\label{automate-reduit} Soient $i$ et $f$ deux objets distincts, n'appartenant pas ˆ $Q$. Notons $Q' = Q \cup \{i{,}f\}$ et $\delta'$ la rŽunion de $\delta$ et des deux ensembles suivants: \begin{itemize} \item $\delta_1$ est l'ensemble des transitions $(i,x,q)$ telles qu'il existe une transition $(j,x,q)$ de ${\cal A}$ avec $j\in I$; \item $\delta_2$ est l'ensemble des transitions $(q,x,f)$ telles qu'il existe une transition $(q,x,g)$ de ${\cal A}$ avec $g\in F$. \end{itemize} \noindent Remarquons que l'intersection de ces deux ensembles peut ne pas tre vide, s'il existe une transition menant d'un Žtat de $I$ ˆ un Žtat de $F$; ceci revient ˆ dire que ${\cal A}$ reconna”t au moins un mot de longueur~1. DŽfinissons alors ${\cal A}' = (Q',\delta',\{i\},\{f\})$. Il est clair que les propriŽtŽs concernant $i$ et $f$ sont vŽrifiŽes. Il reste ˆ montrer que ${\cal A}'$ reconna”t le mme langage que ${\cal A}$. \smallskip \noindent ¥ Soit $x\in\Alphabet$; $x$ est reconnu par ${\cal A}$ ssi il existe une transition $(q,x,q')$ de ${\cal A}$ telle que $q\in I$ et $q' \in F$; mais ceci revient ˆ dire que ${\cal A}'$ possde la transition $(i,x,f)$ ou encore que $x$ est reconnu par ${\cal A}'$. \smallskip \noindent ¥ Soit $u$ de longueur $n³2$, reconnu par ${\cal A}$. $u$ est l'Žtiquette d'un calcul rŽussi de ${\cal A}$, qui passe par les Žtats $q_0,q_1,\ldots,q_{n-1},q_n$ avec $q_0\in I$ et $q_n\in F$. Alors $u$ est l'Žtiquette d'un calcul de ${\cal A}'$ qui passe successivement par les Žtats $i,q_1,\ldots,q_{n-1},f$. Ce calcul est donc rŽussi: par suite, $u$ est reconnu par ${\cal A}'$. \smallskip \noindent ¥ Soit $u$ de longueur $n³2$, reconnu par ${\cal A}'$. $u$ est l'Žtiquette d'un calcul rŽussi $i,q_1,\ldots,q_{n-1},f$. De par la construction de ${\cal A}'$, il existe $q_0\in I$ et $q_n\in F$ tels que les transitions $(q_0,u_1,q_1)$ et $(q_{n-1},u_n,q_n)$ appartiennent ˆ $\delta$. Donc $u$ est l'Žtiquette d'un calcul de ${\cal A}$ qui passe successivement par les Žtats $q_0,q_1,\ldots,q_{n-1},q_n$. Ce calcul est donc rŽussi: par suite, $u$ est reconnu par ${\cal A}$. \end{question} \begin{question}\label{langage-egal} Un calcul de ${\cal A}_{\mathrm{eq}}$ de longueur non nulle est de l'une des deux formes suivantes: $1 \donne{a^n} 1$ avec $n>0$; ou $1 \donne{a^n} 1 \donne{b} 2 \donne{b^q}$ avec $n³0$ et $q³0$. Les calculs rŽussis sont ceux du deuxime type, de poids total nul; ceci Žquivaut ˆ l'ŽgalitŽ $p=q+1$. Donc les Žtiquettes des calculs rŽussis sont les mots de la forme $a^n b^n$ avec $n>0$. \end{question} \begin{question} Les mots de $M_{\mathrm{diff}}$ sont de trois types: \begin{itemize} \item ceux de la forme $a^p$ avec $p>0$; \item ceux de la forme $a^p b^q$ avec $p>q>0$; \item ceux de la forme $b^q$ avec $q>0$; \item ceux de la forme $a^p b^q$ avec $q>p>0$. \end{itemize} \noindent Nous allons montrer que $M_{\mathrm{diff}}$ est le langage reconnu par le $\Z$-automate de la figure~\ref{automate-different}: \begin{figure}[h] \begin{center} \setlength{\unitlength}{1.7pt} \begin{picture}(180,60)(0,0) \thinlines \letvertex A=(85,25) \letvertex C=(45,25) \letvertex D=(05,25) \letvertex E=(125,25) \letvertex F=(165,25) \drawinitialstate[b](A){$1$} \drawstate(C){$2$} \drawstate(D){$3$} \drawstate(E){$4$} \drawstate(F){$5$} \drawedge(A,C){$(a,0)$} \drawloop[b](C){$(a,1)$} \drawloop[t](C){$(a,0)$} \drawedge(C,D){$(b,-1)$} \drawloop[b](D){$(b,-1)$} \drawedge[r](A,E){$(a,1)$} \drawloop[b](E){$(a,1)$} \drawedge[r](E,F){$(b,0)$} \drawloop[b](F){$(b,-1)$} \drawloop[t](F){$(b,0)$} \setprofcurve{+20} \drawcurvededge[l](A,F){$(b,0)$} \end{picture} \end{center} \caption{un $\Z$-automate reconnaissant $M_{\mathrm{diff}}$} \label{automate-different} \end{figure} \noindent Justifions cette affirmation. Les calculs de $M_{\mathrm{diff}}$ ont une longueur au moins Žgale ˆ 1; nous pouvons les sŽparer en quatre types, selon les Žtats traversŽs: \begin{itemize} \item un calcul qui se termine dans l'Žtat 2 est rŽussi ssi il a pour Žtiquette $a^p$ avec $p>0$ et n'emprunte pas la boucle $2 \donne{(a,1)} 2$; \item un calcul qui se termine dans l'Žtat 3 est rŽussi ssi il a une Žtiquette de la forme $a^{q+n} b^q$ o $n>0$ est le nombre de transitions ŽtiquetŽes par le couple $(a,0)$; \item un calcul qui ne passe pas par l'Žtat 4 se termine dans l'Žtat 5 est rŽussi ssi il a une Žtiquette de la forme $b^q$ avec $q>0$ et n'emprunte pas la boucle $5 \donne{(b,-1)} 5$; \item un calcul qui passe par l'Žtat 4 et se termine dans l'Žtat 5 est rŽussi ssi il a une Žtiquette de la forme $a^p b^{p+n+1}$ o $n³0$ est le nombre de passages dans la boucle $5 \donne{(b,0)} 5$. \end{itemize} \noindent Ceci termine la preuve. \end{question} \begin{question}\label{rat-implique-Zrat} D'aprs le rŽsultat de la question~\ref{automate-reduit}, nous pouvons supposer $I = \{i\}$ et $F = \{f\}$. DŽfinissons ${\cal B} = (Q,\delta',i)$ o $\delta'$ est la partie de $Q \times \{e,g,g^{-1} \}$ dŽfinie par les rgles suivantes: \begin{itemize} \item si $q' \ne f$, alors $(i,x,g,q') \in \delta'$ ssi $(i,x,q') \in \delta$; \item si $q \ne i$ et $q' \ne f$, alors $(q,x,e,q') \in \delta'$ ssi $(q,x,q') \in \delta$; \item si $q \ne i$, alors $(q,x,g^{-1},f) \in \delta'$ ssi $(q,x,f) \in \delta$; \item $(i,x,e,f) \in \delta'$ ssi $(i,x,f) \in \delta$. \end{itemize} \noindent Les calculs rŽussis de ${\cal B}$ sont de deux sortes: ceux de longueur 1, rŽduits ˆ une transition $i \donne{(x,e)} f$; et ceux de longueur supŽrieure ˆ 1, composŽs d'une transition $i \donne{(x,g)} q$, suivie de zŽro, une ou plusieurs transitions de poids $e$, suivies d'une transition $q' \donne{(y,g^{-1})} f$. Il est clair que l'ensemble des Žtiquettes de ces calculs est identique ˆ l'ensemble des Žtiquettes de calculs rŽussis de ${\cal A}$. \end{question} \begin{question} ${\cal A} = (Q,\delta,i)$. DŽfinissons successivement: \begin{itemize} \item $Q' = Q \times G$; \item $i' = (i,e)$ o $e$ est le neutre de $G$; \item $F' = Q \times \{e\}$; \item enfin $\bigl( (q,g),x,(q',g') \bigr)$ appartient ˆ $\delta'$ ssi $(q,x,g^{-1} g',q')$ est une transition de $\delta$. \end{itemize} \noindent Notons ${\cal A}' = (Q',\delta',i',F')$. Le calcul $i \donne{(u_1,g_1)} q_1 \ldots \donne{(u_n,g_n)} q_n$ de ${\cal A}$ est rŽussi ssi $g_1 \ldots g_n = e$; mais $(i,e) \donne{u_1} (q_1,g1) \donne{u_2} (q_2,g_2) \ldots \donne{u_n} (q_n,g_n)$ est un calcul rŽussi de ${\cal A}'$ ssi $g_n = e$. Ces deux calculs ont mme Žtiquette. Ceci montre que ${\cal A}'$ reconna”t le mme langage que ${\cal A}$. \end{question} \begin{question} Soient ${\cal A}_1 = (Q_1,\delta_1,i_1)$ et ${\cal A}_2 = (Q_2,\delta_2,i_2)$ deux $\Z$-automates qui reconnaissent respectivement $L_1$ et $L_2$. Nous pouvons supposer $Q_1$ et $Q_2$ disjoints. Soit $i \notin Q_1 \cup Q_2$. Notons $Q = Q_1 \cup Q_2 \cup \{i\}$; $\delta$ est la rŽunion de $\delta_1$, $\delta_2$ et des ensembles de transitions $\delta_3$ et $\delta_4$ dŽfinis par les rgles suivantess: \begin{itemize} \item $(i,x,g,q') \in \delta_3$ ssi $(i_1,x,g,q') \in \delta_1$; \item $(i,x,g,q') \in \delta_4$ ssi $(i_1,x,g,q') \in \delta_2$; \end{itemize} \noindent Le $\Z$-automate ${\cal A} = (Q,\delta,i)$ reconna”t $L_1 \cup L_2$ (preuve non dŽtaillŽe ici). \end{question} \begin{question}\label{concatenation-restreinte} Appliquons le rŽsultat de la question~\ref{rat-implique-Zrat}, en prenant comme groupe $(\Z,+)$ et $g=+1$: ainsi, $R$ est reconnu par un $\Z$-automate ${\cal A}_R = (Q_R,\delta_R,i_R)$, dŽduit d'un automate fini non dŽterministe ${\cal A}_r = (Q_R,\gamma,i_R,f_R)$ rŽduit. D'autre part, $L$ est reconnu par un $\Z$-automate ${\cal A}_L = (Q_L,\delta_L,i_L)$; nous pouvons supposer $Q_R$ et $Q_L$ disjoints. Construisons un $\Z$-automate ${\cal A} = (Q,\delta,i)$ reconnaissant $R \cdot L$. Son ensemble d'Žtats est $Q = Q_R \cup Q_L$; son Žtat initial est $i_R$; enfin, sa table de transition $\delta$ est obtenue en ajoutant ˆ la rŽunion de $\delta_L$ et $\delta_R$ chaque transition $(f_R,x,g,q')$ telle que $(i_L,x,g,q')$ appartienne ˆ $\delta_L$. Soient $\gamma_R$ et $\gamma_L$ des calculs rŽussis de ${\cal A}_R$ et ${\cal A}_L$ respectivement; notons $\widehat{\gamma_R}$ le calcul de ${\cal A}$ dŽduit de $\gamma_R$ en remplaant la premire transition $(i_L,x,g,q')$ par $(f_R,x,g,q')$; alors $\gamma_L \widehat{\gamma_R}$ est un calcul rŽussi de ${\cal A}$. RŽciproquement, tout calcul rŽussi de ${\cal A}$ passe par un ou plusieurs Žtats de ${\cal A}_R$, le dernier Žtant nŽcessairement $f_R$; puis par plusieurs Žtats Žtats de ${\cal A}_L$, le premier Žtant $q'$. Notons $\gamma_1$ la partie de ce calcul qui s'achve en $f_R$, et $\gamma_2$ celle qui commence en $f_R$. Il est clair que $\gamma_1$ est un calcul rŽussi de ${\cal A}_L$; et que, si l'on remplace $f_R$ par $i_L$ dans $\gamma_2$, on obtient un calcul rŽussi de ${\cal A}_L$. \end{question} \begin{question}\label{intersection} Appliquons le rŽsultat de la question~\ref{rat-implique-Zrat}, en prenant comme groupe $(\Z,+)$ et $g=+1$: ainsi, $R$ est reconnu par un $\Z$-automate ${\cal A}_R = (Q_R,\delta_R,i_R)$. D'autre part, $L$ est reconnu par un $\Z$-automate ${\cal A}_L = (Q_L,\delta_L,i_L)$; quitte ˆ multiplier le poids de chaque transition par~2, nous pouvons supposer que les poids des transitions de ${\cal A}_L$ sont pairs. Construisons un $\Z$-automate ${\cal A} = (Q,\delta,i)$ reconnaissant $R \cap L$. Son ensemble d'Žtats est $Q = Q_R \times Q_L$; son Žtat initial est $(i_R,i_L)$; sa table de transition $\delta$ est dŽfinie comme suit: $\bigl( (q_R,q_L),x,g,(q_R',q_L') \bigr)$ appartient ˆ $\delta$ ssi il existe une transition $(q_R,x,g_R,q_R')$ de ${\cal A}_R$ et une transition $(q_L,x,g_L,q_L')$ de ${\cal A}_L$ telles que $g = g_R + g_L$. Il est clair qu'un calcul de ${\cal A}$ est rŽussi ssi les deux calculs obtenus par projection sur les deux automates sont rŽussis; la clŽ est que les poids des transitions de ${\cal A}_R$ n'interfrent pas avec les poids des transitions de ${\cal A}_L$ (preuve non dŽtaillŽe ici). \end{question} \begin{question} $R_1 = \{c\}^*$ et $R_2 = \{a\}^*$ rŽpondent ˆ la question. \end{question} \begin{question}\label{iteration-simple} Ni $ab$, ni $bc$ ne peut appara”tre dans $q$; donc $q=a^j$ ou $q=b^j$ ou $q=c^j$ avec $j>0$. Mais dans chaque cas le mot $pq^2r$ n'est pas dans $L$: en effet, dans $u=a^n b^n c^n$, un ou deux des trois facteurs $a^n$, $b^n$ et $c^n$ verront leur longueur augmenter, et le troisime ne sera pas modifiŽ. \end{question} \begin{question}\label{iteration-double} Comme prŽcŽdemment, ni $ab$, ni $bc$ ne peuvent appara”tre dans $q$, donc les lettre de $q$ sont toutes Žgales; mme raisonnement pour $s$. Clairement, le mot $pq^2rs^2t$ n'est pas dans $L$. \end{question} \begin{question}\label{existence-cycle} Si le $\Z$-langage reconnu par ${\cal A}$ est infini, alors ce langage contient au moins un mot $u$ de longueur au moins $n$. Il est l'Žtiquette d'un calcul rŽussi qui passe par les Žtats $q_0,q_1,\ldots,q_p$ avec $p³n$. Le principe des tiroirs affirme que deux de ces Žtats sont confondus; donc il existe des indices $j$ et $k$ tels que $0²j0$ majorant la valeur absolue de tout ŽlŽment de cet ensemble. L'ensemble des cycles ŽlŽmentaires est Žgalement fini; or aucun ne peut appara”tre itŽrŽ plus de $k$ fois. Donc il n'existe qu'un nombre fini de calculs rŽussis. Ceci contredit l'existence de cycles, prouvŽe ˆ la question~\ref{existence-cycle}. \end{question} \begin{question} Ë chaque calcul rŽussi $\Gamma$ de ${\cal A}$, nous pouvons associer un calcul ŽlŽmentaire $\gamma$, en supprimant au besoin un ou plusiers cycles: la longueur du calcul Žtant finie, ceci se fait en un nombre fini d'Žtapes; nous dirons que $\gamma$ est un \emph{squelette} de $\Gamma$. Il n'existe qu'un nombre fini de calculs ŽlŽmentaires; considŽrons ceux qui traversent au moins un Žtat de ${\cal A}$ par lequel passe un cycle. Soient $\gamma$ un tel calcul et $\pi$ son poids; supposons que les cycles qui passent par un Žtat traversŽ par $\gamma$ sont tous de poids strictement positif; alors, le nombre de calculs rŽussis de ${\cal A}$ dont $\gamma$ est un squelette est fini. Du coup, le langage reconnu par ${\cal A}$ est fini: ceci est contradictoire. \end{question} \begin{question} Soient $\gamma_1$ et $\gamma_2$ de poids respectifs $\pi_1>0$ et $\pi_2<0$. Alors $\gamma_1{}^{-\pi_2}$ et $\gamma_2{}^{\pi_1}$ sont deux cycles de poids opposŽs. \end{question} \begin{question}\label{cycles-separes} Supposons que ces deux cycles sont imbriquŽs, par exemple $j²k²n²m$. Notons $\gamma_1$ le cycle $q_j \to q_{j+1} \to \cdot \to q_{m-1} \to q_m$, $\pi_1$ son poids, $\gamma_2$ le cycle $q_k \to q_{k+1} \to \cdots \to q_{n-1} \to q_n = q_k$ et $\pi_2$ son poids. Notons $\gamma$ le cycle $q_n \to q_{n+1} \to \cdots \to q_{m-1} \to q_m = q_j \to q_{j+1} \to \cdots \to q_{n-1} \to q_n = q_k$ (obtenu en court-circuitant $\gamma_2$ lors d'un parcours de $\gamma_1$) et $\pi$ son poids. Si $\pi=0$, c'est fini; sinon, $\gamma_2$ et $\gamma$ sont deux cycles dont les poids sont de signes opposŽs; et $|\gamma|+|\gamma_2| < |\gamma_1|+|\gamma_2|$. \smallskip \noindent ¥ Supposons que ces deux cycles sont enchevtrŽs, par exemple $j²k²m²n$. Le raisonnement est le mme qu'ˆ la question prŽcŽdente, en notant cette fois $\gamma$ le cycle $q_m \to q_{m_1} \to \cdots \to q_{n-1} \to q_n = q_k \to q_{k+1} \to \cdots \to q_{j-1} \to q_j = q_m$. \smallskip \noindent ¥ Nous concluons en notant qu'au bout d'un nombre fini d'Žtapes, nous tombons sur deux cycles dont l'un est de poids nul, ou deux cycles dont les poids sont de signes opposŽs et qui ne sont ni imbriquŽs, ni enchevtrŽs. \end{question} \begin{question} \end{question} \begin{question} Soit ${\cal A}$ un $\Z$-automate; trois situations peuvent se prŽsenter: \begin{itemize} \item ou bien aucun calcul rŽussi de ${\cal A}$ ne contient de cycle; le langage reconnu par ${\cal A}$ est fini, ce ne peut tre $M$; \item ou bien il existe un calcul rŽussi de ${\cal A}$ contenant au moins un cycle de poids nul; mais alors, d'aprs la question~\ref{cycle-nul}, ${\cal A}$ ne peut reconna”tre $M$; \item ou bien il existe un calcul rŽussi de ${\cal A}$ contenant contenant deux cycles $\gamma_1$ et $\gamma_2$ dont les poids sont de signes opposŽs. D'aprs la question~\ref{cycles-separes}, nous pouvons supposer que ces deux cycles ne sont ni imbriquŽs, ni enchevtrŽs. L'Žtiquette de ce calcul est alors de la forme $pqrst$, o $q \ne \mv$ est l'Žtiquette de $\gamma_1$ et $s \ne \mv$ celle de $\gamma_2$. Notons $\pi_1$ et $\pi_2$ leurs poids respectifs; alors pour tout $k\in\N$, le mot $p q^{1+k\pi_2} r s^{1+k\pi_1} t$ est dans $L$; mais alors, d'aprs le rŽsultat de la question~\ref{iteration-double}, ${\cal A}$ ne peut reconna”tre $M$. \end{itemize} \noindent Dans tous les cas, nous aboutissons ˆ une contradiction. Donc $M$ n'est pas un $\Z$-langage. \textbf{OUF!} \end{question} \begin{panneau} Dans l'article \emph{Languages accepted by integer weighted finite automatas}, dont est inspirŽ ce sujet, les auteurs adoptent une dŽmarche diffŽrente: ils se proposent de montrer que la famille des $\Z$-langages n'est pas stable par concatŽnation. Pour ce faire, ils Žtudient le langage $L_{\mathrm{eq}} \cdot L_{\mathrm{eq}}$; hŽlas, leur preuve est fausseÉ \end{panneau} \begin{question} La rŽponse est nŽgative: notant $\overline{L}$ le complŽmentaire de $L$, nous avons $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$. La famille des $\Z$-langages est close par rŽunion; si elle Žtait close par complŽmentation, elle le serait aussi par intersection, ce qui n'est pas. \end{question} \endinput