13 files changed, 4372 insertions, 220 deletions

diff --git a/controle-20200123.tex b/controle-20200123.tex
index 1ff6354..28b074c 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -473,8 +473,9 @@ acceptant, le langage est fini et égal à $\{a^i : i\in F\}$.
 
 Bref, la condition nécessaire et suffisante de finitude du langage
 reconnu par $\mathscr{A}$ est que $F \cap \{j_1,\ldots,j_2-1\} =
-\varnothing$, et le cas échéant, le langage est constitué des $a^i$
-pour $i\in F$ (et $i<j_1$).
+\varnothing$, ou, ce qui revient au même, $F \subseteq
+\{0,\ldots,j_1-1\}$ ; et le cas échéant, le langage est constitué des
+$a^i$ pour $i\in F$ (et $i<j_1$).
 \end{corrige}
 
 (8) Déduire de l'ensemble de cet exercice que le problème suivant est
diff --git a/controle-20210618.tex b/controle-20210618.tex
new file mode 100644
index 0000000..aa30be9
--- /dev/null
+++ b/controle-20210618.tex
@@ -0,0 +1,672 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{18 juin 2021}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} : 8+7+5.
+
+\ifcorrige
+Ce corrigé comporte 9 pages (page de garde incluse).
+\else
+Cet énoncé comporte 3 pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère
+l'expression rationnelle $r := bb{*}a(a|b){*}$, et soit $L := L(r)$ le
+langage qu'elle dénote (autrement dit, c'est le langage constitué des
+mots qui commencent par un nombre $\geq 1$ de fois la lettre $b$,
+immédiatement suivis par la lettre $a$, puis n'importe quoi).
+
+(0) Pour chacun des mots suivants, dire si oui ou non il appartient
+à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide),
+$a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$.  On ne demande pas
+de justifier les réponses.
+
+\begin{corrige}
+Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas
+à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$.
+\end{corrige}
+
+\emph{Il est fortement conseillé, dans toutes les questions suivantes,
+  d'utiliser les mots qui viennent d'être listés pour vérifier les
+  automates successifs qu'on calculera.}  (Par exemple, pour un
+automate censé reconnaître le langage $L$, on vérifiera qu'il accepte
+bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux
+qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes qui
+auraient dû être détectées par cette vérification pourront être plus
+lourdement sanctionnées.
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$.
+À défaut de donner l'automate de Glushkov ou de Thompson, donner un
+NFA reconnaissant $L$ pourra apporter une partie des points.)
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
+$\mathscr{A}_2$ l'automate en question.  On rappelle qu'on attend ici
+un automate fini \emph{déterministe complet}.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet :
+pour le transformer en automate déterministe complet, on se contente
+pour obtenir l'automate $\mathscr{A}_2$ de lui ajouter un puits vers
+lequel on fait pointer la seule transition manquante :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
+$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
+langage $L$).
+
+\begin{corrige}
+L'automate $\mathscr{A}_2$ est déterministe complet sans état
+inaccessible.  On commence l'algorithme de minimisation en séparant
+les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$.  On
+sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$
+selon que la transition étiquetée $a$ conduit à un état final ou non.
+Enfin, la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en
+deux.  Finalement, on aboutit aux classes suivantes : $\{0\}$,
+$\{1,2\}$, $\{3,4,5\}$ et $\{\bot\}$ (qu'on rebaptise $0,1,3,\bot$
+respectivement), et à l'automate minimal $\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet
+$\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$
+complémentaire de $L$.
+
+\begin{corrige}
+Il suffit d'échanger les états finaux et non-finaux
+dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state] {$3$};
+\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
+\end{tikzpicture}
+\end{center}
+(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur
+ce nouvel automate, en revanche $3$ en est un.  Ces nom sont, bien
+sûr, sans aucun impact sur le fonctionnement de l'automate.)
+\end{corrige}
+
+(5) En appliquant l'algorithme d'élimination des états, déduire
+de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le
+langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne
+vérifient pas $r$).
+\begin{corrige}
+Pour procéder à l'algorithme d'élimination des états, on commence par
+donner à l'automate un unique état final sans aucune transition qui en
+part, appelons-le $\infty$.  On peut aussi d'ores et déjà éliminer
+l'état $3$ qui est maintenant inutile, et remplacer les deux
+transitions $Z\to Z$ étiquetées $a$ et $b$ par une seule
+étiquetée $a|b$ (ce qui, dans un RNFA, revient au même) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$};
+\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a|b$} (qZ);
+\draw[->] (q0) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final);
+\end{tikzpicture}
+\end{center}
+L'élimination de l'état $1$ conduit à remplacer la transition
+$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et
+l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$.
+Finalement, on a affaire à un automate ayant les seuls états $0$
+(initial) et $\infty$ (final) avec la seule transition $0\to\infty$
+étiquetée par l'expression rationnelle $s$ recherchée :
+\[
+\varepsilon \,|\, bb{*} \,|\, a(a|b){*}
+\]
+qui dénote le langage $M$ complémentaire de $L$.  (Autrement dit : un
+mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$
+suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit
+formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de
+n'importe quoi.)
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma =
+\{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles
+\[
+S \rightarrow abc \;|\; aSbc \;|\; abSc
+\]
+On appellera « $0$ » la règle $S \rightarrow abc$, et « $1$ » la règle
+$S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$.
+
+(1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$
+selon cette grammaire $G$.  (On pourra d'abord lire les questions
+suivantes si on a du mal à trouver comment dériver ce mot.)
+
+\begin{corrige}
+L'arbre d'analyse est le suivant :
+% S<a.b.S<a.S<a.b.c.>b.c.>c.>
+\begin{center}
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (68.750bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S1) at (95.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (40.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (a2) at (60.000bp,-90.000bp) [draw=none] {$a$};  \draw (S2) -- (a2);
+\node (b1) at (80.000bp,-90.000bp) [draw=none] {$b$};  \draw (S2) -- (b1);
+\node (c0) at (100.000bp,-90.000bp) [draw=none] {$c$};  \draw (S2) -- (c0);
+\node (b2) at (120.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b2);
+\node (c1) at (140.000bp,-60.000bp) [draw=none] {$c$};  \draw (S1) -- (c1);
+\node (c2) at (160.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c2);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+On va maintenant montrer que $G$ est inambiguë.
+
+(2) Expliquer pourquoi tout mot non-vide du langage $L := L(G)$
+engendré par $G$ a nécessairement $a$ pour préfixe (i.e., commence par
+la lettre $a$).
+
+\begin{corrige}
+Les trois règles $0,1,2$ ont toutes le terminal $a$ comme premier
+symbole de leur membre de droite.  Le fils le plus à gauche de la
+racine (étiquetée $S$) dans n'importe quel arbre d'analyse selon $G$
+est nécessairement étiqueté $a$, et le mot analysé commence donc
+nécessairement par $a$.  (Si on préfère, toute dérivation selon $G$
+commence par une règle produisant $a$ comme symbole le plus à gauche,
+qui ne peut ensuite jamais être effacé ni réécrit puisqu'il s'agit
+d'un terminal.)
+\end{corrige}
+
+(3) Montrer que tout mot de $L$ dérivé en démarrant
+par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
+  selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$
+  où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de
+  dérivations immédiates.  Ou, ce qui revient au même (et on pourra
+  tenir ce point pour acquis) : tout mot $w$ possédant un arbre
+  d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet
+  ordre.} la règle $1$ a nécessairement $aa$ comme préfixe.  Montrer
+de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a
+nécessairement $aba$ comme préfixe.
+
+\begin{corrige}
+Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine
+(étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre
+(i.e., en démarrant par la règle $1$), les descendants du deuxième
+fils (celui étiqueté $S$, y compris lui-même) forment eux-mêmes un
+arbre d'analyse $\mathscr{T}'$ selon $G$, dont le mot analysé $w'$
+commence par $a$ (d'après la question précédente), si bien que le mot
+$w = aw'bc$ analysé par $\mathscr{T}$ commence par $aa$.  (Avec la
+notation qui sera introduite ci-dessous, on a $\mathscr{T} =
+\mathbf{R}_1(\mathscr{T}')$.)
+
+Si on préfère : une dérivation de la forme $S \buildrel
+1\over\Rightarrow aSbc \mathrel{\Rightarrow^*} w$ a nécessairement $w
+= aw'bc$ où $w'$ est le mot obtenu en appliquant les mêmes règles
+à $S$, qui commence donc par $a$, si bien que $w$ commence par $aa$.
+
+Un raisonnement analogue conduit à conclure que tout mot dérivé en
+démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc
+commence par $a$, si bien que le mot commence par $aba$.
+\end{corrige}
+
+(4) En déduire comment, d'après les premières lettres d'un mot $w$
+de $L$, on peut savoir par quelle règle démarre nécessairement une
+dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont
+les fils de la racine dans tout arbre d'analyse de $w$).
+
+\begin{corrige}
+Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots
+ayant (au moins) une dérivation selon $G$ démarrant par les règles
+$0,1,2$ respectivement, on a trivialement $L_0 = \{abc\}$ et on vient
+de voir que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$
+ont $aba$ comme préfixe.  Notamment :
+\begin{itemize}
+\item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle
+  démarre une dérivation de $w$ est déterminée par $w$), et
+\item on peut savoir si un mot $w \in L$ appartient à $L_0$, $L_1$
+  ou $L_2$ en regardant s'il commence par $abc$, $aa$ ou $aba$.
+\end{itemize}
+Ce qui répond à la question posée.
+\end{corrige}
+
+(5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$,
+expliquer comment trouver tous les arbres d'analyse du mot $awbc$
+d'une part, et du mot $abwc$ d'autre part.
+
+\begin{corrige}
+Afin de s'épargner des répétitions fastidieuses, on définit pour toute
+la suite de ce corrigé des notations pour les arbres d'analyse
+selon $G$ démarrant par les règles $0,1,2$ respectivement, à savoir :
+\begin{itemize}
+\item on notera $\mathbf{R}_0$ l'arbre d'analyse associé à la
+  règle $0$, c'est-à-dire l'arbre dont la racine, étiquetée $S$, a
+  exactement trois fils, qui sont des feuilles, et qui sont étiquetés
+  $a,b,c$ dans cet ordre ;
+\item si $\mathscr{T}$ est un arbre d'analyse selon $G$, on notera
+  $\mathbf{R}_1(\mathscr{T})$ l'arbre d'analyse associé à la règle $1$
+  suivie des règles décrites par $\mathscr{T}$, c'est-à-dire l'arbre
+  dont la racine, étiquetée $S$, a exactement quatre fils, étiquetés
+  $a,S,b,c$ dans cet ordre, où le premier et les deux derniers sont
+  des feuilles et où les descendants du second (y compris lui-même)
+  forment une copie de l'arbre d'analyse $\mathscr{T}$ ;
+\item de façon analogue, si $\mathscr{T}$ est un arbre d'analyse
+  selon $G$, on notera $\mathbf{R}_2(\mathscr{T})$ l'arbre d'analyse
+  associé à la règle $2$ suivie des règles décrites par $\mathscr{T}$,
+  c'est-à-dire l'arbre dont la racine, étiquetée $S$, a exactement
+  quatre fils, étiquetés $a,b,S,c$ dans cet ordre, où les deux
+  premiers et le dernier sont des feuilles et où les descendants du
+  troisième (y compris lui-même) forment une copie de l'arbre
+  d'analyse $\mathscr{T}$.
+\end{itemize}
+
+Soit graphiquement :
+\begin{center}
+\begin{tabular}{c|c|c}
+$\mathbf{R}_0$&$\mathbf{R}_1(\mathscr{T})$&$\mathbf{R}_2(\mathscr{T})$\\
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (20.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (c0) at (40.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (20.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$};  \draw (S0) -- (S1);
+\node (b0) at (40.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S1) at (40.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$};  \draw (S0) -- (S1);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+(par exemple, l'arbre d'analyse répondant à la question $1$ est
+l'arbre $\mathbf{R}_2(\mathbf{R}_1(\mathbf{R}_0))$).
+
+Manifestement, tout arbre d'analyse selon $G$ est soit l'arbre
+$\mathbf{R}_0$, soit de la forme $\mathbf{R}_1(\mathscr{T})$ ou
+$\mathbf{R}_2(\mathscr{T})$ avec $\mathscr{T}$ un autre arbre
+(strictement plus petit).
+
+Répondons maintenant à la question posée.
+
+Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, alors
+$\mathbf{R}_1(\mathscr{T})$ est un arbre d'analyse de $awbc$ (toujours
+selon $G$).  Mais réciproquement, comme $awbc$ commence par $aa$
+(i.e., a $aa$ pour préfixe), on a vu en (4) que toute dérivation du
+mot $awbc$ selon $G$ démarre nécessairement par la règle $1$,
+c'est-à-dire que tout arbre d'analyse de $awbc$ est de la
+forme $\mathbf{R}_1(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du deuxième fils de la
+racine).  Bref : $\mathbf{R}_1$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
+
+De même, si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$,
+alors $\mathbf{R}_2(\mathscr{T})$ est un arbre d'analyse de $abwc$.
+Mais réciproquement, comme $abwc$ commence par $aba$ (i.e., a $aba$
+pour préfixe), on a vu en (4) que toute dérivation du mot $abwc$
+selon $G$ démarre nécessairement par la règle $2$, c'est-à-dire que
+tout arbre d'analyse de $abwc$ est de la
+forme $\mathbf{R}_2(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du troisième fils de la
+racine).  Bref : $\mathbf{R}_2$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
+\end{corrige}
+
+(6) En déduire que tout mot $w \in L$ possède un unique arbre
+d'analyse selon $G$, et proposer (sur la base des questions
+précédentes) un algorithme qui le calcule.
+
+\begin{corrige}
+En reformulant les conclusions des questions suivantes, tout mot $w$
+de $L$ est dans un et un seul des trois cas suivants :
+\begin{itemize}
+\item soit $w$ est le mot $abc$ et son unique arbre d'analyse selon $G$
+  est $\mathbf{R}_0$,
+\item soit $w$ commence par $aa$ et alors $w$ est de la forme $aw'bc$
+  et tout arbre d'analyse de $w$ selon $G$ est de la forme
+  $\mathbf{R}_1(\mathscr{T}')$ pour un unique arbre d'analyse
+  $\mathscr{T}'$ de $w'$,
+\item soit $w$ commence par $aba$ et alors $w$ est de la forme $abw'c$
+  et tout arbre d'analyse de $w$ selon $G$ est de la forme
+  $\mathbf{R}_2(\mathscr{T}')$ pour un unique arbre d'analyse
+  $\mathscr{T}'$ de $w'$.
+\end{itemize}
+
+Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un
+unique arbre d'analyse selon $G$ : en effet, dans le premier des trois
+cas ci-dessus, $w$ a pour unique arbre d'analyse $\mathbf{R}_0$, et
+dans les deux derniers cas on a $|w'| < |w|$ (précisément $|w'| =
+|w|-3$), donc $w'$ a un unique arbre d'anayse $\mathscr{T}'$ selon $G$
+par l'hypothèse de récurrence, d'où il résulte que $w$ a lui aussi un
+unique arbre d'analyse (à savoir $\mathbf{R}_1(\mathscr{T}')$ ou
+$\mathbf{R}_2(\mathscr{T}')$).
+
+La grammaire $G$ est donc inambiguë.
+
+Cette démonstration est constructive, c'est-à-dire qu'on a
+l'algorithme suivant qui analyse un mot $w$ et renvoie l'unique arbre
+d'analyse de $w$ selon $G$ (s'il existe, ou signale une erreur
+d'analyse dans le cas contraire) :
+\begin{itemize}
+\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre
+  $\mathbf{R}_0$ ;
+\item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$
+  (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
+  obtenu en effaçant le $a$ initial et le $bc$ final, appliquer
+  récursivement l'algorithme qu'on est en train de définir au
+  mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+  et renvoyer $\mathbf{R}_1(\mathscr{T}')$ ;
+\item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$
+  (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
+  obtenu en effaçant le $ab$ initial et le $c$ final, appliquer
+  récursivement l'algorithme qu'on est en train de définir au
+  mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+  et renvoyer $\mathbf{R}_2(\mathscr{T}')$ ;
+\item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence
+  par autre chose que $aa$ ou $aba$), abandonner avec une erreur
+  d'analyse.
+\end{itemize}
+(L'algorithme termine en temps fini parce que les appels récursifs se
+font sur des mots de longueur strictement plus courte.  Il s'agit d'un
+algorithme par « descente récursive », qui se transforme facilement,
+quitte à remplacer la pile des appels récursifs en une pile en tant
+que structure de données, en un analyseur LL.)
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+(Les deux questions suivantes sont indépendantes.)
+
+\smallskip
+
+(1) Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas
+algébrique\footnote{Ce fait est démontré dans le poly, dans la section
+  consacrée au lemme de pompage pour les langages algébriques et comme
+  illustration de ce dernier ; on ne demande bien sûr pas ici de le
+  redémontrer.}.  Est-il rationnel ?  Est-il décidable ?  Est-il
+semi-décidable ?  On justifiera soigneusement les réponses.
+
+\begin{corrige}
+Le langage proposé n'est pas rationnel car il n'est pas algébrique.
+
+Il est décidable car il est évident qu'on peut algorithmiquement d'une
+part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
+par automate fini) et d'autre part vérifier qu'il a autant de $a$ que
+de $b$ que de $c$.
+
+Étant décidable, il est notamment semi-décidable.
+\end{corrige}
+
+\smallskip
+
+(2) On rappelle la définition du problème de l'arrêt : c'est
+l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un
+  codage permettant de représenter les programmes $e$, les entrées $x$
+  à ces programmes, et les couples $(e,x)$, comme des éléments
+  de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet
+  $\Sigma\neq\varnothing$ arbitraire).  Il n'est pas nécessaire de
+  faire apparaître ce codage dans la description des algorithmes
+  proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme
+(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du
+programme $e$ sur l'entrée $x$ termine en temps fini.  On a vu en
+cours que $H$ était semi-décidable mais non décidable.
+
+On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ et $(e_2,x) \not\in H$.  Autrement dit, le programme
+$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais
+le programme $e_2$, lui, ne termine pas sur cette même entrée.
+L'ensemble $J$ est-il décidable ?  Semi-décidable ?  On justifiera
+soigneusement.
+
+\begin{corrige}
+L'ensemble $J$ n'est pas semi-décidable.
+
+Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme
+$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$
+signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie
+appartient à $Z$, et ne pas terminer sinon).  Fixons une fois pour
+toutes (le code d')un programme $f$ qui, donnée une entrée $x$,
+termine immédiatement (en ignorant $x$).  Alors trivialement $(f,x)
+\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x)
+\in J$ si et seulement si $(e,h) \not \in H$.
+
+On considère alors l'algorithme $T'$, défini de la manière suivante :
+donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister)
+au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in
+J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais).  Par
+construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
+$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
+termine pas.  Ceci signifie que $T'$ semi-décide le complémentaire
+de $H$.
+
+Or le complémentaire de $H$ n'est pas semi-décidable (car si le
+complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et
+son complémentaire semi-décidables, donc $H$ serait décidable, et on
+sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas
+exister.  C'est une contradiction : $J$ n'est donc pas semi-décidable.
+
+\textit{A fortiori}, $J$ n'est pas décidable.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20220616.tex b/controle-20220616.tex
new file mode 100644
index 0000000..7439a45
--- /dev/null
+++ b/controle-20220616.tex
@@ -0,0 +1,674 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{16 juin 2022}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants (le premier teste
+l'application d'algorithmes vus en cours, le second est de nature plus
+théorique).  Ils pourront être traités dans un ordre quelconque, mais
+on demande de faire apparaître de façon très visible dans les copies
+où commence chaque exercice.
+
+\medbreak
+
+Le sujet étant long pour le temps imparti, il ne sera pas nécessaire
+de traiter toutes les questions pour obtenir la totalité des points.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} : autant de points pour chaque exercice.
+
+\ifcorrige
+Ce corrigé comporte 9 pages (page de garde incluse).
+\else
+Cet énoncé comporte 4 pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère
+l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le
+langage qu'elle dénote.
+
+(0) Pour chacun des mots suivants, dire si oui ou non il appartient
+à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide),
+$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$.  On ne demande pas
+de justifier les réponses.
+
+\begin{corrige}
+Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$
+appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas
+à $L$.
+\end{corrige}
+
+\emph{Il est fortement conseillé, dans toutes les questions suivantes,
+  d'utiliser les mots qui viennent d'être listés pour vérifier les
+  automates successifs qu'on calculera.}  (Par exemple, pour un
+automate censé reconnaître le langage $L$, on vérifiera qu'il accepte
+bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux
+qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes qui
+auraient dû être détectées par cette vérification pourront être plus
+lourdement sanctionnées.
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$,
+et il a $4$ états.  À défaut de donner l'automate de Glushkov ou de
+Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie
+des points.)
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2);
+\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3);
+\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3);
+\end{tikzpicture}
+\end{center}
+(on remarquera notamment que tous ses états sont finaux).
+\end{corrige}
+
+(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
+$\mathscr{A}_2$ l'automate en question.  On rappelle qu'on attend ici
+un automate fini \emph{déterministe complet} ; pour information, il a
+$5$ états.
+
+\begin{corrige}
+L'automate $\mathscr{A}_2$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$};
+\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (q0) -- node[auto]{$b$} (q2);
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
+$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
+langage $L$).  Pour information, cet automate a $4$ états : pour la
+commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre
+dans lequel ils sont parcourus lorsque l'automate consomme le
+mot $bab$.
+
+\begin{corrige}
+L'automate $\mathscr{A}_2$ est déterministe complet sans état
+inaccessible.  On commence l'algorithme de minimisation en séparant
+les états finaux $\{0\},\{1,3\},\{2\},\{3\}$ et l'état
+non-final $\varnothing$.  On sépare ensuite les premiers selon que la
+transition étiquetée $b$ conduit à un état non-final, ce qui
+sépare $\{3\}$ du reste, et enfin selon que la transition
+étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du
+reste.  Finalement, on aboutit aux classes suivantes : $\{0\} \equiv
+\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise
+$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L'
+:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$.
+Comme cette expression, et donc cet automate, sont simplement obtenus
+en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
+directement l'automate sans passer par les questions intermédiaires.
+
+\begin{corrige}
+L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en
+échangeant $a$ et $b$ dans $\mathscr{A}_3$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$a$} (q2);
+\draw[->] (q2) -- node[auto]{$b$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$b$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) En utilisant une construction de type « automate produit », donner
+un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 =
+16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des
+mots vérifiant à la fois $r$ et $r'$).  On prendra garde pour la
+question suivante au fait que cet automate possède des états
+inaccessibles.
+
+\begin{corrige}
+En prenant le produit des automates
+$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant
+(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état
+$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple,
+$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et
+$\delta_{\mathscr{A}_4}(1,a) = 2$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$};
+\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$};
+\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$};
+\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$};
+\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$};
+\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$};
+\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$};
+\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$};
+\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$};
+\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$};
+\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$};
+\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$};
+\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$};
+\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$};
+\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$};
+\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$};
+\draw[->] (q11) -- node[auto]{$b$} (q21);
+\draw[->] (q11) -- node[auto]{$a$} (q12);
+\draw[->] (q12) -- node[auto]{$b$} (q23);
+\draw[->] (q12) to[loop above] node[auto]{$a$} (q12);
+\draw[->] (q13) -- node[auto]{$b$} (q23);
+\draw[->] (q13) -- node[auto]{$a$} (q1F);
+\draw[->] (q1F) -- node[auto]{$b$} (q2F);
+\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F);
+\draw[->] (q21) to[loop left] node[auto]{$b$} (q21);
+\draw[->] (q21) -- node[auto]{$a$} (q32);
+\draw[->] (q22) -- node[auto]{$b$} (q23);
+\draw[->] (q22) -- node[auto]{$a$} (q32);
+\draw[->] (q23) to[loop right] node[auto]{$b$} (q23);
+\draw[->] (q23) -- node[auto]{$a$} (q3F);
+\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F);
+\draw[->] (q2F) -- node[auto]{$a$} (q3F);
+\draw[->] (q31) -- node[auto]{$b$} (qF1);
+\draw[->] (q31) -- node[auto]{$a$} (q32);
+\draw[->] (q32) -- node[auto]{$b$} (qF3);
+\draw[->] (q32) to[loop below] node[auto]{$a$} (q32);
+\draw[->] (q33) -- node[auto]{$b$} (qF3);
+\draw[->] (q33) -- node[auto]{$a$} (q3F);
+\draw[->] (q3F) -- node[auto]{$b$} (qFF);
+\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F);
+\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1);
+\draw[->] (qF1) -- node[auto]{$a$} (qF2);
+\draw[->] (qF2) -- node[auto]{$b$} (qF3);
+\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2);
+\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3);
+\draw[->] (qF3) -- node[auto]{$a$} (qFF);
+\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF);
+\end{tikzpicture}
+\end{center}
+Pour plus de lisibilité, on a ici noté les états finaux en les
+entourant deux fois plutôt qu'avec une flèche sortante.
+\end{corrige}
+
+(6) Minimiser l'automate $\mathscr{A}_5$.  On appellera
+$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du
+langage $M = L \cap L'$).  Pour information, cet automate a $6$ états.
+
+\begin{corrige}
+On commence par ne conserver que les états accessibles depuis l'état
+initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$,
+$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la
+représentation ci-dessus, pour avoir un automate déterministe complet
+sans état inaccessible.  On applique ensuite l'algorithme de
+minimisation de manière semblable à la question (3) : les états
+non-finaux vont toujours rester groupés, et les états finaux sont
+séparés un par un.  Finalement, on aboutit à l'automate
+$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a
+rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$,
+$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$,
+$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et
+$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$};
+\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$b$} (q3a);
+\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
+\draw[->] (q3a) -- node[auto]{$a$} (qF);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto,below]{$b$} (qF);
+\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(7) En appliquant l'algorithme d'élimination des états, déduire
+de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le
+langage $M$.  Pour obtenir une expression raisonnablement simple, on
+recommande d'éliminer les états en commençant par ceux qui sont à la
+distance la plus éloignée de l'état initial.
+
+\begin{corrige}
+On commence par effacer l'état puits (qui ne sert à rien) et par créer
+un unique état final sans transition qui en parte :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
+\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
+\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$};
+\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$b$} (q3a);
+\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
+\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT);
+\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below]{$a$} (q3);
+\draw[->] (q3) to[loop below] node[auto]{$a$} (q3);
+\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT);
+\end{tikzpicture}
+\end{center}
+
+On peut alors éliminer les états $3$ et $3'$ (il n'y a pas
+d'interaction entre eux) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
+\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT);
+\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT);
+\end{tikzpicture}
+\end{center}
+
+Et finalement, en éliminant les états $2$ et $2'$, on trouve
+l'expression rationnelle suivante qui dénote le langage $M$ :
+\[
+\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*})
+\]
+(il y a bien sûr d'autres écritures possibles ; par exemple, si on
+élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient :
+$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ;
+l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est
+encore équivalente, mais elle ne s'obtient pas par la procédure
+d'élimination des états).
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+Les parties (A), (B) et (C) de cet exercice sont indépendantes.  On ne
+demande pas de justifications très longues.
+
+\medskip
+
+\textbf{(A)} On se propose de montrer que la question de savoir si
+une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé)
+vérifie $L(G) \neq \varnothing$ est décidable.  Autrement dit, on
+veut montrer qu'il existe un algorithme qui prend en entrée une
+grammaire hors contexte $G$, termine toujours en temps fini, et
+renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) =
+\varnothing$.
+
+(1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il
+existe un arbre d'analyse $\mathscr{T}$ pour $G$.  (Un « arbre
+d'analyse pour $G$ » désigne un arbre d'analyse d'un mot quelconque
+selon $G$.)
+
+\begin{corrige}
+Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout
+arbre d'analyse pour $G$ est l'arbre d'analyse d'un mot de $L(G)$ :
+ainsi, si $L(G) \neq \varnothing$, il existe un arbre d'analyse
+pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse
+pour $G$.
+\end{corrige}
+
+$\bullet$ Pour les questions suivantes, on introduit la terminologie
+suivante : si $\mathscr{T}$ est un arbre et $n$ un nœud (=sommet)
+de $\mathscr{T}$, on dit qu'un nœud $n'$ est un \textbf{descendant} de
+$n$ lorsque $n'$ est soit égal à $n$, soit est un fils de $n$, soit
+est un fils d'un fils de $n$, etc., à n'importe quelle profondeur.
+L'ensemble des descendants de $n$ (y compris $n$ lui-même) est donc un
+arbre ayant $n$ pour racine, qu'on appelle \textbf{sous-arbre qui
+  descend} de $n$.
+
+(2) Montrer que s'il existe un arbre d'analyse $\mathscr{T}$ pour $G$,
+il en existe un vérifiant la propriété additionnelle suivante :
+($\dagger$) « si un nœud $n$ est étiqueté par un nonterminal $X$,
+alors aucun nœud $n' \neq n$ descendant de $n$ ne porte la même
+étiquette $X$ ».
+
+\textit{Indication.}\quad Pour cela, on pourra remarquer que si un
+arbre $\mathscr{T}$ ne vérifie pas ($\dagger$), on peut en construire
+un autre ayant strictement moins de nœuds, en remplaçant le sous-arbre
+qui descend de $n$ par celui qui descend de $n'$, et expliquer
+pourquoi c'est encore un arbre d'analyse pour $G$ si $\mathscr{T}$ en
+est un (pas nécessairement du même mot).
+
+\begin{corrige}
+Si $\mathscr{T}$ est un arbre d'analyse pour $G$ dans lequel un nœud
+$n'$ descendant d'un autre nœud $n$ est étiqueté par le même
+symbole $X$, alors on peut fabriquer un arbre $\mathscr{T}'$ en
+remplaçant le sous-arbre qui descend de $n$ par celui qui descend
+de $n'$.  Cet arbre $\mathscr{T}'$ a strictement moins de nœuds
+que $\mathscr{T}$ car ses nœuds sont exactement ceux de $\mathscr{T}$
+à l'exception de ceux qui descendent de $n$ mais pas de $n'$.  Par
+ailleurs, c'est toujours un arbre d'analyse pour $G$ car chaque nœud a
+des fils étiquetés exactement de la même manière (le seul pour lequel
+ce n'est pas évident est le nœud parent de $n$, mais c'est bien vrai
+car $n'$ et $n$ ont la même étiquette $X$).
+
+Si on considère maintenant $\mathscr{T}$ l'arbre d'analyse pour $G$
+ayant le nombre minimal de nœuds, il vérifie forcément ($\dagger$),
+sans quoi la construction qu'on vient de donner produirait un arbre
+$\mathscr{T}'$ ayant strictement moins de nœuds, contredisant la
+minimalité.  Il existe donc bien un arbre d'analyse pour $G$
+vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse
+pour $G$ tout court).
+\end{corrige}
+
+$\bullet$ Pour la question suivante, on dira qu'un arbre $\mathscr{T}$
+est de \textbf{valence} $\leq k$ lorsque chaque nœud de $\mathscr{T}$
+a au plus $k$ fils.
+
+(3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il
+n'y a qu'un nombre fini d'arbres de valence $\leq k$, dont les sommets
+sont étiquetés par des étiquettes prises dans un ensemble
+$\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la propriété
+($\dagger$) de la question précédente.  Plus précisément, on pourra
+montrer que le nombre de tels arbres est donné par $N(k,m)$ défini par
+la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et $N(k,0) =
+0$) en considérant l'étiquette de la racine (parmi $m$ possibles) et
+les $r \leq k$ sous-arbres qui descendent de ses fils.
+
+\begin{corrige}
+Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et
+dont les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\}$ s'obtient
+en choisissant l'étiquette $Z_i$ de la racine parmi $m$ possibles, le
+nombre $0\leq r\leq k$ de fils de la racine, et les sous-arbres
+$\mathscr{T}_1,\ldots,\mathscr{T}_r$ qui en descendent, qui sont
+eux-mêmes des arbres de valence $\leq k$ vérifiant ($\dagger$) et dont
+les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\} \setminus
+\{Z_i\}$, c'est-à-dire parmi $m-1$ possibles.  Par récurrence sur $m$,
+on montre donc que ce nombre est fini, et précisément qu'il vérifie
+$N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
+\end{corrige}
+
+(4) En déduire un algorithme répondant à la question posée.
+
+\textit{Indication.}\quad Si $k$ est la longueur maximale d'une
+production de la grammaire $G$, on pourra chercher à construire tous
+les arbres de valence $\leq k$, étiquetés par des terminaux ou
+nonterminaux ou $\varepsilon$, vérifiant de plus la
+propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi
+eux.
+
+\begin{corrige}
+Si $k$ est la longueur maximale d'une production de la grammaire $G$
+et $m$ le nombre d'étiquettes possibles d'un arbre d'analyse selon $G$
+(c'est-à-dire le nombre de nonterminaux plus le nombre de terminaux
+plus $1$ pour $\varepsilon$, mais peu importe), on commence par
+énumérer tous les arbres de valence $\leq k$, étiquetés par les tokens
+en question, ce qui est possible d'après la question précédente (et
+effectif avec la récursion évidente sur $m$).  Il suffit ensuite de
+tester tous ces arbres concevables et de vérifie si, à chaque nœud,
+les contraintes imposées à un arbre d'analyse sont vérifiées.  Soit on
+trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq
+\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre
+d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse
+pour $G$ d'après la question (2), donc $L(G) = \varnothing$
+d'après (1) et on peut répondre « faux ».
+\end{corrige}
+
+\medbreak
+
+\textbf{(B)} Montrer que la question de savoir si (pour un alphabet
+$\Sigma$ fixé) une grammaire hors contexte $G$ vérifie $L(G) \neq
+\Sigma^*$, est semi-décidable.  Autrement dit, montrer qu'il existe un
+algorithme qui prend en entrée une grammaire hors contexte $G$,
+termine en temps fini et renvoie « vrai » si $L(G) \neq \Sigma^*$, et
+ne termine pas si $L(G) = \Sigma^*$.
+
+\textit{Indication.}\quad On pourra pour cela énumérer tous les mots
+possibles à la recherche d'un mot qui \emph{n'appartient pas}
+à $L(G)$, et utiliser le fait que tester si $w \in L(G)$ est
+décidable.
+
+\begin{corrige}
+L'algorithme suivant convient : énumérer tous les mots $w \in
+\Sigma^*$ et, pour chacun, utiliser la procédure de décision connue
+pour déterminer en temps fini si $w \in L(G)$.  Si ce n'est pas le
+cas, on termine immédiatement en renvoyant « vrai » (on a $L(G) \neq
+\Sigma^*$) ; si c'est le cas, on continue (on passe au mot suivant).
+Cet algorithme termine (et renvoie « vrai » dans ce cas) exactement
+lorsque $L(G) \neq \Sigma^*$ : il montre donc la semi-décidabilité du
+problème considéré.
+\end{corrige}
+
+\medbreak
+
+\textbf{(C)} (1) Montrer qu'il existe un algorithme qui, donnés une
+expression rationnelle $r_1$ et une grammaire hors contexte $G_1$ (sur
+un même alphabet $\Sigma$), calcule (= renvoie) une grammaire hors
+contexte $G_2$ telle que $L(G_2) = L(G_1) \cup (\Sigma^* \setminus
+L(r_1))$.
+
+\begin{corrige}
+D'après divers résultats du cours : donnée une expression rationnelle
+$r_1$, on sait calculer algorithmiquement un NFA $A_1$ tel que $L(r_1)
+= L(A_1)$ (par exemple avec la construction de Glushkov), on sait
+calculer algorithmiquement un DFA $A_2$ tel que $L(A_1) = L(A_2)$ (en
+déterminisant $A_1$), on sait calculer algorithmiquement un DFA $A_2$
+tel que $L(A_3) = \Sigma^* \setminus L(A_2)$ (en échangeant états
+finaux et non-finaux), on sait calculer algorithmiquement une
+grammaire hors contexte $G_3$ telle que $L(G_3) = L(A_3)$ (en
+construisant une grammaire régulière), et à partir de $G_1$ et $G_3$
+on sait calculer algorithmiquement une grammaire hors contexte $G_2$
+telle que $L(G_2) = L(G_1) \cup L(G_3)$ (stabilité algorithmique des
+langages algébriques par union) : on a alors $L(G_2) = L(G_1) \cup
+(\Sigma^* \setminus L(r_1))$ comme annoncé.
+\end{corrige}
+
+(2) On \underline{admet} que le problème suivant n'est pas décidable
+(pour un alphabet $\Sigma$ fixé de cardinal $\#\Sigma \geq 2$) :
+donnés $G$ une grammaire hors contexte et $r$ une expression
+rationnelle, savoir si $L(r) \subseteq L(G)$.  En déduire que le
+problème suivant (qui en est un cas particulier) n'est lui-même pas
+décidable : donnée $G$ une grammaire hors contexte, savoir si $L(G) =
+\Sigma^*$.
+
+\textit{Indication.}\quad Pour cela, on pourra supposer par l'absurde
+que le problème de reconnaître si $L(G) = \Sigma^*$ est décidable et,
+donnés $G_1$ et $r_1$, construire algorithmiquement une grammaire hors
+contexte $G_2$ telle que $L(G_2) = \Sigma^*$ si et seulement si
+$L(r_1) \subseteq L(G_1)$.
+
+\begin{corrige}
+Supposons par l'absurde qu'on dispose d'un algorithme $\mathfrak{A}$
+qui prend une grammaire hors contexte $G$ en entrée et décide si $L(G)
+= \Sigma^*$.  Considérons l'algorithme suivant qui prend en entrée une
+grammaire hors contexte $G_1$ et une expression rationnelle $r_1$ : on
+commence par calculer une grammaire $G_2$ telle que $L(G_2) = L(G_1)
+\cup (\Sigma^* \setminus L(r_1))$ comme expliqué en question (1), et
+on applique à $G_2$ l'algorithme $\mathfrak{A}$ qu'on a supposé
+exister pour décider si $L(G_2) = \Sigma^*$.  Comme $L(G_2) = L(G_1)
+\cup (\Sigma^* \setminus L(r_1))$, dont le complémentaire est $L(r_1)
+\setminus L(G_1)$, on a $L(G_2) = \Sigma^*$ si et seulement si $L(r_1)
+\subseteq L(G_1)$ : on peut donc renvoyer « vrai » dans ce cas et
+« faux » sinon.  Ceci montre l'existence d'un algorithme décidant si
+$L(r_1) \subseteq L(G_1)$, ce qui est impossible (résultat admis).
+C'est donc que l'hypothèse de l'existence de $\mathfrak{A}$ était
+absurde, et le problème en question n'est pas décidable.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20220825.tex b/controle-20220825.tex
new file mode 100644
index 0000000..c3cf461
--- /dev/null
+++ b/controle-20220825.tex
@@ -0,0 +1,683 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de rattrapage — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{25 août 2022}
+\maketitle
+
+% NOTE: Initially copied from controle-20180206.tex
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+Documents autorisés : uniquement une feuille A4 recto-verso
+(manuscrite ou typographiée).
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} : 7 points par exercice
+
+\ifcorrige
+Ce corrigé comporte 9 pages (page de garde incluse)
+\else
+Cet énoncé comporte 4 pages (page de garde incluse)
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On s'intéresse au
+langage $L$ formé des mots (éléments de $\Sigma^*$) ayant $aa$ ou $bb$
+comme facteur (c'est-à-dire contenant deux $a$ consécutifs, ou bien
+deux $b$ consécutifs), ainsi qu'à son
+complémentaire $M := \Sigma^* \setminus L$.
+
+(1) Donner une expression rationnelle dénotant $L$.
+
+\begin{corrige}
+Le langage des mots contenant deux $a$ consécutifs est dénoté par
+l'expression rationnelle $(a|b){*}\,aa\,(a|b){*}$, et celui des mots
+contenant deux $b$ consécutifs par $(a|b){*}\,bb\,(a|b){*}$.  On peut
+donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \;
+(a|b){*}\,bb\,(a|b){*}$ ou encore, si on préfère,
+$(a|b){*}\,(aa|bb)\,(a|b){*}$.
+\end{corrige}
+
+(2) \emph{Indépendamment} de la question (1), expliquer brièvement pourquoi
+l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (A) at (70bp,35bp) [draw,circle,state] {$A$};
+\node (B) at (70bp,-35bp) [draw,circle,state] {$B$};
+\node (T) at (140bp,0bp) [draw,circle,state,final] {$T$};
+\draw [->] (S) to[loop above] node[auto] {$a,b$} (S);
+\draw [->] (S) -- node[auto,near end] {$a$} (A);
+\draw [->] (S) -- node[auto] {$b$} (B);
+\draw [->] (T) to[loop above] node[auto] {$a,b$} (T);
+\draw [->] (A) -- node[auto,near start] {$a$} (T);
+\draw [->] (B) -- node[auto] {$b$} (T);
+\end{tikzpicture}
+\end{center}
+
+De quelle sorte d'automate s'agit-il ?  (DFA ?  NFA ?...)
+
+\begin{corrige}
+Un chemin de l'unique état initial $S$ à l'unique état final $T$ de
+$\mathscr{A}_2$ doit passer soit par l'état $A$ soit par l'état $B$,
+donc la lecture de ses étiquettes contient le facteur $aa$
+(correspondant aux transitions $S\to A$ et $A\to T$) ou $bb$ ; et
+réciproquement, un mot contenant le facteur $aa$ ou $bb$ peut se lire
+en suivant un chemin de $S$ à $T$ dans l'automate (en plaçant le
+facteur $aa$ au niveau des transitions $S\to A$ et $A\to T$ ou de
+façon analogue pour $bb$).
+
+Il s'agit là d'un automate non déterministe (l'état $S$ a plusieurs
+transitions sortantes étiquetées par $a$), mais sans transitions
+spontanées ou en abrégé, NFA.
+\end{corrige}
+
+(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté
+en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant.
+
+\begin{corrige}
+En notant $S$, $SA$, $SB$, $SAT$ et $SBT$ les états de l'automate
+déterministe $\mathscr{A}_3$ qui correspondent aux ensembles d'états
+de l'automate $\mathscr{A}_2$ donnés par les lettres en question, la
+déterminisation conduit à l'automate $\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (SAT) at (140bp,35bp) [draw,circle,state,final] {$SAT$};
+\node (SBT) at (140bp,-35bp) [draw,circle,state,final] {$SBT$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (SAT);
+\draw [->] (SB) -- node[auto,below] {$b$} (SBT);
+\draw [->] (SAT) to[out=300,in=60] node[auto] {$b$} (SBT);
+\draw [->] (SBT) to[out=120,in=240] node[auto] {$a$} (SAT);
+\draw [->] (SAT) to[loop above] node[auto] {$a$} (SAT);
+\draw [->] (SBT) to[loop below] node[auto] {$b$} (SBT);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu
+en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique)
+résultant.
+
+\begin{corrige}
+On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans
+état inaccessible.  La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et
+$SAT,SBT$ de l'autre.  Ensuite on sépare $S$ et $SA$ et $SB$ (car le
+premier ne conduit qu'à des états non finaux, le deuxième conduit à un
+état final par la transition étiquetée $a$, et le troisième conduit à
+un état final par la transition étiquetée $b$).  Les étapes suivantes
+ne conduisent pas à d'autres séparations d'états.  On obtient
+finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut
+appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state,final] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) Construire un automate $\mathscr{A}_5$ reconnaissant le
+langage $M$ complémentaire de $L$.
+
+\begin{corrige}
+On obtient $\mathscr{A}_5$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_4$, c'est-à-dire l'automate $\mathscr{A}_5$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state,final] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state,final] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below,near end] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+(L'état $U$ est maintenant un puits.)
+\end{corrige}
+
+(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des
+états, déterminer une expression rationnelle dénotant le langage $M$.
+
+\begin{corrige}
+On va manipuler des automates finis à transitions étiquetées par des
+expressions rationnelles (ou « RNFA »).  Dans un premier temps, on
+donne à l'automate un unique état final $F$ en faisant pointer vers
+lui une transition spontanée (i.e., étiquetée
+par $\underline{\varepsilon}$) depuis tout état qui était final.
+L'état $U$ peut être éliminé d'emblée puisqu'il est inutile (il n'est
+pas co-accessible : c'est un puits !).  On a donc affaire à l'automate
+suivant
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}$} (F);
+\draw [->] (SB) -- node[auto,below,near end] {$\underline{\varepsilon}$} (F);
+\draw [->] (S) to[out=270,in=90] (0,-30bp) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}$} (140bp,-30bp) to[in=270,out=90] (F);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $SB$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a|ba$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (S) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (SA) to[loop below] node[auto] {$ba$} (SA);
+\end{tikzpicture}
+\end{center}
+Et l'élimination de l'état $SA$ conduit à l'expression rationnelle
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(a|ba)(ba){*}(\underline{\varepsilon}|b)$
+(il y a bien sûr toutes sortes d'autres expressions rationnelles
+équivalentes : par exemple, on peut la réécrire comme
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(\varepsilon|b)a(ba){*}(\underline{\varepsilon}|b)$
+ou encore comme
+$(\varepsilon|b)(\underline{\varepsilon}|a(ba){*}(\underline{\varepsilon}|b))$ ;
+si on avait éliminé l'état $SA$ en premier, on serait plutôt tombé sur
+$\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon}|a)$,
+et ainsi de suite).
+\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$ » (i.e., les
+  deux ont le même effet ou la même valeur), 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 de renommer
+en $a$ la lettre « parenthèse ouvrante » de $\Sigma$ et en $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 pourra si on le souhaite remplacer $\mathbb{N}$ partout dans cet
+exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$
+[fini] non vide fixé quelconque : grâce au codage de Gödel, ceci ne
+change rien au problème ni aux raisonnements.)
+
+Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$
+(cf. le paragraphe précédent).
+
+On dira que deux langages $L,M$ disjoints (c'est-à-dire tels que
+$L\cap M = \varnothing$) sont \emph{calculablement séparables}
+lorsqu'il existe un langage $E$ \underline{décidable} tel que $L
+\subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où
+$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le
+cas contraire, on dit que $L$ et $M$ sont \emph{calculablement
+  inséparables}.
+
+(1) Expliquer pourquoi deux langages $L,M$ disjoints sont
+calculablement séparables si et seulement s'il existe un algorithme
+qui, prenant en entrée un élément $x$ de $\mathbb{N}$ :
+\begin{itemize}
+\item termine toujours en temps fini,
+\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est
+  imposé si $x\not\in L\cup M$ à part de terminer en temps fini).
+\end{itemize}
+
+\begin{corrige}
+Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$, alors un algorithme qui décide $E$
+(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si
+$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères
+demandés.  Réciproquement, donné un algorithme qui répond aux critères
+demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond
+« vrai », alors $E$ est bien décidable (on peut toujours modifier
+l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou
+« faux »), et on a $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$.
+\end{corrige}
+
+(2) Expliquer pourquoi deux langages \emph{décidables} disjoints sont
+toujours calculablement séparables.
+
+\begin{corrige}
+Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est
+décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M
+\subseteq (\mathbb{N}\setminus E)$ (c'est une reformulation du fait
+que $M$ est disjoint de $E=L$).
+\end{corrige}
+
+On cherche maintenant à montrer qu'il existe deux langages $L,M$
+\emph{semi-décidables} disjoints et calculablement inséparables.
+
+Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être
+  rigoureux, on a fixé un codage de Gödel permettant de représenter
+  les programmes $e$, les entrées $x$ à ces programmes, et les couples
+  $(e,x)$, comme des éléments de $\mathbb{N}$.  Il n'est pas
+  nécessaire de faire apparaître ce codage dans la description des
+  algorithmes proposés, qui peut rester informelle.} $(e,x)$ formés
+d'un programme (=algorithme) $e$ et d'une entrée $x$, tels que
+l'exécution du programme $e$ sur l'entrée $x$ termine en temps fini et
+renvoie la valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et
+$M$ le langage défini de la même manière mais avec la valeur $2$,
+i.e., $\varphi_e(x) = 2$.  (Ici, $1$ et $2$ peuvent être remplacés par
+deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité
+remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots
+distincts quelconques, par exemple $a$ et $aa$.)
+
+(3) Pourquoi $L$ et $M$ sont-ils disjoints ?
+
+\begin{corrige}
+Comme $L$ est l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) =
+1$ et $M$ l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = 2$,
+aucun couple ne peut appartenir aux deux, c'est-à-dire qu'ils sont
+disjoints.
+\end{corrige}
+
+(4) Pourquoi $L$ et $M$ sont-ils semi-décidables ?
+
+\begin{corrige}
+Pour semi-décider si un couple $(e,x)$ appartient à $L$, il suffit de
+lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle
+termine en retournant $1$, renvoyer « vrai », tandis que si elle
+termine en renvoyant n'importe quelle autre valeur, faire une boucle
+infinie (bien sûr, si le programme $e$ ne termine jamais sur
+l'entrée $x$, on ne termine pas non plus).  Ceci montre que $L$ est
+semi-décidable.  Le même raisonnement s'applique pour $M$.
+\end{corrige}
+
+(5) En imitant la démonstration du théorème de Turing sur
+l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun
+algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours
+en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x)
+\in M$ (indication : si un tel algorithme existait, on pourrait s'en
+servir pour faire le contraire de ce qu'il prédit).
+
+\begin{corrige}
+Montrons par l'absurde qu'il n'existe aucun algorithme $T$ comme
+annoncé.  Définissons un nouvel algorithme $T'$ qui, donné un
+entier $e$, effectue les calculs suivants : (1º) interroger
+l'algorithme $T$ (supposé exister !) en lui fournissant le couple
+$(e,e)$ comme entrée, et ensuite (2º) s'il répond vrai, renvoyer la
+valeur $2$, tandis que s'il répond n'importe quoi d'autre, renvoyer la
+valeur $1$.  L'algorithme $T'$ qui vient d'être décrit aurait un
+certain numéro, disons, $p$, et la description de l'algorithme fait
+qu'il termine toujours, que la valeur $\varphi_p(e)$ qu'il renvoie
+vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $(e,e) \in L$
+(c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $(e,e) \in M$
+(c'est-à-dire si $\varphi_e(e) = 2$).  En particulier, en prenant
+$e=p$, on voit que $\varphi_p(p)$ doit valoir $1$ ou $2$, doit valoir
+$2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une
+contradiction.
+\end{corrige}
+
+(6) Conclure.
+
+\begin{corrige}
+La question (5) montre (compte tenu de la question (1)) que $L$ et $M$
+ne sont pas calculablement séparables, i.e.., sont calculablement
+inséparables, tandis que (4) et (5) montrent que $L$ et $M$ sont
+disjoints et semi-décidables.  On a donc bien montré l'existence de
+langages semi-décidables disjoints et calculablement inséparables.
+\end{corrige}
+
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20230615.tex b/controle-20230615.tex
new file mode 100644
index 0000000..d9bc00d
--- /dev/null
+++ b/controle-20230615.tex
@@ -0,0 +1,870 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{15 juin 2023}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} et \emph{approximatif} : exercice 1 :
+(a) $1.5$, (b) $1.5$, (c) $1$, (d) $4$, (e) $3$, (f) $3$ (soit au
+total $14$) ; exercice 2 : (a) $1$, (b) $2$, (c) $1$, (d) $2$ (soit au
+total $6$).
+
+\ifcorrige
+Ce corrigé comporte 8 pages (page de garde incluse).
+\else
+Cet énoncé comporte 4 pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère les huit
+automates suivants
+($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$)
+sur l'alphabet $\Sigma$ :
+
+\begin{center}
+\begin{tabular}{|c|c|}
+\hline
+$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
+\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1);
+\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}&
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\end{tikzpicture}
+}\\
+\hline
+\end{tabular}
+\end{center}
+
+On définit aussi les douze langages suivants, où $w_0$ désigne le
+mot $ababb$ :
+\begin{itemize}
+\item $L_0 = \varnothing$ : le langage vide.
+\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$.
+\item $L_2$ : le langage constitué des mots qui sont un sous-mot de
+  $w_0$.
+\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme
+  sous-mot.
+\item $L_4$ : le langage constitué des mots qui sont un facteur de
+  $w_0$.
+\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme
+  facteur.
+\item $L_6$ : le langage constitué des mots qui sont un préfixe de
+  $w_0$.
+\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme
+  préfixe.
+\item $L_8$ : le langage constitué des mots qui sont un suffixe de
+  $w_0$.
+\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme
+  suffixe.
+\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des
+  mots qui sont une répétition d'un nombre quelconque ($i$) de copies
+  de $w_0$ (par exemple, $ababbababb$).
+\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage
+  constitué des mots obtenus en précédant $w_0$ d'un nombre
+  quelconque ($i$) de copies de la lettre $b$ et en le suivant du même
+  nombre de copies de la lettre $a$ (par exemple, $bbababbaa$).
+\end{itemize}
+
+\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou
+lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui
+reconnu par l'automate $A$.  On ne demande pas de justifier la
+réponse.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$.
+
+L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant
+$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un
+chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant
+$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence
+par un chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant
+$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un
+chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant
+$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les
+lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre
+quelconque de lettres quelconques).
+
+L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes
+de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début
+de $w_0$).
+
+L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes
+de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin
+de $w_0$).
+
+L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs
+de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle
+de lettres consécutives de $w_0$).
+
+(Les justifications entre parenthèses n'étaient pas demandées.)
+\end{corrige}
+
+\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée
+pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le
+langage $L$ reconnu par $A$.  On ne demande pas de justifier la
+réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en
+cours.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$.
+
+L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté
+par $(a|b){*}ababb$.
+
+L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté
+par $ababb(a|b){*}$.
+
+L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté
+par $(a|b){*}ababb(a|b){*}$.
+
+L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté
+par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$.
+
+L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté
+par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération
+de tous les préfixes de $w_0$) ou, si on préfère, par
+$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$
+(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans
+l'ordre $5,4,3,2,1,0$).
+
+L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté
+par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération
+de tous les suffixes de $w_0$) ou, si on préfère, par
+$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$
+(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans
+l'ordre $0,1,2,3,4,5$).
+\end{corrige}
+
+\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type
+d'automate vu en cours (DFA complet, DFA à spécification incomplète,
+NFA ou bien NFA à transitions spontanées) est l'automate $A$.  On
+donnera à chaque fois le type le plus particulier applicable.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double
+transition étiquetée $a$ depuis l'état $0$).
+
+L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{v}}$ est un NFA.
+
+L'automate $A_{\mathrm{w}}$ est un NFA.
+
+L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états
+initiaux).
+
+L'automate $A_{\mathrm{z}}$ est un NFA.
+\end{corrige}
+
+\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$
+(cette question-ci n'est pas posée pour $A_{\mathrm{t}},
+A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état
+inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le
+langage $L$).  On appliquera un algorithme vu en cours en le nommant.
+
+{\footnotesize Conseil sur la présentation graphique : pour s'éviter
+  des maux de tête dans le placement des états (et en éviter aussi au
+  correcteur), il est conseillé de commencer par placer
+  horizontalement de gauche à droite les états successifs rencontrés
+  lors de la consommation du mot $w_0 = ababb$ par l'automate
+  construit, et d'ajouter ensuite les autres états éventuellement
+  nécessaires.\par}
+
+\begin{corrige}
+S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit
+simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous,
+où aboutissent toutes les transitions manquantes :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax
+La construction est analogue pour $A_{\mathrm{u}}$ :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à
+un « vrai » non-déterminisme et on applique donc l'algorithme de
+déterminisation vu en cours, qui donne (en omettant les accolades dans
+le nommage des états) :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$};
+\node (q5) at (300bp,-45bp) [draw,circle,state,final] {\small $0,5$};
+\node (q1X) at (30bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,5$};
+\node (q2X) at (110bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,5$};
+\node (q3X) at (190bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,3,5$};
+\node (q4X) at (270bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,4,5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[loop below] node[auto]{$b$} (q0);
+\draw[->] (q1) to[loop below] node[auto]{$a$} (q1);
+\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0);
+\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1);
+\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3);
+\draw[->] (q5) to[loop above] node[auto]{$b$} (q5);
+\draw[->] (q5) to[out=165,in=45] node[auto,swap,near end]{$a$} (q1X);
+\draw[->] (q1X) -- node[auto]{$b$} (q2X);
+\draw[->] (q2X) -- node[auto]{$a$} (q3X);
+\draw[->] (q3X) -- node[auto]{$b$} (q4X);
+\draw[->] (q4X) -- node[auto,swap]{$b$} (q5);
+\draw[->] (q1X) to[loop left] node[auto]{$a$} (q1X);
+\draw[->] (q2X) to[out=45,in=195] node[auto]{$b$} (q5);
+\draw[->] (q3X) to[out=240,in=300] node[auto]{$a$} (q1X);
+\draw[->] (q4X) to[out=240,in=300] node[auto]{$a$} (q3X);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax {\footnotesize\textbf{Note:} Une version
+  précédente de ce corrigé donnait un automate certes correct (DFA
+  complet sans état inaccessible qui soit équivalent à $A$) mais qui
+  n'est pas celui, représenté ci-dessus, obtenu en appliquant
+  l'algorithme de déterminisation.  (L'automate qui était représenté
+  était, en fait, l'automate minimal obtenu en identifiant tous les
+  états contenant $5$ dans celui ci-dessus.)\par}
+La construction pour $A_{\mathrm{x}}$ est exactement comme pour
+$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués
+finaux :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax
+S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai »
+non-déterminisme et on applique donc l'algorithme de déterminisation
+vu en cours, qui donne (en omettant les accolades dans le nommage des
+états) :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
+\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$};
+\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (qI) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245);
+\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
+\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
+\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3);
+\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$.
+\end{corrige}
+
+\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci),
+minimiser le DFA trouvé à la question (d).
+
+\begin{corrige}
+On a affaire à un DFA complet sans état inaccessible : on va le
+minimiser avec l'algorithme de Moore.
+
+Dans une première étape, on fait deux classes d'état : celle des états
+finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$
+et celle des états non-finaux, c'est-à-dire le seul
+état $\varnothing$.
+
+Séparons maintenant les états selon la cible de la transition
+étiquetée par $a$ : la classe formée de
+$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux :
+$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et
+$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état
+non-final.  La cible de la transition étiquetée par $b$, pour sa part,
+sépare $\{5\}$ de tous les autres états (le seul où elle mène à un
+état non-final).  À ce stade, on a quatre classes : la classe formée
+de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux
+classes singleton, $\{5\}$ et $\varnothing$.
+
+À l'étape suivante, la cible de la transition étiquetée par $a$ ne
+sépare rien (les états de la première classe mènent à la seconde et
+les états de la seconde mènent au puits).  La cible de la transition
+étiquetée par $b$, en revanche, sépare la classe formée de
+$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe)
+et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle
+sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les
+cibles sont dans trois classes distinctes).  À ce stade, les seuls
+états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$.  Or
+comme ils ont exactement les mêmes cibles de transitions étiquetées
+par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique
+ici : il fusionne exactement deux états, à savoir
+$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
+\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (qI) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2);
+\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
+\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
+\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels
+sont rationnels ?  Lesquels sont algébriques ?  Lesquels sont
+décidables ?  Lesquels sont semi-décidables ?  On justifiera la
+réponse à chaque fois (par exemple en donnant une expression
+rationnelle, un automate, une grammaire hors-contexte, un algorithme,
+ou n'importe quel autre type d'argument permettant de conclure).
+
+\begin{corrige}
+Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils
+sont reconnaissables : on a vu que les automates $A_{\mathrm{s}},
+A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}},
+A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les
+reconnaissent.  Il reste donc à traiter le cas de
+$L_0,L_2,L_{10},L_{11}$.
+
+Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on
+peut donner des expressions rationnelles pour les deux, à savoir
+$\bot$ pour $L_0$ et, en énumérant systématiquement tous les
+sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab |
+babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais
+ce n'est pas très intéressant et ce n'était pas demandé).
+
+Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel
+car il est l'étoile de Kleene d'un langage rationnel (si on préfère,
+il est dénoté par l'expression rationnelle $(ababb){*}$).
+
+Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en
+particulier, algébriques, décidables et semi-décidables.
+
+Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i :
+i\in\mathbb{N}\}$.  Montrons qu'il n'est pas rationnel, et montrons
+qu'il est algébrique.
+
+Il n'est pas rationnel par le lemme de pompage.  En effet, supposons
+par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel,
+et soit $k$ tel que donné par le lemme de pompage.  Considérons le mot
+$t := b^k ababb a^k \in L_{11}$.  D'après la propriété de $k$, il
+existe une factorisation $t = uvw$ vérifiant les propriétés garanties
+par le lemme de pompage.  Le fait que $|uv|\leq k$, comme le préfixe
+de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure
+que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$
+avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et
+$\ell_1+\ell_2\leq k$.  On a alors $w = b^{k-\ell_1-\ell_2} ababb
+a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$.  Comme les mots de
+$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$
+(i.e., la longueur de leur plus long préfixe formé uniquement de la
+lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de
+leur plus long suffixe formé uniquement de la lettre $a$), on devrait
+avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq
+1$.
+
+En revanche, le langage $L_{11}$ est algébrique, car il est engendré
+par la grammaire suivante d'axiome $S$ :
+\[
+S \rightarrow ababb \;|\; bSa
+\]
+Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable.
+(Au demeurant, il est facile de donner un algorithme qui décide si un
+mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$
+est égal à son nombre final de $a$ et, une fois ce fait vérifié, on
+vérifie qu'une fois retiré le préfixe et le suffixe en question il
+reste exactement le mot $ababb$.)
+
+Pour résumer, tous les langages dont on a parlé sont algébriques,
+décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+{\footnotesize Dans cet exercice, les questions (1) et (2) sont
+  indépendantes, et la question (4) ne dépend que de la
+  question (2).\par}
+
+\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante
+est-elle calculable ?
+\[
+h(0) = 1\;\;,\;\;
+h(1) = 10\;\;,\;\;
+h(2) = 10^{10}\;\;,\;\;
+h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\;
+h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\;
+\]
+\[
+\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n
+\]
+(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur
+le nombre $10$.  Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend
+comme $10^{\big(10^{\scriptstyle 10}\big)}$.)
+
+\begin{corrige}
+La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut
+exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur
+d'une variable en partant de $1$.  On en déduit que la fonction $h$
+est calculable : en effet, on peut exécuter une boucle à $n$
+itérations en appliquant la fonction $g$ à une variable en partant
+de $1$.
+\end{corrige}
+
+\medskip
+
+Fixons maintenant une numérotation (« codage de Gödel ») des
+algorithmes prenant en entrée un entier et renvoyant un entier, et
+appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé
+par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et
+$\varphi_e(n)$ non défini si cette exécution ne termine pas).
+Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante :
+\[
+b(n) = \max\{\varphi_e(n) : 0\leq e\leq n
+\text{~et~}\varphi_e(n)\text{~défini}\}
+\]
+(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$
+qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.)
+
+\textbf{(2)} On veut montrer que pour toute fonction calculable
+$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour
+tout $n\geq n_0$ on ait $b(n) > f(n)$.  Supposons donc $f\colon
+\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer
+pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire
+$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire
+que $b(n) > f(n)$ lorsque $n\geq p$, et conclure.
+
+\begin{corrige}
+\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$
+l'est et que l'addition l'est.  Il existe donc un algorithme qui la
+calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$.
+
+\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur
+$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies
+lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$.  En
+particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la
+valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une
+fonction totale ici).  On a donc $b(n) \geq \varphi_p(n) = f(n)+1 >
+f(n)$.  On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui
+était voulu (pour $n_0 = p$).
+\end{corrige}
+
+\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites
+ci-dessus) :
+\[
+\lim_{n\to+\infty} \frac{b(n)}{h(n)} = +\infty
+\]
+
+\begin{corrige}
+On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si
+$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$.  Pour cela, soit $C$ un
+réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer
+$C$ entier.  La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot
+h(n)$) est calculable car $h$ l'est (question (1)) et que la
+multiplication l'est.  D'après la question (2), il existe $n_0$ tel
+que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on
+voulait montrer.
+\end{corrige}
+
+\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du
+problème de l'arrêt de manière légèrement différente de ce qui a été
+vu en cours.  Supposons donc par l'absurde que le problème de l'arrêt
+$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit
+décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette
+hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure.
+
+\begin{corrige}
+\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$
+qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$,
+cet algorithme est censé terminer en temps fini et répondre « oui » si
+le programme codé par $e$ termine sur l'entrée $n$, « non » sinon.  On
+peut alors calculer $b(n)$ de la manière suivante : on démarre avec
+$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour
+chacune des valeurs en question, on utilise $T$ pour savoir si
+$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule
+cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce
+calcul termine en temps fini justement puisque $\varphi_e(n)$ est
+défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$.
+À la fin de la boucle, on a bien calculé le max de toutes les valeurs
+$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$.  La fonction
+$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème
+de l'arrêt l'est).
+
+\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il
+existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$.
+Comme on vient de voir que (sous l'hypothèse que le problème de
+l'arrêt est calculable) la fonction $b$ est calculable, en appliquant
+ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq
+n_0$ on ait $b(n) > b(n)$, ce qui est absurde.  C'est donc que
+l'hypothèse était absurde : le problème de l'arrêt n'est pas
+décidable.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
diff --git a/errata-notes-inf105.tex b/errata-notes-inf105.tex
index 4afd008..05f6445 100644
--- a/errata-notes-inf105.tex
+++ b/errata-notes-inf105.tex
@@ -71,187 +71,144 @@ Git: \input{vcline.tex}
 %
 %
 
+\newlength{\oldparindent}
+\oldparindent=\parindent
+\renewcommand{\narrower}{\advance\leftskip\oldparindent\advance\rightskip\oldparindent}
+\parindent=0pt
+\parskip=6ptplus6pt
+
 Les errata suivants sur le document « THL (Théorie des langages) /
 Notes de cours » sont relatifs à la version étiquetée
-\verb=f1826f0 Tue Nov 14 13:05:17 2017 +0100=
-et distribuée pour l'année universitaire 2017–2018.
-
-\medskip
-
-¶1.2.6, dernier paragraphe, (page 5), l'affirmation « Le suffixe
-correspondant au préfixe $abb$ est $bcab$ puisque $abbcab =
-(abb)(bcab)$ » est incorrecte, il faut remplacer $bcab$ par $cab$ et
-lire : « Le suffixe correspondant au préfixe $abb$ est $cab$ puisque
-$abbcab = (abb)(cab)$ ».
-
-\medskip
-
-{\footnotesize
-
-¶1.5.3, dernier paragraphe, (page 14), au lieu de « racourcis », lire
-« raccourcis ».
+\verb=28531fc Thu Jan 23 14:37:46 2020 +0100=
+et distribuée pour l'année universitaire 2020–2021.
 
 \medskip
 
-Démonstration de la proposition 2.4.6, deuxième paragraphe, (page 27),
-dans la phrase « on crée une transition $q\to q'$ étiquetée par $x$ »,
-la précision que $x \in \Sigma$ peut être utile : remplacer par « on
-crée une transition $q\to q'$ étiquetée par $x \in \Sigma$ ».
+Dans la démonstration de la proposition 3.2.4, qui constitue la
+construction de l'automate de Glushkov d'une concaténation, la
+construction donnée affirme à tort que les états finaux de l'automate
+construit sont uniquement ceux du second automate ($A_2$) concaténé.
+Or il faut aussi marquer comme finaux les états finaux de $A_1$
+\emph{lorsque (et seulement lorsque)} l'état initial $q_2$ de $A_2$
+était final.
 
-\par}
+Pour corriger cette erreur, ajouter à la fin de la phrase (page 32,
+lignes 11–13)
 
-\medskip
+{\narrower
 
-Démonstration du lemme 3.2.2, deuxième paragraphe, (page 30), le
-traitement des états finaux de l'automate $A'$ construit n'est pas
-correct, il faut marquer le nouvel état $q_0$ créé comme final
-lorsqu'il existait un état initial qui était aussi final.  En
-conséquence, remplacer les $F$ de ce paragraphe par $F'$, retirer le
-mot « et » devant « $\delta'$ est la réunion », et ajouter à la fin du
-paragraphe : « et enfin $F' = F$ ou $F' = F\cup\{q_0\}$ selon que
-$I\cap F = \varnothing$ ou $I\cap F \neq \varnothing$ respectivement
-(i.e., $q_0$ est final lorsqu'il existait déjà un état à la fois
-initial et final) ».  Le paragraphe ainsi modifié est le suivant :
-
-{\smallskip
-
-Formellement : soit $A = (Q,I,F,\delta)$.  On définit alors $A' =
-(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus
-\{q_0\}$ (où $\uplus$ désigne une réunion disjointe), $\delta'$ est la
-réunion de l'ensemble des transitions $(q,x,q')$ qui étaient déjà
-dans $\delta$ et de l'ensemble des $(q_0,x,q')$ telles qu'il existe
-une transition $(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$
-ou $F' = F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F
-\neq \varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il
-existait déjà un état à la fois initial et final).
+L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
+que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
+chaque transition sortant de $q_2$ par une transition identiquement
+étiquetée, et de même cible, partant de \emph{chaque} état final
+de $A_1$.
 
 \par}
 
-\medskip
-
-{\footnotesize
-
-¶3.6.3 (page 56), au lieu de « fącon », lire « façon ».
+la parenthèse suivante
 
-\medskip
+{\narrower
 
-¶4.0.1 (page 50), au lieu de « démarré », lire « démarrée ».
+(ces derniers seront marqués finaux si $q_2$ était final dans $A_2$)
 
-\medskip
+\par}
 
-¶4.1.7, second paragraphe, (page 53), pour alléger la syntaxe,
-déplacer la parenthèse commençant par « plus le numéro du type » à la
-fin du paragraphe : « Les grammaires de types 0 et 1, avec celles de
-type 2 c'est-à-dire hors contexte, et celles de type 3 (= régulières)
-qui seront définies en 4.2.2 ci-dessous, forment une hiérarchie
-appelée hiérarchie de Chomsky : plus le numéro du type est élevé plus
-la grammaire est contrainte et plus la classe de langages définie est
-petite. ».
+et remplacer la phrase (page 32, lignes 15–18)
 
-\medskip
+{\narrower
 
-¶4.2.4, deuxième paragraphe, (page 55), au lieu de « racourci », lire
-« raccourci ».
+On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
+l'état initial est $q_1$, les états finaux $F' = F_2$, et la relation
+de transition $\delta$ est la réunion de $\delta_1$, de l'ensemble des
+triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, et enfin de
+l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$
+et que $q\in F_1$.
 
 \par}
 
-\medskip
+par
 
-¶4.4.1 (page 58), la rédaction ne rend pas suffisamment explicite le
-fait que tout nœud qui n'est pas une feuille doit être étiqueté par un
-nonterminal.  Pour rendre ce fait plus explicite, remplacer dans le
-deuxième tiret « si un nœud de l'arbre est étiqueté par $T$ et n'est
-pas une feuille (i.e., s'il a des fils) » par « si un nœud de l'arbre
-n'est pas une feuille (i.e., s'il a des fils) et si on appelle $T$ son
-étiquette », et ajouter après les deux sous-cas de ce tiret
-(c'est-à-dire après « dans $G$ », en passant à la ligne) la
-parenthèse : « dans ces deux sous-cas, il résulte de l'existence d'une
-règle $T\rightarrow\cdots$ que $T$ est un nonterminal : seules les
-feuilles peuvent être étiquetées par un terminal ou $\varepsilon$ ».
-Le passage ainsi modifié est le suivant :
-
-{\smallskip
-
-Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$ et $N$
-l'ensemble de ses nonterminaux.  Un \textbf{arbre d'analyse} (ou
-\textbf{arbre de dérivation} ; en anglais \textbf{parse tree})
-\textbf{incomplet} pour $G$ est un arbre (fini, enraciné et ordonné)
-dont les nœuds sont étiquetés par des éléments de $\Sigma \cup N \cup
-\{\varepsilon\}$, vérifiant les propriétés suivantes :
-\begin{itemize}
-\item la racine de l'arbre est étiquetée par l'axiome $S$ de $G$ ;
-\item si un nœud de l'arbre n'est pas une feuille (i.e., s'il a des
-  fils) et si on appelle $T$ son étiquette, alors
-\begin{itemize}
-\item soit ce nœud a un unique fils étiqueté $\varepsilon$ et il
-  existe une règle $T \rightarrow \varepsilon$ dans $G$,
-\item soit ce nœud a des fils étiquetés par des éléments $x_1\cdots
-  x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une règle $T
-  \rightarrow x_1\cdots x_n$ dans $G$,
-\end{itemize}
-(dans ces deux sous-cas, il résulte de l'existence d'une règle
-$T\rightarrow\cdots$ que $T$ est un nonterminal : seules les feuilles
-peuvent être étiquetées par un terminal ou $\varepsilon$).
-\end{itemize}
+{\narrower
+
+On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
+l'état initial est $q_1$, l'ensemble $F'$ des états finaux est $F_2$
+si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si $q_2$ était
+final dans $A_2$, la relation de transition $\delta'$ est la réunion
+de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in \delta_2$ tels
+que $q\neq q_2$, et enfin de l'ensemble des triplets $(q,x,q')$ tels
+que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$.
 
 \par}
 
-\medskip
+On notera que, en revanche, la remarque qui suit la démonstration, et
+qui décrit une façon de voir la construction en passant par l'ajout
+temporaire de transitions spontanées, est correcte (l'élimination des
+transitions spontanées en question conduira à rendre finaux les états
+de $A_1$ lorsque $q_2$ l'état), et est probablement la façon la plus
+simple de mémoriser cette construction sans se tromper.
 
-¶4.5.2, avant-dernier paragraphe (en-dessous des arbres, page 61),
-l'affirmation « Cette grammaire n'est donc pas ambiguë » est
-incorrecte.  Lire à la place : « Cette grammaire est donc ambiguë ».
+\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
 
 \medskip
 
-{\footnotesize
-
-¶4.7.5, dernier paragraphe, (page 66), au lieu de « complexitée »,
-lire « complexité ».
+Dans la démonstration de la proposition 3.4.7, qui constitue la
+procédure d'élimination des états, il n'est pas suffisamment clair
+quelles sont les paires d'états concernées par l'élimination de
+l'état $q$.  Pour remédier à ce manque de clarté, ajouter une note en
+bas de page après « simultanément pour toute paire » (page 40,
+ligne 14 en partant du bas) :
 
-\smallskip
+{\narrower
 
-¶4.7.6, premier paragraphe, (page 66), au lieu de « meme », lire
-« même ».
+Plutôt qu'examiner toutes les paires, on peut se contenter d'examiner
+les cas où \emph{soit} il existe une transition de $q_1$ vers $q_2$
+\emph{soit} il existe à la fois une transition de $q_1$ vers $q$ et
+une transition de $q$ vers $q_2$.  En revanche, insistons bien sur le
+fait que le cas où $q_1$ et $q_2$ coïncide doit être traité comme les
+autres.
 
 \par}
 
-\medskip
-
-Définition 5.1.5, premier paragraphe, (page 70), retirer la parenthèse
-« (fonction) » après « calculable » (qui était destinée à l'index
-uniquement).
+\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
 
 \medskip
 
-{\footnotesize
+Paragraphe 2.1.7, l'expression rationnelle donnée entre parenthèses
+comporte une faute de frappe : page 18, ligne 9 en partant du bas,
+remplacer $(b|c){*}a(b|c){*}b(a|b|c){*}$ par
+$(b|c){*}a(a|c){*}b(a|b|c){*}$.
 
-Définition 5.1.5, deuxième paragraphe, (page 66), pour éclaircir la
-syntaxe, ajouter « et » devant « « non » ($0$) ».
+\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
 
 \medskip
 
-¶5.1.10 (page 72), il manque « comme » avant le dernier mot :
-remplacer « donne bien le résultat final de $T$ résultat » par « donne
-bien le résultat final de $T$ comme résultat ».
-
-\medskip
+Paragraphe 4.3.2, la grammaire ne devrait pas avoir de
+production $\varepsilon$ compte tenu de ce qui en est dit
+en-dessous  : page 56, ligne 18, remplacer $S \rightarrow U \;|\; V
+\;|\; \varepsilon$ par $S \rightarrow U \;|\; V$.
 
-¶5.2.1, note en bas de page 28, (page 73), retirer la virgule après
-« Java ».
+\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}
 
 \medskip
 
-Démonstration du théorème 5.2.4, premier paragraphe, (page 74),
-remplacer « on n'a pas de choix que de ne pas terminer » par « la
-seule possibilité est de ne pas terminer ».
-
-\medskip
+Paragraphe 4.3.5, il manque à la grammaire $G'$ des productions $U
+\rightarrow \varepsilon$ et $V \rightarrow \varepsilon$ : page 58,
+lignes 4–5, remplacer
+\[
+\begin{aligned}
+U &\rightarrow aUbU\\
+V &\rightarrow bVaV\\
+\end{aligned}
+\]
+par
+\[
+\begin{aligned}
+U &\rightarrow aUbU \;|\; \varepsilon\\
+V &\rightarrow bVaV \;|\; \varepsilon\\
+\end{aligned}
+\]
 
-Démonstration du théorème 5.2.4, deuxième paragraphe, (page 74), pour
-éclaircir la syntaxe, ajouter « et ensuite » devant « (2º) ».
 
-\par}
 
 %
 %
diff --git a/exemples-automates.xoj b/exemples-automates.xoj
new file mode 100644
index 0000000..0b60119
--- /dev/null
+++ b/exemples-automates.xoj
diff --git a/misc/quiz-extract-automata.pl b/misc/quiz-extract-automata.pl
new file mode 100755
index 0000000..8327ce3
--- /dev/null
+++ b/misc/quiz-extract-automata.pl
@@ -0,0 +1,53 @@
+#! /usr/local/bin/perl -w
+
+use strict;
+use warnings;
+
+my $inputfile = $ARGV[0];
+die "please pass input file as argument" unless defined($inputfile);
+my $outputdir = "/tmp/automata";
+
+my $f;
+
+open $f, "<", $inputfile or die "can't open $inputfile: $!";
+my %automata;
+my $thisname;
+while (<$f>) {
+    $thisname = undef if defined($thisname) && /^\\end\{center\}/;
+    $automata{$thisname} .= $_ if defined($thisname);
+    $thisname = $1 if /^\\begin\{center\}\s*\%+\s*NAME:\s*(\S+)/;
+}
+close $f;
+
+my $prologue = <<'__EOF__';
+\documentclass[crop,tikz]{standalone}
+%
+%
+%
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+%
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+__EOF__
+
+mkdir $outputdir;
+
+foreach my $name (keys(%automata)) {
+    chdir $outputdir;
+    print "Processing $name\n";
+    open $f, ">", "${outputdir}/${name}.tex";
+    print $f $prologue;
+    print $f "\\begin{document}\n\n";
+    print $f $automata{$name};
+    print $f "\n\\end{document}\n";
+    close $f;
+    system "pdflatex", "${name}.tex";
+    system "pdf2svg", "${name}.pdf", "${name}.raw.svg";
+    system "scour", "-i", "${name}.raw.svg", "-o", "${name}.svg";
+    system "rsvg-convert", "${name}.svg", "-d", "300", "-p", "300", "-b", "white", "-o", "${name}.png";
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 74b3147..b56b958 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1167,7 +1167,7 @@ L'extension la plus fréquente est celle des \emph{références arrière}
 facteur du mot se retrouve aussi à un autre emplacement.  Par exemple,
 pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression
 régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage
-$\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots
+$\{a^nba^n : n\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots
 formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la
 \emph{même suite de $a$} (le « \texttt{\char"5C\relax 1} » désigne
 « une copie de la chaîne de caractères qui a été capturée par le
@@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne
 respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche
 un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher
 « \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début
-de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le
+de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le
 \texttt{a} soit à la fin de la chaîne donnée, et rechercher
 « \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée
 soit exactement \texttt{a} (cet exemple n'est donc pas très utile,
@@ -1547,7 +1547,7 @@ accepte exactement les mots contenant un $a$ suivi, pas forcément
 immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
 sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
 reconnaissable.  (Il est aussi rationnel puisque dénoté par
-l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.)
+l'expression rationnelle $(b|c){*}a(a|c){*}b(a|b|c){*}$.)
 
 \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA
 est dit \defin[accessible (état)]{accessible} lorsqu'il existe un mot
@@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$.
 
 (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
 ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe
-de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$,
-puis en éliminant les ε-transitions qu'on vient d'ajouter
-(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$
-et $q_2$ devenus inutiles.  Cela donne le même résultat que ce qui
-vient d'être dit.)
+de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$
+(qui cessent d'être initiaux), puis en éliminant les ε-transitions
+qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi
+que les états $q_1$ et $q_2$ devenus inutiles.  Cela donne le même
+résultat que ce qui vient d'être dit.)
 
 Il est alors clair qu'un chemin de l'état initial à un état final dans
 cet automate $A'$ consiste soit en un chemin d'un état initial à un
@@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
 que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
 chaque transition sortant de $q_2$ par une transition identiquement
 étiquetée, et de même cible, partant de \emph{chaque} état final
-de $A_1$.  Graphiquement :
+de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final
+dans $A_2$).  Graphiquement :
 
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
@@ -2852,19 +2853,20 @@ et
 De façon plus formelle, considérons un nouvel ensemble d'états $Q' =
 (Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion
 disjointe.  On définit alors l'automate $A'$ dont l'ensemble d'états
-est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la
-relation de transition $\delta$ est la réunion de $\delta_1$, de
-l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$,
-et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q')
-\in \delta_2$ et que $q\in F_1$.
+est $Q'$, l'état initial est $q_1$, l'ensemble $F'$ des états finaux
+est $F_2$ si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si
+$q_2$ était final dans $A_2$, la relation de transition $\delta'$
+est la réunion de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in
+\delta_2$ tels que $q\neq q_2$, et enfin de l'ensemble des triplets
+$(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$.
 
 (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
 ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une
-ε-transition de chaque état final de $A_1$ vers $q_2$, puis en
-éliminant les ε-transitions qu'on vient d'ajouter
-(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$
-devenu inutile.  Cela donne le même résultat que ce qui vient d'être
-dit.)
+ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse
+d'être initial), puis en éliminant les ε-transitions qu'on vient
+d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état
+$q_2$ devenu inutile.  Cela donne le même résultat que ce qui vient
+d'être dit.)
 
 Il est alors clair qu'un chemin de l'état initial $q_1$ à un état
 final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état
@@ -3639,21 +3641,35 @@ Symboliquement :
 \end{tikzpicture}
 \end{center}
 
-Cette transformation doit être effectuée \emph{simultanément pour
-  toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle
-$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque
-telle paire, on remplace l'étiquette de la transition $r_{12}$ entre
-eux par $(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement
-de l'automate, car tout chemin dans $A$ peut être remplacé par un
-chemin dans $A'$ en effaçant simplement les $q$ (si on considère
-$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on
-voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se
-transformer en $q_1 \to q_2$ en consommant un mot qui vérifie
-l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
-
-En éliminant (dans n'importe quel ordre) tous les états autres que
-$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
-transition $(q_0,r,q_\infty)$, qui est donc essentiellement
+Pour éliminer l'état $q$, cette transformation doit être effectuée
+\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec
+$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il
+existe une transition de $q_1$ vers $q$ et une transition de
+$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une
+transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ :
+pour \emph{chaque} telle paire, on remplace l'étiquette de la
+transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$.  (On
+prendra garde aux cas particuliers suivants : si la transition de $q$
+vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors
+on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du
+fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et
+si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à
+prendre $r_{12}=\bot$, alors on la crée avec l'étiquette
+$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers,
+s'il n'y avait ni transition de $q$ vers lui-même ni de
+$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.)
+
+La transformation qui vient d'être décrite ne change pas le
+fonctionnement de l'automate, car tout chemin dans $A$ peut être
+remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on
+considère $q_1$ et $q_2$ les états avant un bloc de $q$ dans le
+chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to
+q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui
+vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
+
+En éliminant (successivement dans n'importe quel ordre) tous les états
+autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant
+une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement
 l'expression rationnelle $r$.
 \end{proof}
 
@@ -5028,7 +5044,7 @@ langage $L(G)$ que la précédente (elle est donc faiblement équivalente
 l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$)
 \[
 \begin{aligned}
-S &\rightarrow U \;|\; V \;|\; \varepsilon\\
+S &\rightarrow U \;|\; V\\
 U &\rightarrow aUb \;|\; ab\\
 V &\rightarrow aVbb \;|\; abb\\
 \end{aligned}
@@ -5154,8 +5170,8 @@ Un raisonnement analogue montre que la grammaire $G'$ donnée par
 \[
 \begin{aligned}
 S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\
-U &\rightarrow aUbU\\
-V &\rightarrow bVaV\\
+U &\rightarrow aUbU \;|\; \varepsilon\\
+V &\rightarrow bVaV \;|\; \varepsilon\\
 \end{aligned}
 \]
 engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que
diff --git a/programme-inf105.tex b/programme-inf105.tex
index e4ab97a..a65fc55 100644
--- a/programme-inf105.tex
+++ b/programme-inf105.tex
@@ -59,35 +59,36 @@ et notions sur les mots : concaténation de deux mots, longueur d'un
 mot ; préfixe, suffixe, facteur, sous-mot et mot miroir.
 
 Opérations sur les langages : opérations booléennes (complémentaire,
-union, intersection), concaténation, étoile de Kleene.  Définition des
-langages rationnels.  Expressions rationnelles.
+union, intersection), concaténation, étoile de Kleene.
 
+\thingy  Définition des langages rationnels.  Expressions rationnelles.
 
-\thingy Automates finis : automates déterministes (DFA), automates
-déterministes à spécification incomplète, automates non déterministes
-(NFA), automates non déterministes à transitions spontanées
-($\varepsilon$-NFA).
+Automates finis : automates déterministes (DFA), automates
+déterministes à spécification incomplète (DFAi), automates non
+déterministes (NFA), automates non déterministes à transitions
+spontanées ($\varepsilon$-NFA).
 
-Équivalence entre ces différentes sortes d'automates.  Langages
-reconnaissables.
+\thingy Équivalence entre DFA, DFAi, NFA et $\varepsilon$-NFA.
+Langages reconnaissables.
 
-
-\thingy Stabilité des langages reconnaissables par complémentaire,
+Stabilité des langages reconnaissables par complémentaire,
 union, intersection ; stabilité par concaténation et étoile de Kleene.
+
 Les langages rationnels sont reconnaissables.  Automate de Glushkov
 \emph{ou} (au choix) automate de Thompson d'une expression
 rationnelle.
 
-Automates à transitions étiquetées par des expressions rationnelles
+\thingy Automates à transitions étiquetées par des expressions rationnelles
 (informellement), équivalence avec les autres sortes d'automates,
 équivalence avec les expressions rationnelles (par élimination des
 états =algorithme de Kleene).  Équivalence entre langages rationnels
 et reconnaissables.
 
-
-\thingy Énoncé et démonstration du lemme de pompage pour les
+Énoncé et démonstration du lemme de pompage pour les
 langages rationnels (=reconnaissables).
 
+\thingy Exemples d'utilisation du lemme de pompage.
+
 DFA minimal\footnote{On conviendra d'utiliser la notion d'automate
   déterministe \emph{complet}, et la première étape de minimisation
   sera de compléter l'automate en lui ajoutant éventuellement un
@@ -101,43 +102,23 @@ peut décider algorithmiquement si deux expressions rationnelles sont
 \thingy TD sur les automates finis et langages rationnels.
 
 
-\thingy TP sur les expressions régulières et automates finis.
-
-
-\thingy Grammaires hors contexte\footnote{Je propose pour gagner du
-  temps de ne faire que mentionner au passage le fait qu'il existe des
-  grammaires plus générales, sans entrer dans les détails.}, langages
-algébriques (=définis par une grammaire hors contexte).  Dérivations,
-dérivations gauches et droites.  Arbre d'analyse (=de dérivation).
-Ambiguïté (grammaires inambiguës et ambiguës, exemple de langage
-intrinsèquement ambigu).
+\thingy Grammaires hors contexte, langages algébriques (=définis par
+une grammaire hors contexte).  Dérivations\footnote{On pourra même
+  sauter complètement la notion de dérivation et définir le langage
+  engendré par une grammaire à travers les arbres d'analyse.}.  Arbre
+d'analyse (=de dérivation).  Ambiguïté (grammaires inambiguës et
+ambiguës).
 
-
-\thingy Stabilité des langages algébriques par réunion, concaténation
+Stabilité des langages algébriques par réunion, concaténation
 et étoile de Kleene.  Les langages rationnels sont algébriques :
 d'après ce qu'on vient de dire et directement en associant une
 grammaire à un DFA ou NFA.
 
-L'intersection d'un langage algébrique et d'un langage rationnel est
-algébrique (admis sans démonstration).
-
-Lemme de pompage pour les langages algébriques (admis sans
-démonstration, mais on peut esquisser l'idée).
+L'intersection d'un langage algébrique et d'un langage
+rationnel est algébrique (admis sans démonstration).
 
 L'appartenance d'un mot au langage défini par une grammaire hors
-contexte est algorithmiquement décidable (l'énoncer et éventuellement
-expliquer une approche possible\footnote{Par ex., en montrant qu'on
-  peut trouver une grammaire monotone équivalente ; ou bien esquisser
-  comment on peut mettre la grammaire sous forme normale de Chomsky et
-  utiliser l'algorithme de programmation dynamique (CYK) ?} si le
-temps le permet).
-
-Selon le temps disponible : quelques notions sur l'analyse syntaxique
-en pratique : notion d'analyseurs descendants et ascendants (sans
-entrer dans les détails).
-
-
-\thingy TD sur les grammaires hors contexte et langages algébriques.
+contexte est algorithmiquement décidable (admis sans démonstration).
 
 
 \thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
@@ -155,10 +136,10 @@ ensemble est décidable ssi lui et son complémentaire sont
 semi-décidables.  Un ensemble est semi-décidable ssi il est (vide ou)
 énuméré par une fonction calculable.
 
-Notion de machine universelle.  Indécidabilité du problème de l'arrêt.
-
+\thingy Notion de machine universelle.  Indécidabilité du problème de l'arrêt.
 
-\thingy TP sur les grammaires hors contexte avec JavaCC.
+\thingy TD sur les grammaires hors contexte / langages algébriques, et
+sur la calculabilité.
 
 
 %
diff --git a/quiz-20220428.tex b/quiz-20220428.tex
new file mode 100644
index 0000000..faec769
--- /dev/null
+++ b/quiz-20220428.tex
@@ -0,0 +1,238 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\newcounter{quescnt}
+\newenvironment{question}%
+{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
+{\relax}
+\newcounter{answcnt}[quescnt]
+\newcommand\answer{%
+\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
+\newcommand\rightanswer{%
+\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+%
+\begin{document}
+
+\textbf{Questions pour INF105 pour le QCM du 2022-04-28.}
+
+Chaque question comporte \emph{une et une seule réponse correcte}.
+Elle a été indiquée par une flèche ci-dessous :
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants est un facteur de $abcabcabc$ sur
+l'alphabet $\Sigma := \{a,b,c\}$ ?
+
+\answer
+$abab$
+
+\answer
+$aaac$
+
+\answer
+$bcbc$
+
+\rightanswer
+$cabc$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants est un sous-mot de $abcabcabc$ sur
+l'alphabet $\Sigma := \{a,b,c\}$ ?
+
+\answer
+$abacbab$
+
+\rightanswer
+$acbbc$
+
+\answer
+$aabbcc$
+
+\answer
+$acbacb$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$aabbab$
+
+\answer
+$bababa$
+
+\rightanswer
+$ababab$
+
+\answer
+$aaabbb$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $a{*}b{*}a{*}b{*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+$aaabbb$
+
+\answer
+$ababab$
+
+\answer
+$babbba$
+
+\answer
+$baaaba$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $a{*}(bba{*}){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+$abbbba$
+
+\answer
+$aaabbb$
+
+\answer
+$abbaab$
+
+\answer
+$abaabb$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $a{*}(ba{*}ba{*}){*}$ sur
+l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\rightanswer
+l'ensemble des mots dont le nombre total de $b$ est pair
+
+\answer
+l'ensemble des mots dont le nombre total de $b$ est $\geq 2$
+
+\answer
+l'ensemble des mots commençant et finissant à la fois par un $a$
+
+\answer
+l'ensemble des mots commençant par un $a$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Laquelle des expressions rationnelles suivantes est équivalente à
+l'expression $(aa\,|\,aba)$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$ab{*}a$
+
+\answer
+$a{*}ba{*}$
+
+\rightanswer
+$a(\underline{\varepsilon}|b)a$
+
+\answer
+$(a|ab)(ab|a)$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Laquelle des expressions rationnelles suivantes est équivalente à
+l'expression $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$(a|b){*}$
+
+\answer
+$ab(ab){*}$
+
+\answer
+$(ba){*}$
+
+\rightanswer
+$\underline{\varepsilon} \,|\, a(ba){*}b$
+
+\end{question}
+
+
+%
+%
+%
+\end{document}
diff --git a/quiz-20220602.tex b/quiz-20220602.tex
new file mode 100644
index 0000000..93183ff
--- /dev/null
+++ b/quiz-20220602.tex
@@ -0,0 +1,432 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+%
+\newcounter{quescnt}
+\newenvironment{question}%
+{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
+{\relax}
+\newcounter{answcnt}[quescnt]
+\newcommand\answer{%
+\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
+\newcommand\rightanswer{%
+\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+
+\textbf{Questions pour INF105 pour le QCM du 2022-06-02.}
+
+Chaque question comporte \emph{une et une seule réponse correcte}.
+Elle a été indiquée par une flèche ci-dessous :
+
+
+%
+%
+%
+
+\begin{question}
+
+Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
+\{a,b\}$, qui sont tous des sous-ensembles du langage rationnel $L_0
+:= L(a{*}b{*}) = \{a^i b^j : i,j \in \mathbb{N}\}$, un seul est
+rationnel : lequel ?
+
+\answer
+Le langage $\{a^i b^j : i=j\}$ formé des mots de $L_0$ ayant le même
+nombre de $a$ que de $b$.
+
+\answer
+Le langage $\{a^i b^j : i\geq j\}$ formé des mots de $L_0$ ayant au
+moins autant de $a$ que de $b$.
+
+\answer
+Le langage $\{a^i b^j : i\neq j\}$ formé des mots de $L_0$ ayant un
+nombre différent de $a$ et de $b$.
+
+\rightanswer
+Le langage $\{a^i b^j : i\equiv j \pmod{12}\}$ formé des mots de $L_0$
+tels que le nombre de $a$ et de $b$ soient congrus l'un à l'autre modulo $12$
+(c'est-à-dire que la différence entre ces deux nombres soit multiple
+de $12$).
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
+\{a,b\}$, un seul \emph{n'est pas} rationnel : lequel ?
+
+\answer
+Le langage des mots $w$ comportant exactement $42$ lettres $a$ (au
+total, c'est-à-dire $|w|_a = 42$).
+
+\rightanswer
+Le langage des mots $w$ comportant exactement autant de lettres $a$
+que de lettres $b$ (au total, c'est-à-dire $|w|_a = |w|_b$).
+
+\answer
+Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme facteur.
+
+\answer
+Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme sous-mot.
+
+\answer
+Le langage des mots qui \emph{ne sont pas} un sous-mot de “$abbab$”.
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
+\{a,b,c\}$, un seul \emph{n'est pas} rationnel : lequel ?
+
+\answer
+Le langage des mots de longueur $\geq 3$ dont la troisième lettre (à
+partir du début) est identique à la troisième lettre à partir de la
+fin.
+
+\answer
+Le langage des mots de longueur $\geq 3$ dont chaque troisième lettre
+(c'est-à-dire la troisième, la sixième, la neuvième, etc., jusqu'à la
+fin du mot) sont toutes identiques.
+
+\rightanswer
+Le langage des mots de longueur impaire dont la lettre du milieu est
+un $a$.
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel langage reconnaît l'automate fini sur l'alphabet $\Sigma :=
+\{a,b\}$ représenté ci-dessous ?
+
+\begin{center} %% NAME: q4
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (00bp,-70bp) [draw,circle,state] {$3$};
+\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q3) to node[auto] {$a$} (q4);
+  \draw [->] (q1) to node[auto] {$b$} (q3);
+  \draw [->] (q2) to node[auto] {$b$} (q4);
+  \draw [->] (q1) to[loop above] node[auto] {$a,b$} (q1);
+  \draw [->] (q4) to[loop below] node[auto] {$a,b$} (q4);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+Le langage formé des mots de longueur $\geq 2$ dont toutes les lettres
+ne sont pas identiques.
+
+\answer
+Le langage formé des mots de longueur $\geq 2$ dont la dernière lettre
+est identique à la première.
+
+\answer
+Le langage formé des mots comportant au moins deux $a$ ou bien
+comportant au moins deux $b$.
+
+\answer
+Le langage formé des mots dont le nombre de $a$ et le nombre de $b$
+sont tous les deux pairs.
+
+\answer
+Le langage formé des mots ayant $ab$ comme facteur.
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+L'élimination des transitions spontanées sur l'automate fini sur
+l'alphabet $\Sigma := \{a,b\}$ représenté ci-dessous
+
+\begin{center} %% NAME: q5
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+  \draw [->,out=270,in=270] (q3) to node[above] {$\varepsilon$} (q1);
+\end{tikzpicture}
+\end{center}
+
+\noindent s'obtient-elle...
+
+\rightanswer
+En supprimant la transition étiquetée $\varepsilon$ reliant $3$ à $1$
+et en ajoutant une transition étiquetée $a$ reliant $3$ à $2$ ?
+
+\answer
+En supprimant la transition étiquetée $\varepsilon$ reliant $3$ à $1$
+et en ajoutant une transition étiquetée $a$ reliant $2$ à $1$ ?
+
+\answer
+En remplaçant la transition étiquetée $\varepsilon$ reliant $3$ à $1$
+par une transition étiquetée $a$ (toujours reliant $3$ à $1$) ?
+
+\answer
+En remplaçant la transition étiquetée $\varepsilon$ reliant $3$ à $1$
+par une transition étiquetée $b$ (toujours reliant $3$ à $1$) ?
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel est le langage reconnu par l'automate ci-dessous ?
+
+\begin{center} %% NAME: q6
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial above,final,accepting below] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state,initial above,final,accepting below] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,initial above,final,accepting below] {$3$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+$\{\varepsilon,a,b,ab\}$
+
+\answer
+$\{\varepsilon,ab\}$
+
+\answer
+$\{\varepsilon,a,b,ab,ba\}$
+
+\answer
+$\{\varepsilon,ab,ba\}$
+
+\answer
+$\{a,b,ab\}$
+
+\answer
+$\{ab\}$
+
+\answer
+$\varnothing$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel est le langage reconnu par l'automate ci-dessous ?
+
+\begin{center} %% NAME: q7
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state,initial above,final,accepting below] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,initial above] {$3$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\answer
+$\{\varepsilon,a,b,ab\}$
+
+\answer
+$\{\varepsilon,ba\}$
+
+\answer
+$\{\varepsilon,a,b,ab,ba\}$
+
+\answer
+$\{\varepsilon,ab,ba\}$
+
+\answer
+$\{\varepsilon,a,b\}$
+
+\rightanswer
+$\{\varepsilon\}$
+
+\answer
+$\varnothing$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+L'automate canonique (= automate fini déterministe complet ayant le
+nombre minimum possible d'états) équivalent à l'automate $\mathscr{A}$
+représenté ci-dessous
+
+\begin{center} %% NAME: q8
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q1) to node[auto] {$b$} (q2);
+  \draw [->] (q2) to[loop above] node[auto] {$b$} (q2);
+  \draw [->] (q2) to node[auto] {$a$} (q3);
+  \draw [->] (q3) to[loop above] node[auto] {$a,b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\noindent s'obtient-il...
+
+\answer
+En ne changeant rien (l'automate $\mathscr{A}$ est déjà minimal) ?
+
+\rightanswer
+En fusionnant les états $2$ et $3$ (donnant un automate minimal à deux états) ?
+
+\answer
+En fusionnant les états $1$ et $2$ (donnant un automate minimal à deux états) ?
+
+\answer
+En fusionnant tous les états (donnant un automate minimal à un seul état) ?
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Parmi les expressions rationnelles ci-dessous, laquelle dénote le
+langage reconnu par l'automate suivant ?
+
+\begin{center} %% NAME: q9
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state,final] {$2$};
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->,out=30,in=150] (q1) to node[auto] {$\varepsilon$} (q2);
+  \draw [->,out=210,in=330] (q2) to node[auto] {$\varepsilon$} (q1);
+  \draw [->] (q2) to[loop above] node[auto] {$b$} (q2);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+$(a|b){*}$
+
+\answer
+$(ab|ba){*}$
+
+\answer
+$(aa|bb){*}$
+
+\answer
+$a{*}\,|\,b{*}$
+
+\answer
+$a(a|b){*}b$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Parmi les expressions rationnelles ci-dessous, laquelle dénote le
+langage reconnu par l'automate suivant ?  (Note : l'expression
+correcte ci-dessous est obtenue en éliminant les états dans
+l'ordre $3,2,1$.)
+
+\begin{center} %% NAME: q10
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (60bp,35bp) [draw,circle,state] {$2$};
+\node (q3) at (60bp,-35bp) [draw,circle,state] {$3$};
+  \draw [<-] (q1) -- ++(-20bp,20bp);
+  \draw [->] (q1) -- ++(-20bp,-20bp);
+  \draw [->,out=90,in=150] (q1) to node[auto] {$a$} (q2);
+  \draw [->,out=330,in=30] (q2) to node[auto] {$b$} (q3);
+  \draw [->,out=210,in=270] (q3) to node[auto] {$c$} (q1);
+  \draw [->] (q2) to node[auto] {$a$} (q1);
+  \draw [->] (q3) to node[auto] {$b$} (q2);
+  \draw [->] (q1) to node[auto] {$c$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+$(cc\,|\,(a|cb)(bb){*}(a|bc)){*}$
+
+\answer
+$(a(b(cc){*}b){*}a){*}$
+
+\answer
+$(abc|cba){*}$
+
+\answer
+$(aa|b(aa|cc)b|cc){*}$
+
+\end{question}
+
+
+%
+%
+%
+\end{document}
diff --git a/rattrapage-20230621.tex b/rattrapage-20230621.tex
new file mode 100644
index 0000000..27d0168
--- /dev/null
+++ b/rattrapage-20230621.tex
@@ -0,0 +1,575 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances (rattrapage) — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances (rattrapage)\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{21 juin 2023}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+Documents autorisés : uniquement une feuille A4 recto-verso
+(manuscrite ou typographiée).
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+\ifcorrige
+Ce corrigé comporte 6 pages (page de garde incluse).
+\else
+Cet énoncé comporte 3 pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+% NOTE: Initially copied from controle-20180322.tex
+
+Dans cet exercice, on pose $\Sigma = \{a,b,c\}$.  On appelle $L$ le
+langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot,
+c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre
+mais non nécessairement consécutivement (à titre d'exemple, $abac \in
+L$).
+
+\textbf{(1)} Proposer un automate non-déterministe (NFA), sans
+transition spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$.
+On justifiera rapidement pourquoi l'automate proposé convient.
+
+\begin{corrige}
+On peut proposer l'automate $\mathscr{A}_1$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+Pour se convaincre qu'il convient, on remarque qu'un chemin de
+l'unique état initial ($0$) à l'unique état final ($3$) dans cet
+automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to
+3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement,
+intercalées d'un nombre quelconque de transitions d'un état vers
+lui-même, étiquetées par une lettre quelconque : la lecture de ses
+étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et
+réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une
+fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux
+transitions changeant d'état).
+
+\emph{Remarque :} il est correct de donner directement l'automate
+déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA
+est, en particulier, un NFA), à condition de justifier proprement
+qu'il convient.
+\end{corrige}
+
+\textbf{(2)} Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$
+trouvé en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant.
+
+\begin{corrige}
+En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' :=
+\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui
+correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$
+qu'on vient d'indiquer, la déterminisation conduit à l'automate
+$\mathscr{A}_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(3)} Minimiser (si nécessaire) l'automate $\mathscr{A}_2$
+obtenu en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal
+(=canonique) résultant.
+
+\begin{corrige}
+On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans
+état inaccessible.  La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et
+$3'$ (final) de l'autre.  Ensuite on sépare $0',1'$ d'une part et $2'$
+de l'autre (car les premiers ne conduisent qu'à des états non finaux,
+tandis que $2'$ conduit à un état final par la transition
+étiquetée $c$).  L'étape suivante sépare $0'$ et $1'$ (car le premier
+ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape
+précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$
+par la transition étiquetée $b$).  On a donc séparé tous les états, ce
+qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal.
+
+\emph{Remarque :} on pouvait aussi invoquer l'argument suivant :
+puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots
+stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin
+d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe
+quel automate reconnaissant $L$.  Comme $\mathscr{A}_2$ a
+effectivement $4$ états, il est forcément minimal.
+\end{corrige}
+
+\textbf{(4)} Construire un automate $\mathscr{A}_4$ reconnaissant le
+langage $M := \Sigma^*\setminus L$ complémentaire de $L$.
+
+\begin{corrige}
+On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate
+$\mathscr{A}_4$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(5)} En appliquant à $\mathscr{A}_4$ la méthode d'élimination
+des états, déterminer une expression rationnelle dénotant le
+langage $M$.  (Si on souhaite obtenir une expression plus compacte, il
+est recommandé de commencer l'élimination des états par ceux qui sont
+le plus loin de l'état initial.)
+
+\begin{corrige}
+On va manipuler des automates finis à transitions étiquetées par des
+expressions rationnelles (ou « RNFA »).  Dans un premier temps, on
+donne à l'automate un unique état final $F$ en faisant pointer vers
+lui une transition spontanée (i.e., étiquetée
+par $\underline{\varepsilon}$) depuis tout état qui était final, et un
+unique état initial $I$ depuis lequel on fait partir une transition
+spontanée vers $0'$.  L'état $3'$ peut être éliminé d'emblée puisqu'il
+est inutile (il n'est pas co-accessible : c'est un puits !).  Par
+ailleurs, deux transitions entre les mêmes états sont remplacées par
+une seule étiquetée par la disjonction des étiquettes (par exemple,
+les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées
+par une seule étiquetée $b|c$).  On a donc affaire à l'automate
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2);
+\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $2'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+(on a fait usage du fait évident que l'expression rationnelle
+$r\underline{\varepsilon}$ est équivalente à $r$).  On élimine
+ensuite l'état $1'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF);
+\end{tikzpicture}
+\end{center}
+Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement
+deux états $I$ et $F$ reliés par une transition étiquetée par
+\[
+(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big)
+\]
+qui est l'expression rationnelle recherchée (dénotant $M$).
+
+L'élimination des états dans l'ordre $0',1',2'$ conduirait à
+l'expression rationnelle moins compacte
+\[
+\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*}
+\]
+qui est cependant sans doute plus lisible.
+
+\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression
+rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci
+ne répond pas à la question car elle ne peut pas s'obtenir par
+élimination des états à partir de $\mathscr{A}_4$.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+% NOTE: Initially copied from controle-20180322.tex
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On appelle $L = L(G)$
+le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
+\end{aligned}
+\]
+
+Les questions de cet exercice sont essentiellement indépendantes, si
+ce n'est que la question (6) fait appel à la conclusion (énoncée) des
+questions (2) à (5).
+
+\smallskip
+
+\textbf{(1)} Donner deux arbres d'analyse (pour $G$) différents du
+mot $aab$.  Que peut-on dire de la grammaire $G$ ?
+
+\begin{corrige}
+On peut proposer les arbres d'analyse suivants :\\
+% S<a.S<a.S<e.>>b.S<e.>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S3);
+\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'une part,\hfill et
+% S<a.S<a.S<e.>b.S<e.>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b0);
+\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S3);
+\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'autre part\\
+(en fait, on peut se convaincre que ce sont les seuls possibles).
+La grammaire $G$ est donc ambiguë.
+\end{corrige}
+
+L'objet des questions suivantes est de montrer que $L$ n'est pas
+rationnel.
+
+Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des
+mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels
+quelconques.
+
+\textbf{(2)} Donner une expression rationnelle qui dénote $M$.
+
+\begin{corrige}
+Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$.
+\end{corrige}
+
+Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la
+forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq
+j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que
+de $b$).
+
+\textbf{(3)} Montrer que $P \subseteq L$.
+
+\begin{corrige}
+Soient $i\geq j$ deux entiers naturels : on va expliquer comment
+produire le mot $a^i b^j$ selon les règles de $G$.  À partir de
+l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a
+\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS
+\Rightarrow \cdots \Rightarrow a^{i-j} S$.  Appliquons maintenant $j$
+fois la règle $S\rightarrow aSbS$, suivie à chaque fois de
+$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi
+$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b
+\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow
+\cdots \Rightarrow a^i S b^j$.  Il suffit de terminer par une
+application de $S \rightarrow \varepsilon$ : on obtient ainsi une
+dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j
+\in L$.
+
+(On pouvait aussi, plus informellement, esquisser l'allure d'un arbre
+de dérivation de $a^i b^j$ un peu à la manière de l'un ou l'autre de
+ceux de la question (1), mais en appliquant $i-j$ fois la règle $a
+\rightarrow aS$ et $j$ fois la règle $S \rightarrow aSbS$.)
+\end{corrige}
+
+\textbf{(4)} Montrer que $L\cap M \subseteq P$.
+
+\begin{corrige}
+Considérons la propriété « avoir (au total) au moins autant de $a$ que
+de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
+(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup
+N = \{a,b,S\}$).  Cette propriété est vérifiée par le pseudo-mot $S$.
+Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou
+$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente
+d'au moins autant que le nombre de $b$.  Elle est donc possédée par
+tout pseudo-mot, et en particulier tout mot, qui dérive de $S$
+selon $G$.  On vient donc de prouver que tout mot de $L$ a au moins
+autant de $a$ que de $b$.  Notamment, tout mot de $L\cap M$ est un mot
+de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq
+j$ (c'est ce qu'on vient de prouver).  Il est donc dans $P$.
+\end{corrige}
+
+\textbf{(5)} Montrer que $P$ n'est pas rationnel.
+
+\begin{corrige}
+Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit
+rationnel.  Appliquons le lemme de pompage pour les langages
+rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de
+pompage garantit l'existence.  Considérons le mot $t := a^k b^k$ (qui
+appartient bien à $P$ et est bien de longueur $\geq k$) : il doit
+alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$,
+non nécessairement dans $P$) pour laquelle on a
+(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ 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 b^k$ est de cette forme) ; disons $u =
+a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} 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} b^k$ appartient à $P$ ; or pour $i=0$,
+ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$.  On a donc
+abouti à une contradiction, et c'est que $P$ n'est pas rationnel.
+\end{corrige}
+
+\textbf{(6)} Déduire des questions (2) à (5) que $L$ n'est pas
+rationnel (on explicitera très soigneusement le raisonnement).
+
+\begin{corrige}
+On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs
+trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$.  Mais
+on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap
+M = P$.  Le langage $M$ est rationnel d'après la question (2).  Si le
+langage $L$ était lui aussi rationnel, le langage $L\cap M$
+(c'est-à-dire $P$) le serait car l'intersection de deux langages
+rationnels est rationnelle.  Or on a vu à la question (5) que $P$
+n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+% NOTE: Initially copied from controle-20210618.tex
+
+(Les deux questions suivantes sont indépendantes.)
+
+\smallskip
+
+\textbf{(1)} Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas
+algébrique\footnote{Ce fait est démontré dans le poly, dans la section
+  consacrée au lemme de pompage pour les langages algébriques et comme
+  illustration de ce dernier ; on ne demande pas ici de le
+  redémontrer : on peut le tenir pour admis.}.  Est-il rationnel ?
+Est-il décidable ?  Est-il semi-décidable ?  On justifiera
+soigneusement les réponses.
+
+\begin{corrige}
+Le langage proposé n'est pas rationnel car il n'est pas algébrique.
+
+Il est décidable car il est évident qu'on peut algorithmiquement d'une
+part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
+par automate fini) et d'autre part vérifier qu'il a autant de $a$ que
+de $b$ que de $c$.
+
+Étant décidable, il est notamment semi-décidable.
+\end{corrige}
+
+\smallskip
+
+\textbf{(2)} On rappelle la définition du problème de l'arrêt : c'est
+l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un
+  codage permettant de représenter les programmes $e$, les entrées $x$
+  à ces programmes, et les couples $(e,x)$, comme des éléments
+  de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet
+  $\Sigma\neq\varnothing$ arbitraire).  Il n'est pas nécessaire de
+  faire apparaître ce codage dans la description des algorithmes
+  proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme
+(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du
+programme $e$ sur l'entrée $x$ termine en temps fini.  On a vu en
+cours que $H$ était semi-décidable mais non décidable.
+
+On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ et $(e_2,x) \not\in H$.  Autrement dit, le programme
+$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais
+le programme $e_2$, lui, ne termine pas sur cette même entrée.
+L'ensemble $J$ est-il décidable ?  Semi-décidable ?  On justifiera
+soigneusement.
+
+\begin{corrige}
+L'ensemble $J$ n'est pas semi-décidable.
+
+Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme
+$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$
+signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie
+appartient à $Z$, et ne pas terminer sinon).  Fixons une fois pour
+toutes (le code d')un programme $f$ qui, donnée une entrée $x$,
+termine immédiatement (en ignorant $x$).  Alors trivialement $(f,x)
+\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x)
+\in J$ si et seulement si $(e,h) \not \in H$.
+
+On considère alors l'algorithme $T'$, défini de la manière suivante :
+donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister)
+au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in
+J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais).  Par
+construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
+$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
+termine pas.  Ceci signifie que $T'$ semi-décide le complémentaire
+de $H$.
+
+Or le complémentaire de $H$ n'est pas semi-décidable (car si le
+complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et
+son complémentaire semi-décidables, donc $H$ serait décidable, et on
+sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas
+exister.  C'est une contradiction : $J$ n'est donc pas semi-décidable.
+
+\textit{A fortiori}, $J$ n'est pas décidable.
+\end{corrige}
+
+
+%
+%
+%
+\end{document}