1 files changed, 32 insertions, 28 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex
index 8db45ea..94058dd 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -158,13 +158,13 @@ automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to
 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 au moins un chemin de $0$ à $3$
-(une fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront
-aux transitions changeant d'état).
+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 NFA
-est, en particulier, un DFA), à condition de justifier proprement
+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}
 
@@ -176,7 +176,7 @@ 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}_1$ suivant :
+$\mathscr{A}_2$ suivant :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$};
@@ -203,14 +203,14 @@ résultant.
 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'$ (finaux) 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
+$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.
+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
@@ -249,7 +249,7 @@ $\mathscr{A}_3$ suivant :
 é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
-plutôt proches de l'état final.)
+le plus loin de l'état initial.)
 
 \begin{corrige}
 On va manipuler des automates finis à transitions étiquetées par des
@@ -258,12 +258,13 @@ 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
+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,c$ sont remplacées par
-une seule étiquetée $b|c$).  On a donc affaire à l'automate suivant :
+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$};
@@ -427,7 +428,7 @@ dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j
 
 \begin{corrige}
 Considérons la propriété « avoir (au total) au moins autant de $a$ que
-de $b$ », si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
+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
@@ -448,7 +449,8 @@ 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$ pour laquelle on a
+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
@@ -482,14 +484,16 @@ n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
 \exercice
 
 Dans cet exercice, on s'intéresse au langage $L$ formé des
-programmes $e$ (codés, dans un langage Turing-complet fixé quelconque,
-comme des entiers naturels ou comme des mots sur un alphabet fixé sans
-importance) qui, quel que soit le paramètre $n$ qu'on leur fournit
-en entrée, terminent en temps fini et retournent la valeur $0$ : soit
-$L = \{e : (\forall n) {\varphi_e(n)\downarrow} = 0\}$.  Si l'on
-préfère, $L$ est l'ensemble de toutes les façons de coder la fonction
-constante égale à $0$.  On appellera aussi $M$ le complémentaire
-de $L$.  On se demande si $L$ ou $M$ sont semi-décidables.
+programmes $e$ (codés, dans une formalisation quelconque de la
+calculabilité\footnote{Par exemple, un langage de programmation
+  (Turing-complet) quelconque.}, comme des entiers naturels ou comme
+des mots sur un alphabet fixé sans importance) qui, quel que soit le
+paramètre $n$ qu'on leur fournit en entrée, terminent en temps fini et
+retournent la valeur $0$ : soit $L = \{e : (\forall n)
+{\varphi_e(n)\downarrow} = 0\}$.  Si l'on préfère, $L$ est l'ensemble
+de toutes les façons de coder la fonction constante égale à $0$.  On
+appellera aussi $M$ le complémentaire de $L$.  On se demande si $L$ ou
+$M$ sont semi-décidables.
 
 \smallskip
 
@@ -561,7 +565,7 @@ finie au bout de ce temps.
 \medskip
 
 (2) Achille et Patrocle se disputent pour savoir si $M$ (le
-complémentaire de $L$) est semi-décidable.  Achile pense qu'il l'est,
+complémentaire de $L$) est semi-décidable.  Achille pense qu'il l'est,
 et il tient le raisonnement suivant pour l'expliquer :
 
 {\narrower