Copy a lot of exercises into the course notes.printed-2018

author: David A. Madore <david+git@madore.org> 2018-10-03 11:13:07 +0200
committer: David A. Madore <david+git@madore.org> 2018-10-03 11:13:07 +0200
commit: ad186bc02f3b9c6e74364c682fd001b22b705cde (patch)
tree: c4ecdf973f387283ae1fed409389b9a38b16c934 /notes-inf105.tex
parent: f0a89652674ee5c96c697524e00b822b801dd6bf (diff)
download: inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.tar.gz
inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.tar.bz2
inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.zip
1 files changed, 2586 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 737ff57..ef982a0 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -30,6 +30,8 @@
 \newtheorem{comcnt}{Tout}[subsection]
 \newcommand\thingy{%
 \refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
 \newtheorem{defn}[comcnt]{Définition}
 \newtheorem{prop}[comcnt]{Proposition}
 \newtheorem{lem}[comcnt]{Lemme}
@@ -60,6 +62,15 @@
   \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
 %
 \newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}}
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+%
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\footnotesize\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
 %
 %
 % NOTE: compile dot files with
@@ -5696,7 +5707,7 @@ hors contexte $G$ (absolument quelconque) est la suivante :
 Énonçons précisément le résultat en question :
 
 \begin{thm}\label{algebraic-languages-are-decidable}
-Il existe un algorithme qui, donnée une grammaire hors-contexte $G$
+Il existe un algorithme qui, donnée une grammaire hors contexte $G$
 (sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, décide si $w
 \in L(G)$.  Autrement dit, les langages algébriques sont
 \emph{décidables} au sens
@@ -5705,7 +5716,7 @@ de \ref{definition-computable-function-or-set}.
 Plus exactement, on montre :
 \begin{itemize}
 \item Il existe un algorithme qui, donnée une grammaire
-  hors-contexte $G$ (sur un alphabet $\Sigma$), calcule une grammaire
+  hors contexte $G$ (sur un alphabet $\Sigma$), calcule une grammaire
   $G'$ (sur le même alphabet $\Sigma$ et ayant le même ensemble $N$ de
   nonterminaux que $G$) dont toutes les productions sont soit de la
   forme $T \rightarrow \alpha$ avec $|\alpha| \geq 1$, et une partie
@@ -6732,6 +6743,2579 @@ construire un algorithme résolvant le problème de l'arrêt.
   lequel on travaille.)\par}
 
 
+%
+%
+%
+
+\appendix
+\section{Exercices}\label{section-exercises}
+
+\subsection{Langages rationnels et automates}
+
+\exercice
+
+Soit $\Sigma = \{0,1\}$.  On appelle \emph{mot binaire} un mot sur
+l'alphabet $\Sigma$, et mot binaire \emph{normalisé} un mot binaire
+qui \emph{soit} commence par $1$, \emph{soit} est exactement égal
+à $0$.
+
+(1) Montrer que le langage $L_n = \{0, 1, 10, 11, 100, 101,\ldots\}$
+des mots binaires normalisés est rationnel en exhibant directement une
+expression rationnelle qui le dénote, et montrer qu'il est
+reconnaissable en exhibant directement un automate fini qui le
+reconnaît.
+
+(2) On définit la \emph{valeur numérique} d'un mot binaire
+$x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$ (où $x_i$ vaut
+$0$ ou $1$ et est numéroté de $0$ pour le chiffre le plus à droite
+à $n-1$ pour le plus à gauche) ; la valeur numérique du mot
+vide $\varepsilon$ est $0$.
+
+Parmi les langages suivants, certains sont rationnels.  Dire lesquels
+et justifier brièvement pourquoi ils le sont (on ne demande pas de
+justifier pourquoi ceux qui ne sont pas rationnels ne le sont pas) :
+
+(a) le langage $L_a$ des mots binaires dont la valeur numérique est
+paire,
+
+(b) le langage $L_b$ des mots binaires \emph{normalisés} dont la
+valeur numérique est paire,
+
+(c) le langage $L_c$ des mots binaires dont la valeur numérique est
+multiple de $3$ (indication : selon que $n$ est congru à $0$, $1$ ou
+$2$ modulo $3$, et selon que $x$ vaut $0$ ou $1$, à quoi est congru
+$2n+x$ modulo $3$ ?),
+
+(d) le langage $L_d$ des mots binaires dont la valeur numérique est un
+nombre premier,
+
+(e) le langage $L_e$ des mots binaires dont la valeur numérique est
+une puissance de $2$, i.e., de la forme $2^i$ pour $i\in\mathbb{N}$,
+
+\begin{corrige}
+(1) On peut écrire $L_n = L_{0|1(0|1){*}}$, langage dénoté par
+  l'expression rationnelle $0|1(0|1){*}$.  Ce langage est reconnu, par
+  exemple, par le DFAI suivant :
+\begin{center}
+%%% begin ex1p1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (qY) at (97bp,105bp) [draw,circle,state,final] {$Y$};
+  \node (qX) at (18bp,74bp) [draw,circle,state,initial] {$X$};
+  \node (qZ) at (97bp,18bp) [draw,circle,state,final] {$Z$};
+  \draw [->] (qX) ..controls (45.279bp,84.58bp) and (58.943bp,90.081bp)  .. node[auto] {$0$} (qY);
+  \draw [->] (qX) ..controls (44.52bp,55.44bp) and (60.758bp,43.63bp)  .. node[auto] {$1$} (qZ);
+  \draw [->] (qZ) to[loop below] node[auto] {$0,1$} (qZ);
+%
+\end{tikzpicture}
+
+%%% end ex1p1 %%%
+\end{center}
+
+(2) (a) Le langage $L_a$ est rationnel car il s'agit du langage des
+mots binaires qui soit sont le mot vide soit finissent par $0$ : il
+est dénoté par l'expression rationnelle
+$\underline{\varepsilon}|(0|1){*}0$.\spaceout (b) On a $L_b = L_a \cap
+L_n$ et on a vu que $L_a$ et $L_n$ sont rationnels, donc $L_b$ l'est
+aussi (on peut aussi exhiber une expression rationnelle qui le
+dénote : $0|1(0|1){*}0$).
+
+(c) Ajouter un $0$ ou un $1$ à la fin d'un mot binaire de valeur
+numérique $n$ le transforme en un mot de valeur numérique $2n+x$
+où $x$ est le chiffre affixé.  Considérons les six combinaisons entre
+les trois cas possibles de la valeur numérique $n$ modulo $3$ et les
+deux cas possibles de la valeur de $x$ :
+\begin{center}
+\begin{tabular}{c|c|c}
+$n\equiv?\pmod{3}$&$x=?$&$2n+x\equiv?\pmod{3}$\\\hline
+$0$&$0$&$0$\\
+$0$&$1$&$1$\\
+$1$&$0$&$2$\\
+$1$&$1$&$0$\\
+$2$&$0$&$1$\\
+$2$&$1$&$2$\\
+\end{tabular}
+\end{center}
+Ceci définit un DFA dont les trois états correspondent aux trois
+valeurs possibles de $n$ modulo $3$, la transition $n\to n'$ étiquetée
+par $x$ correspond au passage de $n$ à $2n+x$ modulo $3$,
+c'est-à-dire :
+\begin{center}
+%%% begin example6 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$1$} (q2);
+  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$0$} (q1);
+  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
+  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$0$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example6 %%%
+\end{center}
+(On a marqué l'état $0$ comme initial car le mot vide a une valeur
+numérique congrue à $0$ modulo $3$, et seul $0$ comme final car on
+veut reconnaître les multiples de $3$.)
+
+(d) Le langage $L_d$ n'est pas rationnel (on pourrait le démontrer à
+l'aide du lemme de pompage, mais ce n'est pas très facile).
+
+(e) Le langage $L_e$ est rationnel car il s'agit du langage dénoté par
+l'expression rationnelle $0{*}10{*}$.
+\end{corrige}
+
+%
+
+\exercice
+
+Soit $\Sigma = \{a\}$.  Montrer que le langage $L = \{a^2, a^3, a^5,
+a^7, a^{11}, a^{13}\ldots\}$ constitué des mots ayant un nombre
+\emph{premier} de $a$, n'est pas rationnel.
+
+\begin{corrige}
+Supposons par l'absurde que $L$ soit rationnel.  D'après le lemme de
+pompage, il existe un certain $k$ tel que tout mot de $L$ de longueur
+$\geq k$ se factorise sous la forme $uvw$ avec (i) $|v|\geq 1$,
+(ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$.  Soit
+$p$ un nombre premier supérieur ou égal à $k$ (qui existe car
+l'ensemble des nombres premiers est infini) : le mot $a^p \in L$
+admet une factorisation comme on vient de dire.  Posons $|u| =: m$ et
+$|v| =: n$, si bien que $|w| = p-m-n$.  On a alors $n\geq 1$
+d'après (i), et $|uv^iw| = m + in + (p-m-n) = p+(i-1)n$ est premier
+pour tout $i\geq 0$ d'après (iii).  En particulier pour $i=p+1$ on
+voit que $p + pn = p(n+1)$ est premier, ce qui contredit le fait qu'il
+s'agit d'un multiple non-trivial ($n+1\geq 2$) de $p$.
+\end{corrige}
+
+%
+
+\exercice
+
+On considère l'automate suivant :
+\begin{center}
+%%% begin ex1p2a %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (98bp,72bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (258bp,72bp) [draw,circle,state] {$3$};
+  \node (q2) at (178bp,72bp) [draw,circle,state] {$2$};
+  \node (q5) at (178bp,18bp) [draw,circle,state] {$5$};
+  \node (q4) at (98bp,18bp) [draw,circle,state] {$4$};
+  \node (q7) at (338bp,47bp) [draw,circle,state,final] {$7$};
+  \node (q6) at (258bp,18bp) [draw,circle,state] {$6$};
+  \draw [->] (q2) ..controls (206.11bp,72bp) and (218.58bp,72bp)  .. node[auto] {$a$} (q3);
+  \draw [->] (q3) ..controls (285.85bp,63.395bp) and (299.33bp,59.074bp)  .. node[auto] {$\varepsilon$} (q7);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+  \draw [->] (q6) ..controls (285.62bp,27.897bp) and (299.46bp,33.043bp)  .. node[auto] {$\varepsilon$} (q7);
+  \draw [->] (q4) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q5);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+  \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp)  .. node[auto] {$\varepsilon$} (q4);
+  \draw [->] (q5) ..controls (206.11bp,18bp) and (218.58bp,18bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp)  .. node[auto] {$\varepsilon$} (q1);
+  \draw [->] (q1) ..controls (126.11bp,72bp) and (138.58bp,72bp)  .. node[auto] {$a$} (q2);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a %%%
+\end{center}
+
+(0) Décrire brièvement le langage accepté par l'automate en question.
+
+(1) Cet automate est-il déterministe ?  Si non, le déterminiser.
+
+(2) Minimiser l'automate déterminisé (on doit trouver un DFA ayant
+quatre états).  Décrire brièvement la signification de ces quatre
+états, de façon à vérifier qu'il accepte le même langage que décrit
+en (0).
+
+(3) Éliminer les états de l'automate d'origine de façon à obtenir une
+expression rationnelle dénotant le langage reconnu par le langage
+décrit en (0).
+
+\begin{corrige}
+(0) L'automate proposé accepte les mots ayant soit deux $a$
+  consécutifs (en passant par le chemin $0\to 1\to 2\to 3\to 7$) soit
+  deux $b$ consécutifs (en passant par le chemin $0\to 4\to 5\to 6\to
+  7$).
+
+(1) L'automate ayant des ε-transitions, il ne peut pas être
+  déterministe : on a affaire à un εNFA.  Avant de le déterminiser, on
+  élimine ses ε-transitions : la ε-fermeture de $0$ est $\{0,1,4\}$,
+  celle de $3$ est $\{3,7\}$ et celle de $6$ est $\{6,7\}$ ; on est
+  amené au NFA suivant :
+\begin{center}
+%%% begin ex1p2b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,47bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (178bp,72bp) [draw,circle,state,final,accepting above] {$3$};
+  \node (q2) at (98bp,72bp) [draw,circle,state] {$2$};
+  \node (q5) at (98bp,18bp) [draw,circle,state] {$5$};
+  \node (q7) at (268bp,47bp) [draw,circle,state,final] {$7$};
+  \node (q6) at (178bp,18bp) [draw,circle,state,final,accepting below] {$6$};
+  \draw [->] (q2) ..controls (126.11bp,72bp) and (138.58bp,72bp)  .. node[auto] {$a$} (q3);
+  \draw [->] (q3) ..controls (208.21bp,63.701bp) and (225.92bp,58.67bp)  .. node[auto] {$a,b$} (q7);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+  \draw [->] (q6) ..controls (208.34bp,27.667bp) and (226.26bp,33.576bp)  .. node[auto] {$a,b$} (q7);
+  \draw [->] (q5) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q0) ..controls (45.62bp,37.103bp) and (59.462bp,31.957bp)  .. node[auto] {$b$} (q5);
+  \draw [->] (q0) ..controls (45.849bp,55.605bp) and (59.331bp,59.926bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+%
+\end{tikzpicture}
+
+%%% end ex1p2b %%%
+\end{center}
+(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés.  Il ne
+faut pas oublier que $3$ et $6$ sont finaux puisqu'ils ont l'état
+final $7$ dans leur ε-fermeture.)
+
+On peut maintenant procéder à la déterminisation.  Pour abréger les
+noms des états, on note, par exemple, $023$ pour $\{0,2,3\}$.  En
+construisant de proche en proche, on obtient le DFA suivant :
+\begin{center}
+\scalebox{0.8}{%PLEASE!  There HAS to be a better way to do this!
+%%% begin ex1p2c %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+\end{scope}
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+\end{scope}
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+\end{scope}
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+\end{scope}
+  \node (q0) at (18bp,121.73bp) [draw,circle,state,initial] {$0$};
+  \node (q027) at (382bp,39.732bp) [draw,circle,state,final] {$027$};
+  \node (q056) at (188bp,58.732bp) [draw,circle,state,final,accepting below] {$056$};
+  \node (q023) at (188bp,166.73bp) [draw,circle,state,final,accepting above] {$023$};
+  \node (q057) at (382bp,185.73bp) [draw,circle,state,final] {$057$};
+  \node (q0567) at (285bp,58.732bp) [draw,circle,state,final,accepting above] {$0567$};
+  \node (q02) at (100bp,160.73bp) [draw,circle,state] {$02$};
+  \node (q0237) at (285bp,166.73bp) [draw,circle,state,final,accepting below] {$0237$};
+  \node (q05) at (100bp,68.732bp) [draw,circle,state] {$05$};
+  \draw [->] (q057) ..controls (367.95bp,143.33bp) and (356.68bp,115.58bp)  .. (340bp,95.732bp) .. controls (334.17bp,88.79bp) and (326.73bp,82.582bp)  .. node[auto] {$b$} (q0567);
+  \draw [->] (q0) ..controls (45.352bp,134.58bp) and (60.273bp,141.85bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q0237) to[loop above] node[auto] {$a$} (q0237);
+  \draw [->] (q023) ..controls (213.27bp,203.89bp) and (232.48bp,226.69bp)  .. (256bp,236.73bp) .. controls (279.71bp,246.86bp) and (289.57bp,244.97bp)  .. (314bp,236.73bp) .. controls (330.09bp,231.3bp) and (345.38bp,220.3bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q023) ..controls (222.58bp,166.73bp) and (234.64bp,166.73bp)  .. node[auto] {$a$} (q0237);
+  \draw [->] (q02) ..controls (129.57bp,162.73bp) and (142.05bp,163.6bp)  .. node[auto] {$a$} (q023);
+  \draw [->] (q0567) to[loop below] node[auto] {$b$} (q0567);
+  \draw [->] (q05) ..controls (129.65bp,65.401bp) and (142.24bp,63.937bp)  .. node[auto] {$b$} (q056);
+  \draw [->] (q056) ..controls (222.58bp,58.732bp) and (234.64bp,58.732bp)  .. node[auto] {$b$} (q0567);
+  \draw [->] (q0237) ..controls (322.23bp,165.23bp) and (331.57bp,165.88bp)  .. (340bp,167.73bp) .. controls (343.63bp,168.53bp) and (347.33bp,169.66bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q056) ..controls (217.15bp,28.639bp) and (235.83bp,12.746bp)  .. (256bp,5.7322bp) .. controls (280.35bp,-2.7337bp) and (288.93bp,-0.26493bp)  .. (314bp,5.7322bp) .. controls (327.41bp,8.9409bp) and (341.18bp,15.299bp)  .. node[auto,below] {$a$} (q027);
+  \draw [->] (q05) ..controls (100bp,100.68bp) and (100bp,117.05bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q057) ..controls (397.04bp,148.37bp) and (402.36bp,127.76bp)  .. (400bp,109.21bp) .. controls (398.44bp,96.972bp) and (395.4bp,83.809bp)  .. node[auto] {$a$} (q027);
+  \draw [->] (q027) ..controls (362.81bp,75.635bp) and (351.82bp,95.041bp)  .. (340bp,110.73bp) .. controls (332.19bp,121.1bp) and (322.64bp,131.57bp)  .. node[auto] {$a$} (q0237);
+  \draw [->] (q0567) ..controls (324.14bp,51.105bp) and (336.81bp,48.57bp)  .. node[auto,below] {$a$} (q027);
+  \draw [->] (q027) ..controls (382bp,87.723bp) and (382bp,124.52bp)  .. node[auto] {$b$} (q057);
+  \draw [->] (q02) ..controls (115.85bp,134.94bp) and (120.35bp,122.5bp)  .. (118bp,110.98bp) .. controls (116.93bp,105.75bp) and (115.19bp,100.36bp)  .. node[auto] {$b$} (q05);
+  \draw [->] (q0) ..controls (45.218bp,104.36bp) and (61.545bp,93.546bp)  .. node[auto] {$b$} (q05);
+%
+\end{tikzpicture}
+
+%%% end ex1p2c %%%
+}
+\end{center}
+(À titre d'exemple, la transition étiquetée $b$ partant de l'état
+$0237$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
+le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to
+0$, $0\to 5$, $3\to 7$ et $7\to 7$.  Tous les états contenant l'un des
+symboles $3,6,7$ sont finaux.)
+
+(2) On a affaire à un DFA (sous-entendu : \emph{complet}) dont tous
+les états sont accessibles, on peut donc appliquer directement
+l'algorithme de Moore.  Une première partition sépare les états
+finaux, soit $023, 0237, 027, 056, 0567, 057$ des non-finaux, soit $0,
+02, 05$.  L'étape suivante distingue $02$ parce que sa $a$-transition
+conduit à une classe différente que celles de $0$ et $05$, et $05$
+parce que sa $b$-transition conduit à une classe différente de $0$ et
+$02$.  Les étapes suivantes ne changent rien.  Finalement, on arrive à
+un automate à quatre états :
+\begin{center}
+%%% begin ex1p2d %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+  \filldraw (0bp,0bp) -- (0bp,112bp) -- (200bp,112bp) -- (200bp,0bp) -- cycle;
+\end{scope}
+  \node (q02) at (100bp,93bp) [draw,circle,state] {$02$};
+  \node (q0) at (18bp,56bp) [draw,circle,state,initial] {$0$};
+  \node (qA) at (182bp,60bp) [draw,circle,state,final] {$A$};
+  \node (q05) at (100bp,19bp) [draw,circle,state] {$05$};
+  \draw [->] (q0) ..controls (45.691bp,68.345bp) and (60.407bp,75.151bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (qA) to[loop below] node[auto] {$a,b$} (qA);
+  \draw [->] (q02) ..controls (129.2bp,81.367bp) and (143.35bp,75.529bp)  .. node[auto] {$a$} (qA);
+  \draw [->] (q05) ..controls (128.81bp,33.252bp) and (143.85bp,40.959bp)  .. node[auto,below] {$b$} (qA);
+  \draw [->] (q05) ..controls (100bp,46.09bp) and (100bp,55.041bp)  .. node[auto] {$a$} (q02);
+  \draw [->] (q02) ..controls (116.71bp,70.13bp) and (120.2bp,60.948bp)  .. (118bp,52.251bp) .. controls (117.33bp,49.598bp) and (116.4bp,46.928bp)  .. node[auto] {$b$} (q05);
+  \draw [->] (q0) ..controls (45.691bp,43.655bp) and (60.407bp,36.849bp)  .. node[auto] {$b$} (q05);
+%
+\end{tikzpicture}
+
+%%% end ex1p2d %%%
+\end{center}
+où $A$ représente la classe de tous les états finaux de l'automate
+précédent.
+
+La signification des quatre états est la suivante : l'état $0$
+signifie que l'automate n'a encore rien lu, l'état $02$ signifie que
+l'automate vient de lire un $a$, le $05$ signifie qu'il vient de lire
+un $b$, le $A$ signifie qu'il a lu deux $a$ consécutifs ou bien deux
+$b$ consécutifs.  Sur cette description, il est clair que l'automate
+accepte les mots contenant deux $a$ consécutifs ou bien deux $b$
+consécutifs.
+
+(3) L'élimination des états $1$ à $6$ peut se faire dans un ordre
+quelconque et conduit à l'automate (à transitions étiquetées par des
+expressions rationnelles) suivant :
+\begin{center}
+%%% begin ex1p2a2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,20.549bp) [draw,circle,state,initial] {$0$};
+  \node (q7) at (104bp,20.549bp) [draw,circle,state,final] {$7$};
+  \draw [->] (q0) ..controls (47.743bp,20.549bp) and (62.773bp,20.549bp)  .. node[auto] {$aa$} (q7);
+  \draw [->] (q0) ..controls (42.511bp,4.2138bp) and (55.796bp,-1.5495bp)  .. (68bp,1.5495bp) .. controls (71.958bp,2.5545bp) and (75.953bp,4.1071bp)  .. node[auto,below] {$bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a2 %%%
+\end{center}
+
+Il y a plusieurs flèches entre les mêmes états : quitte à les
+remplacer par des disjonctions, on obtient :
+\begin{center}
+%%% begin ex1p2a3 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q7) at (119bp,18bp) [draw,circle,state,final] {$7$};
+  \draw [->] (q0) ..controls (51.292bp,18bp) and (73.384bp,18bp)  .. node[auto] {$aa|bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a3 %%%
+\end{center}
+
+Enfin, on doit éliminer les états $0$ et $7$ eux-mêmes : pour cela, on
+ajoute un nouvel état initial qui ne soit la cible d'aucune flèche et
+un nouvel état final d'où ne part aucune flèche,
+\begin{center}
+%%% begin ex1p2a4 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (qi) at (18bp,18bp) [draw,circle,state,initial] {$\phantom{0}$};
+  \node (q0) at (97bp,18bp) [draw,circle,state] {$0$};
+  \node (q7) at (198bp,18bp) [draw,circle,state] {$7$};
+  \node (qf) at (277bp,18bp) [draw,circle,state,final] {$\phantom{7}$};
+  \draw [->] (qi) ..controls (45.659bp,18bp) and (57.817bp,18bp)  .. node[auto] {$\varepsilon$} (q0);
+  \draw [->] (q7) ..controls (225.66bp,18bp) and (237.82bp,18bp)  .. node[auto] {$\varepsilon$} (qf);
+  \draw [->] (q0) ..controls (130.29bp,18bp) and (152.38bp,18bp)  .. node[auto] {$aa|bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a4 %%%
+\end{center}
+
+Et l'élimination des états $0$ et $7$ dans un ordre quelconque conduit
+finalement à l'expression rationnelle $(a|b){*}(aa|bb)(a|b){*}$.
+\end{corrige}
+
+%
+
+\exercice
+
+Soit $\Sigma = \{a,b\}$.
+
+(1) Tracer l'automate de Thompson de l'expression rationnelle
+$a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?
+
+(2) En éliminer les transitions spontanées.
+
+(3) Déterminiser l'automate obtenu (on demande un automate complet).
+
+(4) Minimiser l'automate obtenu (on demande un automate complet).
+
+(5) Vérifier le résultat en décrivant en français le langage dénoté
+par l'expression rationnelle initiale et reconnu par l'automate
+finalement obtenu.
+
+\begin{corrige}
+(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$
+  états puisque cette expression rationnelle contient $7$ symboles
+  parenthèses non comptées.  Il est le suivant (où on a omis les
+  $\varepsilon$ sur les transitions spontanées) :
+\begin{center}
+\scalebox{0.34}{%
+%%% begin ex3p1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,45bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (255bp,18bp) [draw,circle,state] {$3$};
+  \node (q2) at (176bp,45bp) [draw,circle,state] {$2$};
+  \node (q5) at (413bp,48bp) [draw,circle,state] {$5$};
+  \node (q4) at (334bp,18bp) [draw,circle,state] {$4$};
+  \node (q7) at (571bp,86bp) [draw,circle,state] {$7$};
+  \node (q6) at (492bp,86bp) [draw,circle,state] {$6$};
+  \node (q9) at (729bp,86bp) [draw,circle,state] {$9$};
+  \node (q8) at (650bp,86bp) [draw,circle,state] {$8$};
+  \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$};
+  \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$};
+  \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$};
+  \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$};
+  \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp)  .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp)  .. node[auto] {{}} (q3);
+  \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp)  .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp)  .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp)  .. node[auto] {{}} (q5);
+  \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp)  .. node[auto] {{}} (q3);
+  \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp)  .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp)  .. node[auto] {$a$} (q11);
+  \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp)  .. node[auto] {$a$} (q8);
+  \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp)  .. node[auto] {{}} (q12);
+  \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp)  .. node[auto] {{}} (q9);
+  \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp)  .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp)  .. node[auto] {{}} (q12);
+  \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp)  .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp)  .. node[auto] {{}} (q1);
+  \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp)  .. node[auto] {{}} (q7);
+  \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp)  .. node[auto] {{}} (q13);
+  \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp)  .. node[auto] {{}} (q10);
+  \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp)  .. node[auto] {{}} (q4);
+  \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp)  .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp)  .. node[auto] {{}} (q10);
+  \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp)  .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp)  .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp)  .. node[auto] {{}} (q13);
+  \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp)  .. node[auto] {{}} (q1);
+  \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp)  .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp)  .. node[auto] {{}} (q5);
+%
+\end{tikzpicture}
+
+%%% end ex3p1 %%%
+}
+\end{center}
+
+Cet automate n'est pas déterministe : un automate comportant des
+ε-transitions est forcément non-déterministe.
+
+\smallbreak
+
+(2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$
+(car des transitions non spontanées y aboutissent) vont disparaître ;
+les ε-fermetures $C(q)$ de ces états sont les suivantes :
+
+\begin{center}
+\begin{tabular}{r|l}
+$q$&ε-fermeture $C(q)$\\
+\hline
+$0$&$\{0,1,3,4,5,13\}$\\
+$2$&$\{1,2,3,4,5,13\}$\\
+$6$&$\{6,7\}$\\
+$8$&$\{5,8,9,10,12,13\}$\\
+$11$&$\{5,10,11,12,13\}$\\
+\end{tabular}
+\end{center}
+
+En remplaçant chaque transition $q^\sharp \to q'$ étiquetée
+d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour
+chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient le NFA
+suivant :
+
+\begin{center}
+%%% begin ex3p1b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$};
+  \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$};
+  \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$};
+  \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$};
+  \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp)  .. node[auto] {$a$} (q2);
+  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
+  \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp)  .. node[auto] {$a$} (q11);
+  \draw [->] (q11) to[loop above] node[auto] {$a$} (q11);
+  \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp)  .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp)  .. node[auto,near start] {$b$} (q6);
+  \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp)  .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp)  .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp)  .. node[auto,below] {$b$} (q6);
+  \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp)  .. node[auto] {$b$} (q6);
+  \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp)  .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp)  .. node[auto,near start] {$b$} (q6);
+  \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp)  .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp)  .. node[auto] {$a$} (q8);
+%
+\end{tikzpicture}
+
+%%% end ex3p1b %%%
+\end{center}
+
+Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
+leur ε-fermeture.
+
+\smallbreak
+
+(3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le
+déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la
+seule transition qui manque, c'est-à-dire une transition étiquetée par
+$b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même
+étiquetées $a$ et $b$).  Nous ne représentons pas l'automate à $6$
+états ainsi fabriqué.
+
+\smallbreak
+
+(4) On part de l'algorithme déterministe complet obtenu à la
+question (3), et on lui applique l'algorithme de minimisation.  On
+sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et
+les non-finaux $\{6,\bot\}$.  La transition étiquetée $a$ sépare les
+états $6$ et $\bot$ car le premier aboutit dans la classe
+$\{0,2,8,11\}$ tandis que le second aboutit dans la classe
+$\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
+états.  L'automate minimal est donc le suivant :
+\begin{center}
+%%% begin ex3p1c %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$};
+  \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$};
+  \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$};
+  \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$a$} (qF);
+  \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$b$} (qbot);
+  \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot);
+  \draw [->] (qF) to[loop above] node[auto] {$a$} (qF);
+  \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q6);
+%
+\end{tikzpicture}
+
+%%% end ex3p1c %%%
+\end{center}
+où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.
+
+\smallbreak
+
+(5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$
+consécutifs ni de $b$ final,
+c'est-à-dire des mots dans lesquels chaque $b$ est suivi
+d'au moins un $a$ : l'expression rationnelle initiale le présente
+comme le langage constitués des mots formés d'un nombre quelconque de
+$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au
+moins un $a$.  L'automate final interdit les suites de deux $b$
+consécutifs comme ceci : l'état $F$ correspond à la situation où on ne
+vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou
+bien on vient de commencer le mot) et on n'en a jamais rencontré deux,
+l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en
+a jamais rencontré deux, et l'état $\bot$ à la situation où on a
+rencontré au moins une fois deux $b$ consécutifs.  Avec cette
+description, il est clair que l'automate fait ce qui était demandé.
+\end{corrige}
+
+%
+
+\exercice
+
+Donner plusieurs (au moins trois) expressions rationnelles
+équivalentes dénotant le langage reconnu par l'automate suivant sur
+l'alphabet $\Sigma = \{a,b\}$ :
+
+\begin{center}
+%%% begin ex3p2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$};
+  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
+  \draw [->] (q2) to[loop right] node[auto] {$b$} (q2);
+  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q0) to[loop left] node[auto] {$a$} (q0);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q1);
+  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
+%
+\end{tikzpicture}
+
+
+%%% end ex3p2 %%%
+\end{center}
+(On pourra considérer les ordres suivants d'élimination des états :
+(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.)
+
+\begin{corrige}
+(A) Si on commence par éliminer l'état $2$ (en considérant l'automate
+comme un automate à transitions étiquetées par des expressions
+rationnelles), l'état $1$ reçoit une transition vers lui-même
+étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
+place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$,
+qu'on peut fusionner avec la transition vers lui-même déjà existante
+étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$.
+Quitte éventuellement à ajouter un nouvel état initial (conduisant à
+$0$ par une transition spontanée) et un nouvel état final (vers lequel
+$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on
+obtient finalement l'expression rationnelle
+\[
+(a|b(ab{*}a){*}b){*}
+\]
+
+\smallbreak
+
+(B) Si on commence par éliminer l'état $1$, il apparaît une transition
+$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
+appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
+de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
+par $\bot$, symbole d'expression rationnelle qui dénote le lagange
+vide, et l'expression rationnelle $\bot{*}$ est équivalente
+à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit
+lui aussi une transition vers lui-même (en passant par $1$) étiquetée
+$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
+existante étiquetée par $b$ pour obtenir une transition étiquetée
+$b|aa$ ; de même, l'état $0$ reçoit une transition étiquetée $bb$,
+qu'on peut fusionner avec celle existante pour obtenir $a|bb$.
+L'élimination de l'état $2$ fait alors apparaître une transition de
+$0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut fusionner avec
+la transition vers lui-même déjà étiquetée par $a|bb$ pour une seule
+étiquetée par $a|bb|ba(b|aa){*}ab$.  On obtient finalement
+\[
+(a|bb|ba(b|aa){*}ab){*}
+\]
+(en particulier, cette expression est équivalente à celle obtenue
+précédemment).
+
+\smallbreak
+
+(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable
+ajouter un nouvel état initial $I$ (conduisant à $0$ par une
+transition spontanée) et un nouvel état final $F$ (vers lequel $0$
+conduit par une transition spontanée).  L'élimination de l'état $0$
+fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une
+transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état
+$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$
+vers $F$ étiquetée $a{*}$.  L'élimination de l'état $2$ fait
+apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$,
+qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour
+obtenir une transition $(ab{*}a|ba{*}b)$.  Finalement, l'élimination
+de l'état $1$ done l'expression rationnelle
+\[
+a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
+\]
+(toujours équivalente aux précédentes).
+\end{corrige}
+
+%
+
+\exercice
+
+On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$
+représenté par la figure suivante :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
+\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$};
+\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
+\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$};
+\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
+\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$};
+\draw[->] (X) -- node[auto]{$\varepsilon$} (A1);
+\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1);
+\draw[->] (A1) -- node[auto]{$a$} (A2);
+\draw[->] (B1) -- node[auto]{$b$} (B2);
+\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
+\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
+\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
+\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
+\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y);
+\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y);
+\end{tikzpicture}
+\end{center}
+
+(0) De quelle sorte d'automate s'agit-il ?  (Autrement dit : est-il
+déterministe ou non ? avec transitions spontanées ou non ?)
+
+(1a) Décrire brièvement, en français, le langage $L$ reconnu
+(=accepté) par l'automate $M$, puis donner une expression
+rationnelle qui le dénote.  (On pourra préférer traiter la question
+(1b) d'abord.)
+
+(1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
+$\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
+(Note : il est recommandé de réutiliser ces mots pour vérifier
+rapidement les réponses aux questions suivantes et ainsi détecter
+d'éventuelles erreurs lors des transformations des automates.)
+
+(2) Éliminer les transitions spontanées de l'automate $M$.  (On
+supprimera les états devenus inutiles.)  On appellera $M_2$ l'automate
+obtenu.
+
+(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire.  (On
+demande un automate déterministe complet.)  On appellera $M_3$
+l'automate déterminisé.
+
+Pour simplifier le travail du correcteur, on demande de représenter
+$M_3$ de sorte que les transitions étiquetées par $a$ soient, dans la
+mesure du possible, horizontales de la gauche vers la droite, et
+celles étiquetées par $b$, verticales du haut vers le bas.
+
+(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire
+(justifier).
+
+(5) Donner un automate (de n'importe quelle sorte) qui reconnaît le
+langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.
+
+(6) Décrire brièvement, en français, ce langage
+complémentaire $\overline{L}$.
+
+(7) (Question bonus, plus longue, à ne traiter qu'en dernier.)
+Calculer une expression rationnelle qui dénote ce langage
+complémentaire $\overline{L}$.  (Ne pas hésiter à introduire des
+notations intermédiaires.)
+
+\begin{corrige}
+(0) L'automate $M$ est un automate fini non-déterministe à transitions
+  spontanées, ou ε-NFA (le concept d'« automate déterministe à
+  transitions spontanées » n'aurait tout simplement pas de sens).
+
+\smallbreak
+
+(1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
+un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le chemin par
+les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
+c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate $M$ dans
+son ensemble accepte les mots comportant exactement un $a$ ou
+(inclusif) exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1
+\penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le
+nombre total d'occurrences de la lettre $x$ dans le mot $w$).  C'est
+le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$
+(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi
+noter $+$).
+
+(1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à
+$L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y
+appartiennent pas.
+
+\smallbreak
+
+(2) La ε-fermeture (arrière) de l'état $X$ est $\{X,A,B\}$ ; la
+ε-fermeture de l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est
+$\{B',Y\}$ ; les autres états sont leur propre ε-fermeture (i.e.,
+celle-ci est un singleton).  L'élimination des transitions spontanées
+conduit donc à l'automate $M_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
+\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
+\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$};
+\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
+\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$};
+\draw[->] (X) -- node[auto]{$b$} (A1);
+\draw[->] (X) -- node[auto,below left]{$a$} (B1);
+\draw[->] (X) -- node[auto,below right]{$a$} (A2);
+\draw[->] (X) -- node[auto,above right]{$b$} (B2);
+\draw[->] (A1) -- node[auto]{$a$} (A2);
+\draw[->] (B1) -- node[auto]{$b$} (B2);
+\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
+\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
+\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
+\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
+\end{tikzpicture}
+\end{center}
+(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition
+non-spontanée n'y conduit.)
+
+\smallbreak
+
+(3) L'algorithme de déterminisation conduit à l'automate $M_3$ suivant
+où, pour plus de lisibilité, les états finaux ont été marqués en les
+entourant deux fois plutôt que par une flèche sortante :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$};
+\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$};
+\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$};
+\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$};
+\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$};
+\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$};
+\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$};
+\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$};
+\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$};
+\draw[->] (s00) -- node[auto]{$a$} (s01);
+\draw[->] (s01) -- node[auto]{$a$} (s02);
+\draw[->] (s10) -- node[auto]{$a$} (s11);
+\draw[->] (s11) -- node[auto]{$a$} (s12);
+\draw[->] (s20) -- node[auto]{$a$} (s21);
+\draw[->] (s21) -- node[auto]{$a$} (s22);
+\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
+\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
+\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
+\draw[->] (s00) -- node[auto]{$b$} (s10);
+\draw[->] (s10) -- node[auto]{$b$} (s20);
+\draw[->] (s01) -- node[auto]{$b$} (s11);
+\draw[->] (s11) -- node[auto]{$b$} (s21);
+\draw[->] (s02) -- node[auto]{$b$} (s12);
+\draw[->] (s12) -- node[auto]{$b$} (s22);
+\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
+\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
+\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
+\end{tikzpicture}
+\end{center}
+
+Pour la commodité de la suite de la correction, on renomme les états
+de cet automate $M_3$ de la façon suivante :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$01$};
+\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$02$};
+\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$10$};
+\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$11$};
+\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$12$};
+\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$20$};
+\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$21$};
+\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$22$};
+\draw[->] (s00) -- node[auto]{$a$} (s01);
+\draw[->] (s01) -- node[auto]{$a$} (s02);
+\draw[->] (s10) -- node[auto]{$a$} (s11);
+\draw[->] (s11) -- node[auto]{$a$} (s12);
+\draw[->] (s20) -- node[auto]{$a$} (s21);
+\draw[->] (s21) -- node[auto]{$a$} (s22);
+\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
+\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
+\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
+\draw[->] (s00) -- node[auto]{$b$} (s10);
+\draw[->] (s10) -- node[auto]{$b$} (s20);
+\draw[->] (s01) -- node[auto]{$b$} (s11);
+\draw[->] (s11) -- node[auto]{$b$} (s21);
+\draw[->] (s02) -- node[auto]{$b$} (s12);
+\draw[->] (s12) -- node[auto]{$b$} (s22);
+\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
+\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
+\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
+\end{tikzpicture}
+\end{center}
+Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré
+de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et
+l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états
+$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la
+lettre $b$.
+
+\smallbreak
+
+(4) L'automate $M_3$ est déjà minimal.  En effet, l'algorithme de
+minimisation commence par séparer les classes $\{01,10,11,12,21\}$
+(états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la
+transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en
+$\{01,21\}$ (qui vont vers un état non-final) et $\{10,11,12\}$ (qui
+vont vers un état final), et la classe $\{00,02,20,22\}$ en
+$\{00,20\}$ (qui vont vers un état final) et $\{02,22\}$ (qui vont
+vers un non-final).  La transition étiquetée par $b$ sépare ensuite en
+deux chacune des trois classes $\{00,20\}$, $\{01,21\}$ et $\{02,22\}$
+(car le premier élément va dans la classe $\{10,11,12\}$ tandis que le
+second reste dans la même classe) et sépare en trois la classe
+$\{10,11,12\}$.  On a donc séparé chacun des états.
+
+\smallbreak
+
+(5) Pour reconnaître le complémentaire du langage reconnu par un
+automate fini déterministe complet, il suffit d'échanger états finaux
+et non-finaux : on peut donc prendre l'automate dessiné en (3) avec,
+cette fois, la convention que les états simplement entourés sont
+finaux (et les doublement entourés sont non-finaux).
+Appelons-le $M_5$.
+
+\emph{Attention :} échanger états finaux et non-finaux ne marche pas
+pour reconnaître le complémentaire du langage reconnu par un automate
+non-déterministe ou incomplet (car la négation de « il existe un
+chemin qui va vers un état final » est « aucun chemin ne va vers un
+état final » et pas « il existe un chemin qui va vers un état
+non-final »).
+
+\smallbreak
+
+(6) Puisque $L$ est le langage formé des mots comportant exactement un
+$a$ ou (inclusif) exactement un $b$, son complémentaire $\overline{L}$
+est formé des mots ayant un nombre différent de $1$ de $a$ \emph{et}
+un nombre différent de $1$ de $b$ ; si on préfère, il s'agit du
+langage comportant ($0$ ou au moins $2$ fois la lettre $a$) \emph{et}
+($0$ ou au moins $2$ fois la lettre $b$).
+
+\smallbreak
+
+(7) L'élimination des états n'est pas trop complexe car l'automate
+$M_5$ a très peu de boucles.  Éliminons simultanément tous les états
+non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour
+créer un nouvel (et unique) état final $F$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s02) at (100bp,0bp) [draw,rounded corners,state] {$02$};
+\node (s20) at (0bp,-60bp) [draw,rounded corners,state] {$20$};
+\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
+\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
+\draw[->] (s00) -- node[auto]{$aa$} (s02);
+\draw[->] (s20) -- node[auto]{$ab{*}a$} (s22);
+\draw[->] (s02) to[loop above] node[auto]{$a$} (s02);
+\draw[->] (s00) -- node[auto]{$bb$} (s20);
+\draw[->] (s02) -- node[auto]{$ba{*}b$} (s22);
+\draw[->] (s20) to[loop left] node[auto]{$b$} (s20);
+\draw[->] (s22) to[loop below] node[auto]{$a|b$} (s22);
+\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
+\draw[->] (s00) -- node[auto]{$r$} (s22);
+\draw[->,out=0,in=90] (s02) to node[auto]{$\varepsilon$} (F);
+\draw[->,out=270,in=270] (s20) to node[auto,below]{$\varepsilon$} (F);
+\draw[->] (s00) to[out=45,in=180] (100bp,40bp) to[out=0,in=45] node[auto,above]{$\varepsilon$} (F);
+\end{tikzpicture}
+\end{center}
+où $r := abaa{*}b \,|\, abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a$
+(correspondant aux quatre façons de passer de $00$ à $22$ dans le
+graphe ci-dessus).  Éliminons l'état $02$ et l'état $20$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
+\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
+\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
+\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
+\draw[->] (s22) to[loop above] node[auto]{$a|b$} (s22);
+\draw[->] (s00) -- node[auto]{$r'$} (s22);
+\draw[->,out=0,in=90] (s00) to node[auto]{$\varepsilon|aaa{*}|bbb{*}$} (F);
+\end{tikzpicture}
+\end{center}
+où $r' := r \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, bbb{*}ab{*}a =
+abaa{*}b \penalty0\,|\, abbb{*}a \penalty0\,|\, baaa{*}b
+\penalty0\,|\, babb{*}a \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\,
+bbb{*}ab{*}a$.  On obtient finalement l'expression rationnelle
+suivante pour $\overline{L}$ :
+\[
+\varepsilon\,|\,aaa{*}\,|\,bbb{*}\,|\,(abaa{*}b \,|\,
+abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a
+\,|\, aaa{*}ba{*}b \,|\, bbb{*}ab{*}a)(a|b){*}
+\]
+Pour comprendre cette expression rationnelle, la disjonction de plus
+haut niveau correspond aux quatre possibilités : (i) $0$ fois la
+lettre $a$ et $0$ fois la lettre $b$, (ii) au moins $2$ fois la lettre
+$a$ et $0$ fois la lettre $b$, (iii) $0$ fois la lettre $a$ et au
+moins $2$ fois la lettre $b$, et (iv) au moins $2$ fois la lettre $a$
+et au moins $2$ fois la lettre $b$.  Pour mieux comprendre
+l'expression du cas (iv), on peut remarquer que $abaa{*}b
+\penalty0\,|\, baaa{*}b \penalty0\,|\, aaa{*}ba{*}b$ dénote le langage
+formé des mots comportant au moins deux $a$ et exactement deux $b$ et
+qui finissent par un $b$, et symétriquement $abbb{*}a \penalty0\,|\,
+babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots
+comportant au moins deux $b$ et exactement deux $a$ et qui finissent
+par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot
+ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe
+qui vérifie cette propriété suivi d'un suffixe quelconque.  (On
+pouvait utiliser directement ce raisonnement pour produire
+l'expression.)
+\end{corrige}
+
+%
+%
+%
+
+\subsection{Langages algébriques et grammaires hors contexte}
+
+\exercice
+
+Considérons le fragment simplifié suivant de la grammaire d'un langage
+de programmation hypothétique :
+\[
+\begin{aligned}
+\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
+|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
+\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
+\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
+\end{aligned}
+\]
+(Ici, les « lettres » ou tokens ont été écrits comme des mots, par
+exemple $\mathtt{foo}$ est une « lettre » : les terminaux sont écrits
+en police à espacement fixe tandis que les nonterminaux sont en
+italique et commencent par une majuscule.  On prendra
+$\mathit{Instruction}$ pour axiome.)
+
+(1) Donner l'arbre d'analyse de :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$ ;
+expliquer brièvement pourquoi il n'y en a qu'un.
+
+(2) Donner deux arbres d'analyse distincts de :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
+Que peut-on dire de la grammaire présentée ?
+
+(3) En supposant que, dans ce langage,
+$\mathtt{begin}\penalty0\ I\penalty0\ \penalty0\mathtt{end}$ (où $I$
+est une instruction) a le même effet que $I$ seul, comment un
+programmeur peut-il réécrire l'instruction considérée en (2) pour
+obtenir un comportant équivalent à l'une ou l'autre des deux
+interprétations ?
+
+(4) Modifier légèrement la grammaire proposée de manière à obtenir une
+grammaire faiblement équivalente dans laquelle seul l'un des arbres
+d'analyse obtenus en (2) est possible (i.e., une grammaire qui force
+cette interprétation-là par défaut) ; on pourra être amené à
+introduire des nouveaux nonterminaux pour des variantes de
+$\mathit{Instruction}$ et $\mathit{Conditional}$ qui interdisent
+récursivement les conditionnelles sans $\mathtt{else}$.
+
+\begin{corrige}
+(1) L'arbre d'analyse de
+  $\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$
+  est le suivant (en notant $I$, $C$ et $E$ pour
+  $\mathit{Instruction}$, $\mathit{Condition}$ et
+  $\mathit{Expression}$ respectivement) :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.4]
+%%% begin ex2p1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
+  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
+  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
+  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
+  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
+  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (qux) at (387bp,162bp) [draw,draw=none] {$\mathtt{qux}$};
+  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
+  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
+  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
+  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
+  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
+  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
+  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
+  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
+  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
+  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
+  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
+  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
+  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
+  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
+  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
+  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
+  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
+  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
+  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
+  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
+  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (qux);
+  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
+  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
+  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1 %%%
+\end{center}
+
+Il est le seul possible car une fois acquis que les deux $\mathtt{if}$
+comportent chacun un $\mathtt{else}$, il se construit ensuite en
+descendant de façon unique (l'instruction est forcément une condition,
+qui s'analyse en $\mathtt{if}\ E\ \mathtt{then}\ I\ \mathtt{else}\ I$
+de façon unique, et chacun des morceaux s'analyse de nouveau de façon
+unique).
+
+\vskip .5explus.1fil
+
+(2) Un arbre d'analyse possible consiste à associer le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ avec
+$\mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}$ :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.4]
+%%% begin ex2p1a %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
+  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+  \node (I0) at (135bp,378bp) [draw,draw=none] {$I$};
+  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
+  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
+  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
+  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (C0) at (135bp,306bp) [draw,draw=none] {$C$};
+  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
+  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
+  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
+  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
+  \draw [] (C0) ..controls (149.48bp,276.85bp) and (156.64bp,262.92bp)  .. (then0);
+  \draw [] (I0) ..controls (135bp,348.85bp) and (135bp,334.92bp)  .. (C0);
+  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
+  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
+  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
+  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
+  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
+  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
+  \draw [] (C0) ..controls (91.844bp,277.03bp) and (70.277bp,263.05bp)  .. (if0);
+  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
+  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
+  \draw [] (C0) ..controls (178.16bp,277.03bp) and (199.72bp,263.05bp)  .. (I1);
+  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
+  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
+  \draw [] (C0) ..controls (120.52bp,276.85bp) and (113.36bp,262.92bp)  .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1a %%%
+\end{center}
+un autre consiste à associer le $\mathtt{else}\penalty0\ \mathtt{bar}$
+avec
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ :
+\begin{center}
+\tikzstyle{automaton}=[scale=0.4]
+%%% begin ex2p1b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (bar) at (387bp,162bp) [draw,draw=none] {$\mathtt{bar}$};
+  \node (then1) at (279bp,90bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (if1) at (135bp,90bp) [draw,draw=none] {$\mathtt{if}$};
+  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
+  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
+  \node (I2) at (351bp,90bp) [draw,draw=none] {$I$};
+  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
+  \node (trippy) at (207bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
+  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
+  \node (foo) at (351bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
+  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
+  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
+  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
+  \node (E1) at (207bp,90bp) [draw,draw=none] {$E$};
+  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
+  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
+  \draw [] (I2) ..controls (351bp,60.846bp) and (351bp,46.917bp)  .. (foo);
+  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
+  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
+  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
+  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (I2);
+  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (bar);
+  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
+  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (E1);
+  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
+  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (if1);
+  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
+  \draw [] (E1) ..controls (207bp,60.846bp) and (207bp,46.917bp)  .. (trippy);
+  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
+  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (then1);
+  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
+  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
+%
+\end{tikzpicture}
+
+%%% end ex2p1b %%%
+\end{center}
+La grammaire présentée est donc ambiguë.
+
+\vskip .5explus.1fil
+
+(3) Pour forcer la première interprétation (le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
+$\mathtt{if}\penalty0\ \mathtt{trippy}$), on peut écrire :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{end}$.
+
+Pour forcer la seconde interprétation (le
+$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
+$\mathtt{if}\penalty0\ \mathtt{happy}$), on peut écrire :
+$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{end}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
+
+\vskip .5explus.1fil
+
+(4) Pour forcer la première interprétation (le $\mathtt{else}$ se
+rapporte au $\mathtt{if}$ le plus proche possible), on peut modifier
+la grammaire comme suit :
+\[
+\begin{aligned}
+\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{CondNoSC}\\
+|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
+\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\
+|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
+\mathit{CondNoSC} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{InstrNoSC}\\
+\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
+\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
+\end{aligned}
+\]
+L'idée est d'obliger une instruction conditionnelle qui apparaîtrait
+après le $\mathtt{then}$ d'une conditionnelle complète à être
+elle-même complète (elle ne peut pas être courte, car alors le
+$\mathtt{else}$ devrait se rattacher à elle), et ce, récursivement.
+On peut montrer que la grammaire ci-dessus est inambiguë et faiblement
+équivalente à celle de départ.
+
+On peut aussi fabriquer une grammaire inambiguë, faiblement
+équivalente à celle de départ, qui force l'autre interprétation (le
+$\mathtt{else}$ se rapporte au $\mathtt{if}$ le plus lointain
+possible), mais c'est nettement plus complexe (l'idée générale pour
+apparier un $\mathtt{else}$ avec un $\mathtt{if}...\mathtt{else}$ dans
+cette logique est de demander que \emph{soit} le $\mathtt{else}$ n'est
+suivi d'aucun autre $\mathtt{else}$, \emph{soit} toute instruction
+conditionnelle entre le $\mathtt{then}$ et le $\mathtt{else}$ est
+elle-même complète).  Contrairement à la grammaire précédente, cette
+grammaire, bien qu'inambiguë, est probablement impossible à analyser
+avec un analyseur LR (ou même, déterministe).
+\end{corrige}
+
+
+%
+
+\exercice\label{non-square-words-is-algebraic}
+
+Soit $\Sigma = \{a,b\}$.  On considère le langage $M$ des mots qui
+\emph{ne s'écrivent pas} sous la forme $ww$ avec $w\in\Sigma^*$
+(c'est-à-dire sous la forme d'un carré ; autrement dit, le langage $M$
+est le \emph{complémentaire} du langage $Q$ des carrés considéré dans
+l'exercice \ref{square-words-not-algebraic}) : par exemple, $M$
+contient les mots $a$, $b$, $ab$, $aab$ et $aabb$ mais pas
+$\varepsilon$, $aa$, $abab$ ni $abaaba$.
+
+(0) Expliquer pourquoi tout mot sur $\Sigma$ de longueur impaire est
+dans $M$, et pourquoi un mot $x_1\cdots x_{2n}$ de longueur paire $2n$
+est dans $M$ si et seulement si il existe $i$ tel que $x_i \neq
+x_{n+i}$.
+
+On considère par ailleurs la grammaire hors contexte $G$
+(d'axiome $S$)
+\[
+\begin{aligned}
+S &\rightarrow A \;|\; B \;|\; AB \;|\; BA\\
+A &\rightarrow a \;|\; aAa \;|\; aAb \;|\; bAa \;|\; bAb\\
+B &\rightarrow b \;|\; aBa \;|\; aBb \;|\; bBa \;|\; bBb\\
+\end{aligned}
+\]
+
+(1) Décrire le langage $L(G,A)$ des mots dérivant de $A$ dans la
+grammaire $G$ (autrement dit, le langage engendré par la grammaire
+identique à $G$ mais ayant pour axiome $A$).  Décrire de même
+$L(G,B)$.
+
+(2) Montrer que tout mot de longueur impaire est dans le
+langage $L(G)$ engendré par $G$.
+
+(3) Montrer que tout mot $t \in M$ de longueur paire est dans $L(G)$.
+(Indication : si $t = x_1\cdots x_{2n}$ est de longueur paire $2n$ et
+que $x_i \neq x_{n+i}$, on peut considérer la factorisation de $t$ en
+$x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)
+
+(4) Montrer que tout mot de $L(G)$ de longueur paire est dans $M$.
+
+(5) En déduire que $M$ est algébrique.
+
+\begin{corrige}
+(0) En remarquant que si $n = |w|$ alors $|ww| = 2n$, on constate que
+  tout mot de la forme $ww$ est de longueur paire, et de plus, que
+  pour un mot de longueur $2n$, être de la forme $ww$ signifie que son
+  préfixe de longueur $n$ soit égal à son suffixe de longueur $n$ ;
+  c'est-à-dire, si $t = x_1\cdots x_{2n}$, que $x_1\cdots x_n =
+  x_{n+1}\cdots x_{2n}$, ce qui signifie exactement $x_i = x_{n+i}$
+  pour tout $1\leq i\leq n$.
+
+(1) La règle $A \rightarrow a \,|\, aAa \,|\, aAb \,|\, bAa \,|\, bAb$
+  permet de faire à partir de $A$ une dérivation qui ajoute un nombre
+  quelconque de fois une lettre ($a$ ou $b$) de chaque part de $A$, et
+  finalement remplace ce $A$ par $a$.  On obtient donc ainsi
+  exactement les mots de longueur impaire ayant un $a$ comme lettre
+  centrale : $L(G,A) = \{w_1aw_2 : |w_1|=|w_2|\}$.  De même, $L(G,B) =
+  \{w_1bw_2 : |w_1|=|w_2|\}$.
+
+(2) Tout mot de longueur impaire est soit dans $L(G,A)$ soit dans
+  $L(G,B)$ selon que sa lettre centrale est un $a$ ou un $b$.  Il est
+  donc dans $L(G)$ en vertu des règles $S\rightarrow A$ et
+  $S\rightarrow B$.
+
+(3) Soit $t = x_1\cdots x_{2n}$ un mot de $M$ de longueur paire $2n$ :
+  d'après (0), il existe $i$ tel que $x_i \neq x_{n+i}$.  Posons alors
+  $u = x_1\cdots x_{2i-1}$ et $v = x_{2i}\cdots x_{2n}$.  Chacun de
+  $u$ et de $v$ est de longueur impaire.  De plus, leurs lettres
+  centrales sont respectivement $x_i$ et $x_{n+i}$, et elles sont
+  différentes : l'une est donc un $a$ et l'autre un $b$ ; mettons sans
+  perte de généralité que $x_i = a$ et $x_{n+i} = b$.  Alors $u \in
+  L(G,A)$ d'après (1) et $v \in L(G,B)$ : le mot $t = uv$ s'obtient
+  donc par la règle $S \rightarrow AB$ (suivie de dérivations de $u$ à
+  partir de $A$ et de $v$ a partir de $B$) : ceci montre bien $t \in
+  L(G)$.
+
+(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de
+  longueur impaire.  Un mot $t$ de $L(G)$ de longueur paire $2n$
+  dérive donc forcément de $AB$ ou de $BA$.  Sans perte de généralité,
+  supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient
+  à $M$.  Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le
+  facteur de $t$ qui dérive de $B$ : on sait alors (toujours
+  d'après (1)) que $u$ s'écrit sous la forme $x_1\cdots x_{2i-1}$ où
+  la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme
+  (quitte à continuer la numérotation des indices) $x_{2i}\cdots
+  x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$.  Alors $x_{n+i}
+  \neq x_i$ donc le mot $t$ est dans $M$ d'après (0).
+
+(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de
+  longueur impaire est dans les deux et qu'un mot de longueur paire
+  est dans l'un si et seulement si il est dans l'autre.  On a donc
+  montré que $M$ est algébrique.
+\end{corrige}
+
+
+%
+
+\exercice\label{square-words-not-algebraic}
+
+Soit $\Sigma = \{a,b\}$.  Montrer que le langage $Q := \{ww :
+w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit,
+des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou
+encore $aabbaabb$ sont dans $Q$) n'est pas algébrique.  On pourra pour
+cela considérer son intersection avec le langage $L_0$ dénoté par
+l'expression rationnelle $a{*}b{*}a{*}b{*}$ et appliquer le lemme de
+pompage.
+
+\begin{corrige}
+Supposons par l'absurde que $Q$ soit algébrique : alors son
+intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} :
+m,n,m',n' \in \mathbb{N}\}$ est encore algébrique.  Or $Q \cap L_0 =
+\{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$.  On va maintenant utiliser
+le lemme de pompage pour arriver à une contradiction.
+
+Appliquons le lemme de pompage pour les langages algébriques au
+langage $Q \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$
+considéré : appelons $k$ l'entier dont le lemme de pompage garantit
+l'existence.  Considérons le mot $t := a^k b^k a^k b^k$ : dans la
+suite de cette démonstration, on appellera « bloc » de $t$ un des
+quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$.  D'après la propriété de
+$k$ garantie par le lemme de pompage, il doit exister une
+factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$,
+(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in Q \cap L_0$ pour
+tout $i\geq 0$.
+
+Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e.,
+doit être de la forme $a^\ell$ ou $b^\ell$, sinon sa répétition ($v^i$
+ou $x^i$ pour $i\geq 2$, qui appartient à $L_0$ d'après (iii)) ferait
+apparaître plus d'alternations entre $a$ et $b$ que le langage $L_0$
+ne le permet.  Par ailleurs, la propriété (ii) assure que le facteur
+$vwx$ ne peut rencontrer qu'un ou deux blocs de $t$ (pas plus).
+Autrement dit, $v$ et $x$ sont contenus dans deux blocs de $t$ qui
+sont identiques ou bien consécutifs\footnote{La formulation est
+  choisie pour avoir un sens même si $v$ ou $x$ est le mot vide (ce
+  qui est possible \textit{a priori}).}.
+
+D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le
+mot vide.  Si ce facteur non trivial est dans le premier bloc $a^k$,
+l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient
+d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$
+avec $k'>k$ si $i>1$, qui n'appartient pas à $Q\cap L_0$, une
+contradiction.  De même, le facteur non trivial est dans le premier
+bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc
+$uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si
+$i>1$, qui n'appartient pas à $Q\cap L_0$, de nouveau une
+contradiction.  Les deux autres cas sont analogues.
+\end{corrige}
+
+\textbf{Remarque :} Les exercices \ref{non-square-words-is-algebraic}
+et \ref{square-words-not-algebraic} mis ensemble donnent un exemple
+explicite d'un langage $M$ algébrique dont le complémentaire $Q$ n'est
+pas algébrique.
+
+%
+
+\exercice
+
+On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
+sur l'alphabet $\Sigma = \{a,b\}$ :
+\[
+S \rightarrow aSS \;|\; b
+\]
+Soit $L = L(G)$ le langage algébrique qu'elle engendre.
+
+(0) Donner quelques exemples de mots dans $L$.
+
+(1) Expliquer pourquoi un $w\in \Sigma^*$ appartient à $L$ si et
+seulement si : soit $w = b$, soit il existe $u,v\in L$ tels que $w =
+auv$.
+
+(2) En déduire par récurrence sur la longueur $|w|$ de $w$ que si $w
+\in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$
+(c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$).  Autrement
+dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un
+mot qui n'appartient jamais à $L$.  (Indication : si on a $auvz =
+au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
+(iii) $|u'|=|u|$.)
+
+(3) En déduire que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
+et $v=v'$.  (Indication analogue.)
+
+(4) En déduire que $G$ est inambiguë, c'est-à-dire que chaque mot
+$w\in L$ a un unique arbre d'analyse pour $G$ (on pourra reprendre
+l'analyse de la question (1) et procéder de nouveau par récurrence
+sur $|w|$).
+
+(5) En s'inspirant des questions précédentes, décrire un algorithme
+simple (en une seule fonction récursive) qui, donné un mot
+$w\in\Sigma^*$ renvoie la longueur du préfixe de $w$ appartenant à $L$
+s'il existe (il est alors unique d'après la question (2)) ou bien
+« échec » s'il n'existe pas ; expliquer comment s'en servir pour
+décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux
+selon que $w\in L$ ou $w\not\in L$).
+
+\begin{corrige}
+(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
+  $ababb$ ou encore $aabbabb$.
+
+(1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$
+  pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés
+  selon l'une des deux règles de la grammaire, soit $S\rightarrow b$
+  ou bien $S\rightarrow aSS$, autrement dit, soit elle a un unique
+  fils étiqueté $b$, soit elle a trois fils étiquetés respectivement
+  $a,S,S$.  Dans le premier cas, le mot $w$ est simplement $b$ ; dans
+  le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour
+  racine les deux fils étiquetés $S$ sont encore des arbres d'analyse
+  pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des
+  arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles
+  de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de
+  profondeur), alors on a $w = auv$ et $u,v\in L$ (puisqu'ils ont des
+  arbres d'analyse pour $G$).
+
+La réciproque est analogue : le mot $b$ appartient trivialement à $L$,
+et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
+\mathscr{V}$ pour $G$, et on peut fabriquer un arbre d'analyse pour $w
+:= auv$ qui a une racine étiquetée $S$ ayant trois fils étiquetés
+$a,S,S$, ces deux derniers ayant pour descendants des sous-arbres
+donnés par $\mathscr{U}$ et $\mathscr{V}$.
+
+\smallbreak
+
+(2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz
+\not\in L$ pour tout $z \in \Sigma^+$.  La récurrence permet de
+supposer la conclusion déjà connue pour tout mot de longueur $<|w|$.
+D'après la question (1), le mot $w$ est soit $b$ soit de la forme
+$auv$ avec $u,v\in L$ et trivialement $|u|<|w|$ et $|v|<|w|$.  Si
+$w=b$, il est évident qu'aucun mot de la forme $bz$ ne peut appartenir
+à $L$ (la question (1) montre que les seuls mots de $L$ sont le mot
+$b$ et des mots commençant par $a$).  Il reste le cas $w = auv$ : on
+veut montrer que $wz$, c'est-à-dire $auvz$, n'appartient pas à $L$.
+Mais s'il y a appartenait, toujours d'après la question (1), il serait
+de la forme $au'v'$ (le cas $b$ étant trivialement exclu), où $u',v'
+\in L$ ; notamment, $uvz = u'v'$.  Distinguons trois cas : (i) soit
+$|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, c'est-à-dire
+que $u'$ peut s'écrire sous la forme $u' = ut$ pour un $t\in
+\Sigma^+$, et par l'hypothèse de récurrence, on a $u'\not\in L$, une
+contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
+strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
+u't$ pour un $t\in\Sigma^+$, et par l'hypothèse de récurrence (puisque
+$|u'|<|u|<|w|$), on a $u\not\in L$, de nouveau une contradiction ;
+(iii) soit $|u'|=|u|$, donc $u'=u$ (puisqu'ils sont préfixes de même
+longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais
+comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$,
+encore une contradiction.
+
+\smallbreak
+
+(3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
+et $v=v'$.  On a notamment $uv = u'v'$.  Distinguons trois cas :
+(i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$,
+c'est-à-dire que $u'$ peut s'écrire sous la forme $u' = ut$ pour un
+$t\in \Sigma^+$, et par la question (2), on a $u'\not\in L$, une
+contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
+strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
+u't$ pour un $t\in\Sigma^+$, et par la question (2), on a $u\not\in
+L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$
+(puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$),
+et on a alors $v' = v$, la conclusion annoncéee.
+
+\smallbreak
+
+(4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse
+pour $G$.  On procède par récurrence sur $|w|$, ce qui permet de
+supposer la conclusion connue pour tout mot de longueur $<|w|$.  Comme
+on l'a expliqué en (1), il y a deux possibilités pour un arbre
+d'analyse de $w$ : soit la racine a un unique fils étiqueté $b$ et le
+mot analysé est $w=b$, soit la racine a trois fils étiquetés $a,S,S$,
+et des deux derniers fils partent des arbres d'analyse
+$\mathscr{U},\mathscr{V}$ de mots $u,v\in L$ tels que $w=auv$.  Ces
+deux cas sont évidemment incompatibles : il reste donc simplement à
+expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont
+uniquement déterminés.  Or la question (3) assure que $u,v$ (tels que
+$w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence
+permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres
+d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement
+déterminés, comme on le voulait.
+
+\smallbreak
+
+(5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe
+  dans $L$ » suivante renvoie la longueur du préfixe de $w$
+appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
+\begin{itemize}
+\item si $w=\varepsilon$, renvoyer échec,
+\item si la première lettre de $w$ est $b$, renvoyer $1$,
+\item sinon (la première lettre de $w$ est $a$), soit $x$ le suffixe
+  de $w$ correspondant (c'est-à-dire $w = ax$, ou si on préfère, $x$
+  enlève la première lettre de $w$),
+\item appeler la fonction elle-même (rechercher préfixe dans $L$)
+  sur $x$ :
+\item si elle échoue, renvoyer échec,
+\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur
+  $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, ou si
+  on préfère, $y$ enlève les $k$ premières lettres de $x$),
+\item appeler la fonction elle-même (rechercher préfixe dans $L$)
+  sur $y$ :
+\item si elle échoue, renvoyer échec,
+\item si elle retourne $\ell$, retourner $1+k+\ell$ (en effet, on a $w
+  = auvz$ où $u$ est de longueur $k$ et $v$ est de longueur $\ell$).
+\end{itemize}
+
+Pour savoir si un mot appartient à $w$, il s'agit simplement de
+vérifier que la valeur retournée (=la longueur du préfixe appartenant
+à $L$) n'est pas un échec et est égale à la longueur $|w|$.
+
+La terminaison de cet algorithme est claire par récurrence sur la
+longueur (chaque appel récursif est fait sur un mot de longueur
+strictement plus courte), et sa correction est garantie par les
+questions précédentes : les cas $b$ et $auv$ sont disjoints et dans le
+dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce
+qu'affirme la non-ambiguïté de la grammaire).
+
+(Il s'agit ici du cas le plus simple d'un analyseur LL, et
+l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1)
+camouflé sous forme d'analyseur par descente récursive.)
+\end{corrige}
+
+%
+
+\exercice
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S, T, U, V\}$ sur l'alphabet $\Sigma =
+\{{\#},{@},{(},{)}, x, y, z\}$ (soit $7$ lettres) donnée par
+\[
+\begin{aligned}
+S &\rightarrow T \;|\; S\mathbin{\#}T\\
+T &\rightarrow U \;|\; U\mathbin{@}T\\
+U &\rightarrow V \;|\; (\,S\,)\\
+V &\rightarrow x \;|\; y \;|\; z\\
+\end{aligned}
+\]
+(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les
+parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes
+auxquelles on peut vouloir appliquer ces opérations.)
+
+La grammaire en question est inambiguë (on ne demande pas de le
+démontrer).
+
+(1) Donner les arbres d'analyse (=de dérivation) des mots suivants :
+(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$,
+(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$,
+(e) $(x\mathbin{\#}y)\mathbin{@}z$.
+
+\begin{corrige}
+On obtient les arbres d'analyse suivants :
+(a) % S<S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>#.T<U<V<z.>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (S2) at (0.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (T0) at (0.000bp,-80.000bp) [draw=none] {$T$};  \draw (S2) -- (T0);
+\node (U0) at (0.000bp,-100.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-120.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-140.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-60.000bp) [draw=none] {$\#$};  \draw (S1) -- (o0);
+\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$};  \draw (S1) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o1);
+\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T2);
+\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(b) % S<S<T<U<V<x.>>>>#.T<U<V<y.>>@.T<U<V<z.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (0.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T0) at (0.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T0);
+\node (U0) at (0.000bp,-70.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-90.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-110.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o0);
+\node (T1) at (60.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T1);
+\node (U1) at (40.000bp,-60.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-80.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-100.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-60.000bp) [draw=none] {$@$};  \draw (T1) -- (o1);
+\node (T2) at (80.000bp,-60.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-100.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-120.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(c) % S<S<T<U<V<x.>>@.T<U<V<y.>>>>>#.T<U<V<z.>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (53.333bp,0.000bp) [draw=none] {$S$};
+\node (S1) at (20.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (T0) at (20.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T0);
+\node (U0) at (0.000bp,-80.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-100.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-120.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-80.000bp) [draw=none] {$@$};  \draw (T0) -- (o0);
+\node (T1) at (40.000bp,-80.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-100.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-120.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-140.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-30.000bp) [draw=none] {$\#$};  \draw (S0) -- (o1);
+\node (T2) at (80.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T2);
+\node (U2) at (80.000bp,-50.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-70.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-90.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(d) % S<T<U<V<x.>>@.T<U<V<y.>>@.T<U<V<z.>>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (26.667bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (26.667bp,-20.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (V0) at (0.000bp,-70.000bp) [draw=none] {$V$};  \draw (U0) -- (V0);
+\node (x0) at (0.000bp,-90.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (20.000bp,-50.000bp) [draw=none] {$@$};  \draw (T0) -- (o0);
+\node (T1) at (60.000bp,-50.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
+\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V1) at (40.000bp,-100.000bp) [draw=none] {$V$};  \draw (U1) -- (V1);
+\node (y0) at (40.000bp,-120.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (o1) at (60.000bp,-80.000bp) [draw=none] {$@$};  \draw (T1) -- (o1);
+\node (T2) at (80.000bp,-80.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
+\node (U2) at (80.000bp,-100.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V2) at (80.000bp,-120.000bp) [draw=none] {$V$};  \draw (U2) -- (V2);
+\node (z0) at (80.000bp,-140.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\hskip1cmplus5cmminus.5cm
+(e) % S<T<U<(.S<S<T<U<V<x.>>>>#.T<U<V<y.>>>>).>@.T<U<V<z.>>>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (86.667bp,0.000bp) [draw=none] {$S$};
+\node (T0) at (86.667bp,-20.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
+\node (U0) at (40.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
+\node (p0) at (0.000bp,-80.000bp) [draw=none] {$($};  \draw (U0) -- (p0);
+\node (S1) at (40.000bp,-80.000bp) [draw=none] {$S$};  \draw (U0) -- (S1);
+\node (S2) at (20.000bp,-110.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (T1) at (20.000bp,-130.000bp) [draw=none] {$T$};  \draw (S2) -- (T1);
+\node (U1) at (20.000bp,-150.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
+\node (V0) at (20.000bp,-170.000bp) [draw=none] {$V$};  \draw (U1) -- (V0);
+\node (x0) at (20.000bp,-190.000bp) [draw=none] {$x$};  \draw (V0) -- (x0);
+\node (o0) at (40.000bp,-110.000bp) [draw=none] {$\#$};  \draw (S1) -- (o0);
+\node (T2) at (60.000bp,-110.000bp) [draw=none] {$T$};  \draw (S1) -- (T2);
+\node (U2) at (60.000bp,-130.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
+\node (V1) at (60.000bp,-150.000bp) [draw=none] {$V$};  \draw (U2) -- (V1);
+\node (y0) at (60.000bp,-170.000bp) [draw=none] {$y$};  \draw (V1) -- (y0);
+\node (p1) at (80.000bp,-80.000bp) [draw=none] {$)$};  \draw (U0) -- (p1);
+\node (o1) at (100.000bp,-50.000bp) [draw=none] {$@$};  \draw (T0) -- (o1);
+\node (T3) at (120.000bp,-50.000bp) [draw=none] {$T$};  \draw (T0) -- (T3);
+\node (U3) at (120.000bp,-70.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
+\node (V2) at (120.000bp,-90.000bp) [draw=none] {$V$};  \draw (U3) -- (V2);
+\node (z0) at (120.000bp,-110.000bp) [draw=none] {$z$};  \draw (V2) -- (z0);
+\end{tikzpicture}
+\end{corrige}
+
+(2) En considérant que $(w)$ a le même effet ou la même valeur
+que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle
+prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est
+  \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus
+  w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » et
+  « $u\boxplus v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».}
+sur l'autre ?  Laquelle ?\quad (b) L'opération $\#$
+s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$
+  \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se
+  comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à
+    droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme
+  « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad
+(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ?
+
+\begin{corrige}
+(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que
+  l'opération $@$ est prioritaire sur $\#$ (elle est toujours plus
+  profonde dans l'arbre, c'est-à-dire appliquée en premier aux
+  opérandes).\quad (b) L'arbre d'analyse (a) de la question (1) montre
+  que $\#$ s'associe à gauche (le $\#$ entre les deux opérandes gauche
+  est plus profond, c'est-à-dire appliqué en premier).\quad
+  (c) Symétriquement, l'arbre d'analyse (d) de la question (1) montre
+  que $@$ s'associe à droite.
+\end{corrige}
+
+\smallskip
+
+(La question (3) est indépendante de (1) et (2).  Par ailleurs, on
+pourra, si on souhaite s'épargner des confusions, choisir d'appeler
+$a$ la lettre « parenthèse ouvrante » de $\Sigma$ et $b$ la lettre
+« parenthèse fermante » afin de les distinguer des parenthèses
+mathématiques.)
+
+(3) Soit $L = L(G)$ le langage engendré par $G$.  Soit $M$ le langage
+des mots sur $\Sigma$ formés d'un certain nombre de parenthèses
+ouvrantes, puis de la lettre $x$, puis d'un certain nombre
+(possiblement différent) de parenthèses fermantes : autrement dit, des
+mots de la forme « ${(}^i\, x\, {)}^j$ », où on a noté « ${(}^i$ » une
+succession de $i$ parenthèses ouvrantes et « ${)}^j$ » une succession
+de $j$ parenthèses fermantes (on pourra noter ce mot $a^i x b^j$ si on
+préfère).\quad (a) Décrire le langage $L\cap M$ (des mots de $L$ qui
+appartiennent aussi à $M$).\quad (b) Ce langage $L\cap M$ est-il
+rationnel ?\quad (c) Le langage $L$ est-il rationnel ?
+
+\begin{corrige}
+(a) Cherchons pour quelles valeurs $(i,j) \in \mathbb{N}^2$ le mot
+  « ${(}^i\, x\, {)}^j$ » de $M$ appartient à $L$.  La dérivation $S
+  \Rightarrow T \Rightarrow U \Rightarrow (S) \Rightarrow (T)
+  \Rightarrow (U) \Rightarrow ((S)) \Rightarrow \cdots
+  \Rightarrow{(}^i\, S\, {)}^i \Rightarrow{(}^i\, T\, {)}^i
+  \Rightarrow{(}^i\, U\, {)}^i \Rightarrow{(}^i\, V\, {)}^i
+  \Rightarrow{(}^i\, x\, {)}^i$ montre que c'est le cas si $j=i$,
+  autrement dit s'il y a autant de parenthèses fermantes qu'ouvrantes.
+  Mais réciproquement, la propriété d'avoir autant de parenthèses
+  fermantes qu'ouvrantes est préservée par toutes les productions
+  de $G$ (et est satisfaite par l'axiome), donc est vérifiée par tout
+  mot de $L=L(G)$.  On a donc prouvé que le $L\cap M$ est l'ensemble
+  des mots de la forme « ${(}^i\, x\, {)}^i$ » où $i\in \mathbb{N}$.
+
+(b) Le langage $L\cap M$ constitué des mots de la forme « ${(}^n\,
+  x\, {)}^n$ » où $i\in \mathbb{N}$ n'est pas rationnel.  Cela résulte
+  du lemme de pompage (presque exactement comme l'exemple du langage
+  $\{a^n b^n : i\in\mathbb{N}\}$ donné en cours) : donnons l'argument
+  en remplaçant la parenthèse ouvrante par $a$ et la parenthèse
+  fermante par $b$ pour plus de clarté notationnelle.  Appliquons le
+  lemme de pompage pour les langages rationnels au langage $L \cap M =
+  \{a^n x b^n : i\in\mathbb{N}\}$ supposé par l'absurde être
+  rationnel : appelons $k$ l'entier dont le lemme de pompage garantit
+  l'existence.  Considérons le mot $t := a^k x b^k$ : il doit alors
+  exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq
+  1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L\cap M$ pour tout $i\geq
+  0$.  La propriété (ii) assure que $uv$ est formé d'un certain nombre
+  de répétitions de la lettre $a$ (car tout préfixe de longueur $\leq
+  k$ de $a^k x b^k$ est de cette forme) ; disons $u = a^\ell$ et $v =
+  a^m$, si bien que $w = a^{k-\ell-m} x b^k$.  La propriété (i)
+  donne $m\geq 1$.  Enfin, la propriété (iii) affirme que le mot
+  $uv^iw = a^{k+(i-1)m} x b^k$ appartient à $L\cap M$ ; mais dès que
+  $i\neq 1$, ceci est faux : il suffit donc de prendre $i=0$ pour
+  avoir une contradiction.
+
+(c) Le langage $M$ est rationnel puisqu'il est dénoté par l'expression
+  rationnelle $a{*}xb{*}$ (toujours en notant $a$ la parenthèse
+  ouvrante et $b$ la parenthèse fermante).  Si le langage $L$ était
+  rationnel, le langage $L\cap M$ le serait aussi (on sait que
+  l'intersection de deux langages rationnels est rationnelle), ce qui
+  n'est pas le cas d'après la question (b).  Le langage $L$ n'est donc
+  pas rationnel.
+\end{corrige}
+
+
+%
+
+\exercice
+
+On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
+sur l'alphabet $\Sigma = \{a,b\}$ :
+\[
+S \rightarrow SaS \;|\; b
+\]
+Soit $L = L(G)$ le langage algébrique qu'elle engendre.
+
+(0) Donner quelques exemples de mots dans $L$.
+
+(1) Cette grammaire $G$ est-elle ambiguë ?
+
+(2) Décrire simplement le langage $L$.
+
+(3) Donner une grammaire inambiguë engendrant le même langage $L$
+que $G$.
+
+\begin{corrige}
+(0) Quelques exemples de mots dans $L$ sont $b$, $bab$, $babab$, et
+  ainsi de suite (cf. (2)).
+
+(1) La grammaire $G$ est ambiguë : le mot $babab$ a deux arbres
+  d'analyse différents, à savoir
+\begin{center}
+\tikzstyle{automaton}=[scale=0.5]
+%%% begin ex3pt1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (S3) at (27bp,90bp) [draw,draw=none] {$S$};
+  \node (S2) at (243bp,162bp) [draw,draw=none] {$S$};
+  \node (S1) at (99bp,162bp) [draw,draw=none] {$S$};
+  \node (S0) at (171bp,234bp) [draw,draw=none] {$S$};
+  \node (S4) at (171bp,90bp) [draw,draw=none] {$S$};
+  \node (a1) at (99bp,90bp) [draw,draw=none] {$a$};
+  \node (a0) at (171bp,162bp) [draw,draw=none] {$a$};
+  \node (b0) at (243bp,90bp) [draw,draw=none] {$b$};
+  \node (b1) at (27bp,18bp) [draw,draw=none] {$b$};
+  \node (b2) at (171bp,18bp) [draw,draw=none] {$b$};
+  \draw [] (S1) ..controls (70.042bp,132.85bp) and (55.714bp,118.92bp)  .. (S3);
+  \draw [] (S0) ..controls (142.04bp,204.85bp) and (127.71bp,190.92bp)  .. (S1);
+  \draw [] (S0) ..controls (171bp,204.85bp) and (171bp,190.92bp)  .. (a0);
+  \draw [] (S2) ..controls (243bp,132.85bp) and (243bp,118.92bp)  .. (b0);
+  \draw [] (S1) ..controls (99bp,132.85bp) and (99bp,118.92bp)  .. (a1);
+  \draw [] (S0) ..controls (199.96bp,204.85bp) and (214.29bp,190.92bp)  .. (S2);
+  \draw [] (S3) ..controls (27bp,60.846bp) and (27bp,46.917bp)  .. (b1);
+  \draw [] (S4) ..controls (171bp,60.846bp) and (171bp,46.917bp)  .. (b2);
+  \draw [] (S1) ..controls (127.96bp,132.85bp) and (142.29bp,118.92bp)  .. (S4);
+%
+\end{tikzpicture}
+
+%%% end ex3pt1 %%%
+\end{center}
+et son symétrique par rapport à l'axe vertical.
+
+\smallbreak
+
+(2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par
+l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse
+entrevoir.  Pour cela, il suffit de voir que l'ensemble des
+pseudo-mots (:= mots sur l'ensemble des terminaux et des nonterminaux)
+qu'on peut dériver de $S$ dans $G$ est le langage $((S|b)a){*}(S|b)$
+constitué des pseudo-mots de la forme $xaxax\cdots ax$ où chaque $x$
+est soit un $S$ soit un $b$, indépendamment les uns des autres.  Or il
+est clair que remplacer un $x$ (et notamment, remplacer un $S$) par
+$SaS$ (qui est de la forme $xax$) dans un pseudo-mot de cette forme
+donne encore un pseudo-mot de cette forme : ceci montre qu'une
+dérivation de $G$, quelle que soit l'application faite de la règle
+$S\rightarrow SaS$, donne des pseudo-mots de cette forme, donc tout
+pseudo-mot obtenu par dérivation de $S$ dans la grammaire $G$ est de
+la forme qu'on vient de dire ; et réciproquement, il est facile de
+produire n'importe quel nombre $n$ de répéritions du motif $aS$ en
+appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on
+peut ensuite librement transformer certains $S$ en $b$.
+
+\smallbreak
+
+(3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le
+même langage que $G$ d'après la question précédente ; et il est
+évident que cette grammaire est inambiguë : toutes les dérivations
+sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
+(ba)^n S$ suivie éventuellement de $\Rightarrow (ba)^n b$.
+\end{corrige}
+
+%
+%
+%
+
+\subsection{Introduction à la calculabilité}
+
+\exercice
+
+Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
+suivantes sont indépendantes (mais on remarquera leur parallélisme).
+Ne pas hésiter à décrire les algorithmes de façon succincte et
+informelle.
+
+(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
+un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$
+sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
+du langage $\Sigma^*$ de tous les mots sur $\Sigma$.  (Autrement dit,
+l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
+$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
+$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
+On ne demande pas que l'algorithme soit efficace.)
+
+(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée
+une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
+langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
+tous les mots.  (« Semi-décider » signifie que l'algorithme $A_2$ doit
+prendre en entrée une grammaire hors contexte $G$, terminer en temps
+fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
+$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
+  termine parfois en répondant « faux », mais ce ne sera pas utile.}
+si $L_G = \Sigma^*$.)  Indication : on peut tester tous les mots
+possibles.
+
+(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on
+lui fournit en entrée un algorithme $T$ qui décide un langage $L_T
+\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
+fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
+« faux », et $L_T$ est le langage des mots sur lesquels il répond
+« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
+différent de $\Sigma^*$.  (C'est-à-dire que $A_3$ doit terminer en
+répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
+L_T$, et ne pas terminer si $L_T = \Sigma^*$.)  Indication : la même
+approche permet de traiter les questions (2) et (3).
+
+(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui,
+dans les mêmes conditions que $A_3$, décide (au lieu de seulement
+semi-décider) si $L_T$ est différent de $\Sigma^*$.  (C'est-à-dire que
+$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
+mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
+\Sigma^*$.)  Indication : expliquer comment on pourrait utiliser un
+tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à
+fabriquer un $T$ qui rejette un mot précisément si un programme donné
+s'arrête.
+
+\begin{corrige}
+(1) Donnée une expression rationnelle $r$, on sait qu'on peut
+  algorithmiquement fabriquer un automate fini non-déterministe à
+  transitions spontanées qui reconnaît exactement le langage $L_r$
+  dénoté par $r$, et ensuite éliminer les transitions spontanées et
+  déterminiser l'automate pour obtenir un automate fini déterministe
+  complet reconnaissant $L_r$.  Sur un tel automate, savoir si $L_r
+  \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$
+  non-final accessible, il existe un mot rejeté par l'automate (i.e.,
+  n'appartenant pas à $L_r$), à savoir le mot lu en suivant les
+  étiquettes d'un chemin quelconque de l'état initial $q_0$
+  jusqu'à $q$, et inversement, si tous les états sont finaux, il est
+  trivial que l'automate accepte tous les mots.  (On pouvait aussi
+  minimiser l'automate et le comparer à l'automate minimal trivial qui
+  reconnaît le langage $\Sigma^*$.)
+
+\smallbreak
+
+(2) On sait qu'il existe un algorithme qui, donnée une grammaire
+hors-contexte $G$ et un mot $w$, décide si $w \in L_G$.  Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_2$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable
+d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w
+\in L_G$, et si ce n'est pas le cas, termine immédiatement en
+répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$),
+tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais.
+
+\smallbreak
+
+(3) On procède exactement comme en (2) : par hypothèse on dispose d'un
+algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$.  Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_3$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant
+l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est
+pas le cas, termine immédiatement en répondant « vrai » (on a trouvé
+un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas,
+l'algorithme $A_3$ ne terminera jamais.
+
+\smallbreak
+
+(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme
+on vient de dire, et montrons pour arriver à une contradiction qu'on
+peut s'en servir pour résoudre le problème de l'arrêt.  On se donne
+donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir
+(en utilisant $A_4$) si $S$ termine sur l'entrée $x$.  Pour cela, on
+va construire un $T$ auquel appliquer $A_4$.
+
+Voici une solution possible : donné un mot $w \in \Sigma^*$, le
+programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
+(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$
+étapes : si l'exécution termine dans le temps imparti, alors $T$
+rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
+termine et répond « vrai » ou « faux », donc il est une entrée
+légitime à $A_4$).  Cette construction fait que $L_T$ rejette au moins
+un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$
+ne termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de
+$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
+sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
+
+\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur
+$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
+$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
+courant et le contenu du ruban à chaque étape), du début à l'arrêt.
+Une telle trace d'exécution existe donc précisément si $S$ termine
+sur $x$.  Or il est visiblement décidable de savoir si un mot $w$
+donné est une trace d'exécution (il suffit de vérifier qu'à chaque
+étape la machine a bien fait ce qu'elle devait faire).  On peut donc
+écrire un algorithme $T$ qui termine toujours et accepte précisément
+les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$.
+Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors
+exactement qu'une trace d'exécution existe, donc que $S$ termine
+sur $x$.  Ainsi l'utilisation de $A_4$ permet de savoir
+algorithmiquement si $S$ termine sur $x$, ce qui contredit
+l'indécidabilité du problème de l'arrêt.
+\end{corrige}
+
+%
+
+\exercice
+
+(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
+= \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
+$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?
+
+(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
+programme (ou, si on préfère, de la $e$-ième machine de Turing),
+exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
+est-il décidable ?  Semi-décidable ?
+
+(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
+programme (ou, si on préfère, de la $e$-ième machine de Turing),
+exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
+Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
+de l'arrêt.)
+
+\begin{corrige}
+(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
+  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
+  de l'algorithme suivant pour décider si $w\in L$ : si
+  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
+  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
+  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
+  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
+  commençant à la position $i \ell$) : s'ils sont tous égaux, renvoyer
+  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
+  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
+    fortiori} semi-décidable).
+
+\smallbreak
+
+(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
+  évidemment calculable.  On peut ensuite lancer l'exécution du
+  $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
+  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
+  exemple, en simulant la $e$-ième machine de Turing sur une machine
+  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
+  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
+  est bien décidable (et \textit{a fortiori} semi-décidable).
+
+\smallbreak
+
+(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
+  différence est que le problème de l'arrêt est l'ensemble des couples
+  $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
+  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
+  que cette limitation ne rend pas pour autant calculable l'ensemble
+  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
+  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
+  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
+  un tel $e'$ se calcule algorithmiquement\footnote{Techniquement, on
+    invoque ici le théorème s-m-n ; mais dans les faits, il s'agit
+    essentiellement d'ajouter une ligne « \texttt{let
+      n=}(représentation décimale de $n$) » au début d'un programme,
+    ce qui est certainement faisable.} à partir de $e$ et $n$.
+  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
+  autre entrée) se comporte donc comme l'exécution du programme $e$
+  sur l'entrée $n$, et notamment, termine si et seulement si elle
+  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
+  dans cette question si et seulement si $(e,n)$ appartient au
+  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
+  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
+  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
+  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
+  semi-décidable : il suffit de lancer l'exécution du programme $e$
+  sur l'entrée $42$ et renvoyer vrai si elle termine (si elle ne
+  termine pas, on ne termine pas).
+\end{corrige}
+
+%
+
+\exercice
+
+Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
+des langages sur $\Sigma$.
+
+(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors
+$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer
+que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce
+dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un
+mot de longueur $n$, comment énumérer toutes les façons de le
+factoriser en mots de longueur non nulle).
+
+(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
+alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
+semi-décidables ; montrer que si un langage $L$ est semi-décidable
+alors $L^*$ est semi-décidable.
+
+\begin{corrige}
+(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
+  $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$,
+  l'algorithme $T_i$ termine toujours en temps fini, en répondant oui
+  si $w\in L_i$ et non si $w\not\in L_i$).
+
+Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot
+$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si
+l'un des deux répond oui, on répond oui, sinon on répond non
+(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et
+$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur
+« ou » logique).  De même pour décider $L_1\cap L_2$, il suffit de
+lancer successivement $T_1$ et $T_2$, si les deux répondent oui on
+répond oui, sinon on répond non (i.e., on calcule les valeurs de
+vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on
+calcule ensuite leur « et » logique).
+
+Pour décider $L_1 L_2$, on effectue une boucle sur toutes les
+factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les
+longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe
+de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$,
+et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$
+pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine
+l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune
+paire ne convient, on répond non.
+
+L'algorithme pour décider $L^*$ est semblable : il s'agit de tester
+toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs
+de longueur non nulle.  (On peut d'ores et déjà exclure
+$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.)
+Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de
+facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
+boucles emboîtées pour déterminer les limites des facteurs
+$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
+par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
+lorsque $i_1+\cdots+i_k = n$, appeler $u_j$ le facteur de $w$ de
+longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$).  Pour
+chaque factorisation comme on vient de le dire, on teste si tous les
+$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
+$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on
+renvoie faux.
+
+(Dans l'algorithme qui précède, on a écarté les factorisations faisant
+intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en
+faisant intervenir le mot vide, quitte à retirer celui-ci, il est
+encore factorisable en mots non vides de $L$.)
+
+\smallbreak
+
+(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
+n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
+terminer.  À part pour l'intersection, on doit donc les lancer « en
+parallèle » et pas « en série » : lorsqu'on dira qu'on lance deux
+algorithmes $T$ et $T'$ « en parallèle », cela signifie qu'on exécute
+une étape du calcul de $T$, puis une étape de $T'$, puis de nouveau
+une de $T$, et ainsi de suite en alternant entre les deux, jusqu'à ce
+que l'un termine et renvoie vrai.
+
+Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
+algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps
+fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour
+semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et
+$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on
+termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).
+
+Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
+de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
+tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
+$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
+algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
+calcul dans son ensemble ne terminera pas.
+
+Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A)
+en lançant en parallèle les algorithmes pour tester toutes les
+différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots
+u_k$ (en mots non vides) du mot $w$.
+\end{corrige}
+
+%
+
+\exercice
+
+On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
+dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
+programme pour une machine de Turing) prenant en entrée un
+$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
+valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
+indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
+existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
+de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
+vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
+à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
+algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
+vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
+pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
+change rien).
+
+Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
+équivalence entre les affirmations suivantes :
+\begin{enumerate}
+\item la fonction $f$ est calculable,
+\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
+  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
+\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
+\end{enumerate}
+
+(Montrer que (3) implique (1) est le plus difficile : on pourra
+commencer par s'entraîner en montrant que (2) implique (1).  Pour
+montrer que (3) implique (2), on pourra chercher une façon de tester
+en parallèle un nombre croissant de valeurs de $p$ de manière à
+s'arrêter si l'une quelconque convient.)
+
+\begin{corrige}
+Montrons que (1) implique (2) : si on dispose d'un algorithme capable
+de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
+algorithme capable de décider si $p=f(n)$ (il suffit de calculer
+$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
+de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
+faux/$0$ sinon).
+
+Le fait que (2) implique (3) est évident car tout ensemble décidable
+est semi-décidable.
+
+Montrons que (2) implique (1) même si ce ne sera au final pas utile :
+supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
+donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
+$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
+qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
+l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
+puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
+sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
+$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
+valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
+de $T$.
+
+\smallbreak
+
+Reste à montrer que (3) implique (1) : supposons qu'on ait un
+algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
+termine en temps fini et répond oui si $p=f(n)$, et ne termine pas
+sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
+cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
+et faire tendre $M$ vers l'infini : plus exactement, on utilise
+l'algorithme $U$ suivant :
+\begin{itemize}
+\item pour $M$ allant de $0$ à l'infini,
+\begin{itemize}
+\item pour $p$ allant de $0$ à $M$,
+\begin{itemize}
+\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
+  plus $M$ étapes,
+\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
+  (sinon, continuer les boucles).
+\end{itemize}
+\end{itemize}
+\end{itemize}
+
+(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
+valeurs de $p$ de plus en plus grand et en attendant de plus en plus
+longtemps pour voir si l'une d'elles termine.)
+
+Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
+$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
+et on renvoie la valeur en question) ; il reste à expliquer pourquoi
+$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
+connaît pas) car la fonction $f$ était supposée définie partout, et
+lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
+terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
+à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
+prise par $p$ dans la boucle intérieure, et pour cette valeur,
+l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
+étapes, ce qui assure que $U$ termine effectivement.
+
+L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
+prouve (1).
+\end{corrige}
+
+%
+
+\exercice
+
+Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
+équivalence entre :
+\begin{itemize}
+\item l'ensemble $A$ est décidable,
+\item il existe une fonction calculable \emph{strictement croissante}
+  $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$.
+\end{itemize}
+
+\begin{corrige}
+Supposons $A$ décidable : on va construire $f$ comme indiqué.  Plus
+exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre
+croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$,
+et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter
+que $A$ est infini donc cette fonction est bien définie).  Montrons
+que $f$ est calculable : donné un entier $n$, on teste successivement
+si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque
+fois en utilisant un algorithme décidant $A$ (qui est censé exister
+par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus
+exactement :
+\begin{itemize}
+\item initialiser $m \leftarrow 0$,
+\item pour $k$ allant de $0$ à l'infini,
+\begin{itemize}
+\item interroger l'algorithme qui décide si $k\in A$,
+\item s'il répond « oui » :
+\begin{itemize}
+\item si $m=n$, terminer et renvoyer $k$,
+\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$).
+\end{itemize}
+\end{itemize}
+\end{itemize}
+La boucle termine car $A$ est infini.
+
+Réciproquement, supposons $f$ strictement croissante calculable et
+posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable.
+Or pour décider si $k \in A$, il suffit de calculer successivement
+$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$
+atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a
+trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a
+été sautée par la fonction $f$ et ne sera donc jamais atteinte).
+L'algorithme est donc explicitement :
+\begin{itemize}
+\item pour $n$ allant de $0$ à l'infini,
+\begin{itemize}
+\item calculer $f(n)$,
+\item si $f(n) = k$, renvoyer vrai,
+\item si $f(n) > k$, renvoyer faux.
+\end{itemize}
+\end{itemize}
+La boucle termine car toute fonction strictement croissante
+$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc
+$f(n)$ finit forcément par atteindre ou dépasser $k$).
+\end{corrige}
+
+%
+
+\exercice
+
+Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
+(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
+fournit le nombre $n$ en entrée, à supposer que cette exécution
+termine ; sinon, $S(e,n)$ n'est pas défini.
+
+Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
+et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
+défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
+égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
+e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
+terminent.
+
+Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
+calculable par un algorithme) : on pourra pour cela montrer que la
+connaissance de $M$ permet de résoudre le problème de l'arrêt.
+Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
+M(k)$ pour tout $k$ n'est calculable.  Montrer que même si $M'$
+vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
+pas calculable.
+
+\emph{Remarque :} La fonction $M$, ou différentes variantes de
+celle-ci, s'appelle fonction du « castor affairé ».  On peut montrer
+encore plus fort : si $F$ est une fonction calculable quelconque,
+alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$
+(autrement dit, la fonction $M$ finit par dépasser n'importe quelle
+fonction calculable : Radó, 1962, \textit{On Non-Computable
+  Functions}).
+
+\begin{corrige}
+Supposons que $M$ soit calculable.  On peut alors résoudre le problème
+de l'arrêt de la manière suivante : donné un algorithme $T$, de
+numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
+si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
+ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
+dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
+faux (il ne terminera jamais).  Cette résolution du problème de
+l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
+par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
+k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
+$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
+$M(k)$ étapes, il ne terminera jamais.
+
+Exactement le même argument montre que $M'$ n'est pas calculable sous
+l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
+pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
+comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
+convient.
+
+Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
+fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
+par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
+$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
+puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
+changer la valeur en un point d'une fonction calculable donne toujours
+une fonction calculable (même si on « ne connaît pas » la valeur à
+changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
+le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
+partout supérieure ou égale à $M$.
+\end{corrige}
+
+%
+
+\exercice
+
+Dans cet exercice, on s'intéresse au langage $L$ formé des
+programmes $e$ (codés, dans une formalisation quelconque de la
+calculabilité\footnote{Par exemple, un langage de programmation
+  (Turing-complet) quelconque.}, comme des entiers naturels ou comme
+des mots sur un alphabet fixé sans importance) qui, quel que soit le
+paramètre $n$ qu'on leur fournit en entrée, terminent en temps fini et
+retournent la valeur $0$ : soit $L = \{e : (\forall n)
+{\varphi_e(n)\downarrow} = 0\}$.  Si l'on préfère, $L$ est l'ensemble
+de toutes les façons de coder la fonction constante égale à $0$.  On
+appellera aussi $M$ le complémentaire de $L$.  On se demande si $L$ ou
+$M$ sont semi-décidables.
+
+\smallskip
+
+(1) Thésée et Hippolyte se disputent pour savoir si $L$ est
+semi-décidable.  Thésée pense qu'il l'est, et il tient le raisonnement
+suivant pour l'expliquer :
+
+{\narrower
+
+Pour savoir si un programme $e$ est dans l'ensemble $L$, il suffit de
+l'examiner pour vérifier que toutes les instructions qui mettent fin
+au programme renvoient la valeur $0$ : si c'est le cas, on termine en
+répondait « oui » (c'est-à-dire $e\in L$) ; sinon, on rentre dans une
+boucle infinie.  Ceci fournit un algorithme qui semi-décide $L$.
+
+\par}
+
+\smallskip
+
+\noindent Hippolyte, elle, pense que $L$ n'est pas semi-décidable.  Son
+argument est le suivant :
+
+{\narrower
+
+Si $L$ était semi-décidable, je pourrais m'en servir pour résoudre le
+problème de l'arrêt.  En effet, donné un programme $e'$ et une
+entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux
+fabriquer le programme $e$ qui prend une entrée $n$, lance l'exécution
+de $e'$ sur l'entrée $m$ pendant au plus $n$ étapes et à la fin
+renvoie $1$ si ces $n$ étapes ont suffi à terminer l'exécution
+de $e'$, et $0$ sinon.  Dire que $e \in L$ signifie que $e'$ ne
+termine jamais sur $m$, donc pouvoir semi-décider $L$ permet de
+résoudre algorithmiquement le problème de l'arrêt, ce qui est
+impossible.
+
+\par}
+
+\smallskip
+
+\noindent Qui a raison ?  Expliquer précisément quelle est l'erreur
+(ou les erreurs) commise(s) par le raisonnement incorrect, et
+détailler les éventuels passages incomplets dans le raisonnement
+correct.
+
+\begin{corrige}
+C'est Hippolyte qui a raison ($L$ n'est pas semi-décidable).
+
+L'argument de Thésée est stupide : une instruction mettant fin au
+programme avec une valeur autre que $0$ pourrait ne jamais être
+atteinte, et réciproquement, même si toutes les instructions mettant
+fin au programme renvoyaient $0$, il pourrait aussi ne jamais
+terminer.  (Au passage, l'argument de Thésée semblerait même montrer
+que $L$ est décidable, pas juste semi-décidable.)
+
+L'argument d'Hippolyte, lui, est correct : il montre que si $L$ était
+semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
+des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
+pas le cas.  (Le complémentaire du problème de l'arrêt n'est pas
+semi-décidable, car s'il l'était, le problème de l'arrêt serait
+décidable, vu qu'il est déjà semi-décidable.)  Parmi les points qui
+méritent éventuellement d'être précisés, on peut mentionner : le fait
+que $e$ se déduise algorithmiquement de $e'$ et $m$ ; et le fait qu'il
+est algorithmiquement possible de lancer l'exécution d'un programme
+sur $n$ étapes (peu importe la définition exacte de « étape » tant que
+chacune termine à coup sûr en temps fini) et tester si elle est bien
+finie au bout de ce temps.
+\end{corrige}
+
+\medskip
+
+(2) Achille et Patrocle se disputent pour savoir si $M$ (le
+complémentaire de $L$) est semi-décidable.  Achille pense qu'il l'est,
+et il tient le raisonnement suivant pour l'expliquer :
+
+{\narrower
+
+Pour savoir si un programme $e$ est dans l'ensemble $M$, il suffit de
+tester successivement les valeurs $\varphi_e(n)$ pour tous les $n$
+possibles : si l'on rencontre un $n$ tel que $\varphi_e(n)$ n'est
+pas $0$, alors on termine en répondant « oui » (c'est-à-dire $e\in
+M$) ; sinon, on ne va jamais terminer, et cela signifie que $e\not\in
+M$.  Ceci fournit un algorithme qui semi-décide $M$.
+
+\par}
+
+\smallskip
+
+\noindent Patrocle, lui, pense que $M$ n'est pas semi-décidable.  Son
+argument est le suivant :
+
+{\narrower
+
+Si $M$ était semi-décidable, je pourrais m'en servir pour résoudre le
+problème de l'arrêt.  En effet, donné un programme $e'$ et une
+entrée $m$ sur laquelle je cherche à tester l'arrêt de $e'$, je peux
+fabriquer le programme $e$ qui prend une entrée $n$, l'ignore purement
+et simplement, exécute $e'$ sur l'entrée $m$ et à la fin renvoie $0$.
+Dire que $e\in M$ signifie que $e'$ ne termine pas sur $m$, donc
+pouvoir semi-décider $M$ permet de résoudre algorithmiquement le
+problème de l'arrêt, ce qui est impossible.
+
+\par}
+
+\smallskip
+
+\noindent Qui a raison ?  Expliquer précisément quelle est l'erreur
+(ou les erreurs) commise(s) par le raisonnement incorrect, et
+détailler les éventuels passages incomplets dans le raisonnement
+correct.
+
+\begin{corrige}
+C'est Patrocle qui a raison ($M$ n'est pas semi-décidable).
+
+Le raisonnement d'Achille se fonde sur l'idée que le complémentaire de
+« l'ensemble des programmes qui renvoient toujours la valeur $0$ » est
+« l'ensemble des programmes qui renvoient parfois une valeur autre
+que $0$ », ce qui oublie la possibilité que le programme ne termine
+pas.  C'est là la principale erreur (le reste est globalement
+correct).
+
+L'argument de Patrocle, lui, est correct : il montre que si $M$ était
+semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
+des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
+pas le cas.  (Le complémentaire du problème de l'arrêt n'est pas
+semi-décidable, car s'il l'était, le problème de l'arrêt serait
+décidable, vu qu'il est déjà semi-décidable.)  On fait appel à des
+fonctions constantes, et qui ne peuvent renvoyer que $0$ ou ne pas
+terminer, mais ce n'est pas spécialement problématique.  Parmi les
+points qui méritent éventuellement d'être précisés, on peut mentionner
+le fait que $e$ se déduise algorithmiquement de $e'$ et $m$.
+\end{corrige}
+
+
 
 %
 %
author	David A. Madore <david+git@madore.org>	2018-10-03 11:13:07 +0200
committer	David A. Madore <david+git@madore.org>	2018-10-03 11:13:07 +0200
commit	ad186bc02f3b9c6e74364c682fd001b22b705cde (patch)
tree	c4ecdf973f387283ae1fed409389b9a38b16c934 /notes-inf105.tex
parent	f0a89652674ee5c96c697524e00b822b801dd6bf (diff)
download	inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.tar.gz inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.tar.bz2 inf105-ad186bc02f3b9c6e74364c682fd001b22b705cde.zip