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