\begin{panneau}Rappel: pour montrer qu'un automate ${\cal A}$ reconna�t un certain langage $L$, il faut prouver: \begin{enumerate} \item que tout mot de $L$ est reconnu par ${\cal A}$;  \item que tout mot reconnu par ${\cal A}$ appartient � $L$. \end{enumerate}\end{panneau}\begin{panneau}Un langage $L$ sera dit \emph{propre} lorsqu'il ne contient pas le mot vide $\mv$.  \end{panneau}\begin{panneau}Nous dirons qu'un automate fini non d�terministe ${\cal A} = (Q,\delta,I,F)$ est \emph{r�duit} s'il v�rifie les conditions suivantes:\begin{itemize} \item ${\cal A}'$ poss�de un seul �tat initial $i$;  \item ${\cal A}'$ poss�de un seul �tat final $f$, distinct de $i$;  \item aucune transition de ${\cal A}'$ ne m�ne � $i$;  \item aucune transition de ${\cal A}'$ ne part de $f$. \end{itemize}\end{panneau}\begin{panneau}Il est interdit d'utiliser des automates � transitions instantan�es (dites aussi $\varepsilon$-transitions). Ceci s'applique aux questions~\ref{automate-reduit} et \ref{groupe-fini}.\end{panneau}\begin{question}\label{automate-reduit}Soit $L$ un langage propre, reconnu par un automate fini non d�terministe ${\cal A} = (Q,\delta,I,F)$. Montrez que $L$ peut �tre reconnu par un automate fini non d�terministe r�duit ${\cal A}'$. Vous donnerez une preuve constructive, en expliquant pr�cis�ment comment d�duire ${\cal A}'$ de ${\cal A}$. \end{question}\begin{panneau}Fixons un alphabet $\Alphabet$ contenant au moins les deux lettres $a$ et $b$. Soit $G$ un groupe not� multiplicativement. Un $G$-automate est un triplet ${\cal A} = (Q,i,\delta)$ o�: \begin{itemize} \item $Q$ est un ensemble fini non vide, dont les �l�ments sont les \emph{�tats} de ${\cal A}$;  \item $i\in Q$ est l'\emph{�tat initial};  \item $\delta \subset Q \times \Alphabet \times G \times Q$ est la \emph{table des transitions}.\end{itemize}\end{panneau}\begin{panneau}Nous noterons $q \donne{(x,g)} q'$ lorsque $(q,x,g,q')$ est une transition de ${\cal A}$. Ceci revient � associer � ${\cal A}$ un graphe orient� �tiquet�, dont les sommets sont les �l�ments de $Q$, et les �tiquettes des arcs sont des �l�ments de $\Alphabet \times G$. Notez bien que, dans un $G$-automate, il n'y a pas de transitions instantan�es.\end{panneau}\begin{panneau}Un \emph{calcul} de ${\cal A}$ de longueur $n�1$ est une suite $(q_{j-1},x_j,g_j,q_j)_{1�j�n}$ de transitions. L'\emph{�tiquette} de ce calcul est le mot $x = x_1 x_2 \ldots x_n$, son \emph{poids} est $g = g_1 g_2 \ldots g_n$. Un calcul est \emph{r�ussi} s'il commence dans l'�tat $i$, et si son poids est le neutre de $G$; notez que le mot vide ne peut pas �tre reconnu, puisque nous ne consid�rons que des calculs de longueur non nulle. Le \emph{langage reconnu} par ${\cal A}$ est l'ensemble des calculs r�ussis de ${\cal A}$.\end{panneau}\begin{question}\label{langage-egal}Dans cette question, $G$ est le groupe $(\Z,+)$. Notons $M_{\mathrm{eq}}$ le langage reconnu par le $G$-automate ${\cal A}_{\mathrm{eq}}$ repr�sent� � la figure~\ref{automate-egal}. Quel est ce langage bien connu?\begin{figure}[h]\begin{center}\setlength{\unitlength}{1.5pt}\begin{picture}(70,40)(0,0)\thinlines\letvertex A=(5,5)\letvertex B=(65,5)\drawinitialstate(A){$1$}\drawstate(B){$2$}\drawloop[t](A){$(a,1)$}\drawedge(A,B){$(b,-1)$}\drawloop[t](B){$(b,-1)$}\end{picture}\end{center}\caption{l'automate ${\cal A}_{\mathrm{eq}}$}\label{automate-egal}\end{figure}\end{question}\begin{panneau}Le r�sultat de la question pr�c�dente montre que la classe des $G$-automates reconna�t des langages non rationnels. \end{panneau}\begin{question}Proposez un $Z$-automate reconnaissant le langage $M_{\mathrm{diff}} = \{ a^p b^q \mid p,q\in\N \mbox{ et } p \ne q \}$.\end{question}\begin{question}Soient $G$ un groupe non r�duit � son neutre $e$, et $L$ un langage rationnel propre reconnu par un automate ${\cal A} = (Q,\delta,I,F)$. Montrez que $L$ peut �tre reconnu par un $G$-automate ${\cal B}$. \emph{Indications}: utilisez le r�sultat de la question~\ref{automate-reduit}; choisissez un �l�ment un �l�ment $g$ de $G$ autre que $e$ et donnez aux transitions un poids �gal � $e$, $g$ ou $g^{-1}$.\end{question}\begin{question}\label{groupe-fini}Soient $G$ un groupe fini et ${\cal A}$ un $G$-automate. Montrez que le langage $L$ reconnu par ${\cal A}$ est rationnel; vous construirez un automate fini non d�terministe qui reconna�t $L$.\end{question}\begin{panneau}Dans la suite, nous fixons $G = (\Z,+)$; un $\Z$-langage est un langage reconnu par un $\Z$-automate. Nous allons �tablir quelques propri�t�s de la classe des $\Z$-langages.\end{panneau}\begin{question}Soient $L_1$ et $L_2$ deux $\Z$-langages. Montrez que $L_1 \cup L_2$ est �galement un $\Z$-langage.\end{question}\begin{question}Soient $L$ un $\Z$-langage et $R$ un langage rationnel. Montrez que $R \cdot L = \{ uv \mid u\in R \mbox{ et } v\in L \}$ est �galement un $\Z$-langage.\end{question}\begin{panneau}On montrerait de m�me que $L \cdot R$ est un $\Z$-langage.\end{panneau}\begin{question}\label{intersection}Soient $R$ un langage rationnel et $L$ un $\Z$-langage. Montrez que $R \cap L$ est �galement un $\Z$-langage.\end{question}\begin{panneau}Nous allons montrer que la famille des $\Z$-langages n'est pas close par intersection. D�finissons trois langages: $L_1 = \{ a^n b^n \mid n�1 \}$, $L_2 = \{ b^n c^n \mid n�1 \}$ et $M = \{ a^n b^n c^n \mid n�1 \}$. \end{panneau}\begin{question}\label{decompose-M}Exhibez deux langages rationnels $R_1$ et $R_2$ tels que $M = (L_1 \cdot R_1) \cap (R_2 \cdot L2)$.\end{question}\begin{question}\label{iteration-simple}Soit $u \in a^* b^* c^*$. Montrez qu'il n'existe aucune d�composition $u = p q r$ v�rifiant $q \ne \mv$ et $p q^k r \in M$ pour tout $k\in\N$.\end{question}\begin{question}\label{iteration-double}Soit $u \in a^* b^* c^*$. Montrez qu'il n'existe aucune d�composition $u = p q r s t$ v�rifiant $q \ne \mv$, $s \ne \mv$ et $p q^k r s^k t \in M$ pour tout $k\in\N$.\end{question}\begin{panneau}Dans la suite, ${\cal A}$ d�signe un $\Z$-automate reconnaissant un $\Z$-langage infini. Soit $(q_{j-1},x_j,g_j,q_j)_{1�j�n}$ un calcul de ${\cal A}$. Nous dirons que ce calcul contient un \emph{cycle} s'il existe deux indices $k$ et $\ell$ tels que $0�k<\ell�n$ et $q_k = q_\ell$.\end{panneau}\begin{question}\label{existence-cycle}Justifiez l'affirmation suivante: il existe au moins un calcul r�ussi de ${\cal A}$ contenant au moins un cycle.\end{question}\begin{question}Montrez que s'il existe un calcul r�ussi de ${\cal A}$ contenant au moins un cycle de poids nul, alors cet automate ne peut reconna�tre $M$. Indication: utilisez le r�sultat de la question~\ref{iteration-simple}.\end{question}\begin{panneau}Supposons maintenant que ${\cal A}$ ne contient aucun cycle de poids nul. \end{panneau}\begin{question}Montrez qu'il existe un calcul r�ussi de ${\cal A}$ contenant au moins un cycle de poids strictement positif.\end{question}\begin{panneau}Par raison de sym�trie, il existe un calcul r�ussi de ${\cal A}$ contenant au moins un cycle de poids strictement n�gatif.\end{panneau}\begin{question}\TripleEtoileMontrez qu'il existe un calcul r�ussi de ${\cal A}$ contenant deux cycles dont les poids sont de signes oppos�s. \emph{Vous pourrez admettre ce r�sultat, au besoin}.\end{question}\begin{question}Montrez qu'il existe un calcul r�ussi de ${\cal A}$ contenant deux cycles de poids oppos�s.\end{question}\begin{panneau}Soit $\ell$ la longueur de ce calcul, et $(q_i)_{0�i�\ell}$ la suite des �tats travers�s. Notons $\alpha$ et $\omega$ (resp. $\alpha'$ et $\omega'$) les indices de d�but et de fin d'un cycle de poids positif (resp. n�gatif) apparaissant dans ce calcul. Nous avons donc $\alpha < \omega$ et $\alpha' < \omega'$; et on ne peut avoir � la fois $\alpha = \alpha'$ et $\omega = \omega'$.\end{panneau}\begin{question}\label{cycles-disjoints}Montrez que ces deux cycles ne sont ni imbriqu�s ni enchev�tr�s; on a donc $\alpha' � \omega$ ou $\omega' � \alpha$.\end{question}\begin{question}En utilisant les r�sultats des questions~\ref{decompose-M} � \ref{cycles-disjoints}, montrez qu'aucun $\Z$-automate ne peut reconna�tre le langage $M$.\end{question}\begin{panneau}Le \emph{compl�ment} d'un $\Z$-langage $L$ est $\Alphabet^+ \setminus L$: il faut exclure le mot-vide, puisque celui-ci ne peut �tre reconnu par un $\Z$-automate.\end{panneau}\begin{question}La famille des $\Z$-langages est-elle close par compl�mentation?\end{question}\endinput\begin{panneau}Nous nous int�ressons maintenant au probl�me suivant: la famille des $\Z$-langages est-elle close par concat�nation et/ou par it�ration? \end{panneau}\begin{question}\DoubleEtoileMontrez que la famille des $\Z$-langages n'est pas close pour l'op�ration~$*$. \end{question}\begin{question}Soit $L$ un $\Z$-langage. Le langage $\displaystyle L^+ = \bigcup_{k�1} L^k$ est-il un $\Z$-langage?\end{question}