Re-read exercises.

1 files changed, 48 insertions, 37 deletions

diff --git a/exercices3.tex b/exercices3.tex
index c2f41cb..7ebae19 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -106,9 +106,9 @@ $a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?
 
 (2) En éliminer les transitions spontanées.
 
-(3) Déterminiser l'automate obtenu.
+(3) Déterminiser l'automate obtenu (on demande un automate complet).
 
-(4) Minimiser l'automate obtenu.
+(4) Minimiser l'automate obtenu (on demande un automate complet).
 
 (5) Vérifier le résultat en décrivant en français le langage dénoté
 par l'expression rationnelle initiale et reconnu par l'automate
@@ -179,16 +179,17 @@ les ε-fermetures $C(q)$ de ces états sont les suivantes :
 $q$&ε-fermeture $C(q)$\\
 \hline
 $0$&$\{0,1,3,4,5,13\}$\\
-$2$&$\{2,3,4,5,13\}$\\
+$2$&$\{1,2,3,4,5,13\}$\\
 $6$&$\{6,7\}$\\
 $8$&$\{5,8,9,10,12,13\}$\\
 $11$&$\{5,10,11,12,13\}$\\
 \end{tabular}
 \end{center}
 
-En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$
-dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel
-que $q^\sharp \in C(q)$, on obtient le NFA suivant :
+En remplaçant chaque transition $q^\sharp \to q'$ étiquetée
+d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour
+chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient le NFA
+suivant :
 
 \begin{center}
 %%% begin ex3p1b %%%
@@ -307,10 +308,10 @@ l'alphabet $\Sigma = \{a,b\}$ :
 %%% end ex3p2 %%%
 \end{center}
 (On pourra considérer les ordres suivants d'élimination des états :
-d'abord $2,1,0$, ensuite $1,2,0$ et enfin $0,2,1$.)
+(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.)
 
 \begin{corrige}
-Si on commence par éliminer l'état $2$ (en considérant l'automate
+(A) Si on commence par éliminer l'état $2$ (en considérant l'automate
 comme un automate à transitions étiquetées par des expressions
 rationnelles), l'état $1$ reçoit une transition vers lui-même
 étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
@@ -325,7 +326,9 @@ obtient finalement l'expression rationnelle
 (a|b(ab{*}a){*}b){*}
 \]
 
-Si on commence par éliminer l'état $1$, il apparaît une transition
+\smallbreak
+
+(B) Si on commence par éliminer l'état $1$, il apparaît une transition
 $0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
 appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
 de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
@@ -345,7 +348,9 @@ une seule étiquetée par $a|b(a(b|aa){*}a){*}b$.  On obtient finalement
 (en particulier, cette expression est équivalente à celle obtenue
 précédemment).
 
-Si on préfère commencer par éliminer l'état $0$, il faut au préalable
+\smallbreak
+
+(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable
 ajouter un nouvel état initial $I$ (conduisant à $0$ par une
 transition spontanée) et un nouvel état final $F$ (vers lequel $0$
 conduit par une transition spontanée).  L'élimination de l'état $0$
@@ -392,7 +397,7 @@ auv$.
 \in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$
 (c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$).  Autrement
 dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un
-mot qui n'appartient jamais à $L$.  (Indication : lorsque $auvz =
+mot qui n'appartient jamais à $L$.  (Indication : si on a $auvz =
 au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
 (iii) $|u'|=|u|$.)
 
@@ -406,10 +411,11 @@ sur $|w|$).
 
 (5) En s'inspirant des questions précédentes, décrire un algorithme
 simple (en une seule fonction récursive) qui, donné un mot
-$w\in\Sigma^*$, décide si $w\in L$ (c'est-à-dire répond vrai ou faux
-selon que $w\in L$ ou $w\not\in L$) ou plus généralement, donné
-$w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant
-à $L$ s'il existe (il est alors unique d'après la question (2)).
+$w\in\Sigma^*$ renvoie la longueur du préfixe de $w$ appartenant à $L$
+s'il existe (il est alors unique d'après la question (2)) ou bien
+« échec » s'il n'existe pas ; expliquer comment s'en servir pour
+décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux
+selon que $w\in L$ ou $w\not\in L$).
 
 \begin{corrige}
 (0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
@@ -417,17 +423,17 @@ $w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant
 
 (1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$
   pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés
-  selon l'une des deux règles de la grammaire, $S\rightarrow b$ ou
-  bien $S\rightarrow aSS$, autrement dit, soit elle a un unique fils
-  étiqueté $b$, soit elle a trois fils étiquetés respectivement
+  selon l'une des deux règles de la grammaire, soit $S\rightarrow b$
+  ou bien $S\rightarrow aSS$, autrement dit, soit elle a un unique
+  fils étiqueté $b$, soit elle a trois fils étiquetés respectivement
   $a,S,S$.  Dans le premier cas, le mot $w$ est simplement $b$ ; dans
   le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour
   racine les deux fils étiquetés $S$ sont encore des arbres d'analyse
   pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des
   arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles
   de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de
-  profondeur), alors on a $w = auv$ et $u,v\in L$ puisqu'ils ont des
-  arbres d'analyse pour $G$.
+  profondeur), alors on a $w = auv$ et $u,v\in L$ (puisqu'ils ont des
+  arbres d'analyse pour $G$).
 
 La réciproque est analogue : le mot $b$ appartient trivialement à $L$,
 et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
@@ -490,8 +496,9 @@ deux cas sont évidemment incompatibles : il reste donc simplement à
 expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont
 uniquement déterminés.  Or la question (3) assure que $u,v$ (tels que
 $w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence
-permet de conclure que les arbres d'analyse $\mathscr{U}$ et
-$\mathscr{V}$ sont uniquement déterminés, comme on le voulait.
+permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres
+d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement
+déterminés, comme on le voulait.
 
 \smallbreak
 
@@ -507,8 +514,8 @@ appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
 \item appeler la fonction elle-même (rechercher préfixe dans $L$)
   sur $x$ :
 \item si elle échoue, renvoyer échec,
-\item si elle retourne $k$, soit $u$ le préfixe de $y$ de longueur
-  $k$, et $z$ le suffixe correspondant (c'est-à-dire $y = ux$, ou si
+\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur
+  $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, ou si
   on préfère, $y$ enlève les $k$ premières lettres de $x$),
 \item appeler la fonction elle-même (rechercher préfixe dans $L$)
   sur $y$ :
@@ -529,7 +536,7 @@ dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce
 qu'affirme la non-ambiguïté de la grammaire).
 
 (Il s'agit ici du cas le plus simple d'un analyseur LL, et
-l'algorithme présenté ci-dessus est essentiellement un analyseur LL
+l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1)
 camouflé sous forme d'analyseur par descente récursive.)
 \end{corrige}
 
@@ -658,7 +665,7 @@ de l'arrêt.)
   allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
   facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
   $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
-  commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
+  commençant à la position $i \ell$) : s'ils sont tous égaux, renvoyer
   vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
   renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
     fortiori} semi-décidable).
@@ -684,7 +691,11 @@ de l'arrêt.)
   considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
   programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
   valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
-  un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
+  un tel $e'$ se calcule algorithmiquement\footnote{Techniquement, on
+    invoque ici le théorème s-m-n ; mais dans les faits, il s'agit
+    essentiellement d'ajouter une ligne « \texttt{let
+      n=}(représentation décimale de $n$) » au début d'un programme,
+    ce qui est certainement faisable.} à partir de $e$ et $n$.
   L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
   autre entrée) se comporte donc comme l'exécution du programme $e$
   sur l'entrée $n$, et notamment, termine si et seulement si elle
@@ -695,7 +706,7 @@ de l'arrêt.)
   décidable, le problème de l'arrêt le serait, ce qui n'est pas le
   cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
   semi-décidable : il suffit de lancer l'exécution du programme $e$
-  sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
+  sur l'entrée $42$ et renvoyer vrai si elle termine (si elle ne
   termine pas, on ne termine pas).
 \end{corrige}
 
@@ -718,8 +729,8 @@ factoriser en mots de longueur non nulle).
 
 (B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
 alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
-semi-décidables ; montrer que si un langage $L$ est décidable alors
-$L^*$ est semi-décidable.
+semi-décidables ; montrer que si un langage $L$ est semi-décidable
+alors $L^*$ est semi-décidable.
 
 \begin{corrige}
 (A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
@@ -756,7 +767,7 @@ facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
 boucles emboîtées pour déterminer les limites des facteurs
 $u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
 par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
-lorsque $i_1+\cdots+i_k = n$, appaler $u_j$ le facteur de $w$ de
+lorsque $i_1+\cdots+i_k = n$, appeler $u_j$ le facteur de $w$ de
 longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$).  Pour
 chaque factorisation comme on vient de le dire, on teste si tous les
 $u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
@@ -772,12 +783,12 @@ encore factorisable en mots non vides de $L$.)
 
 (B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
 n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
-terminer.  On doit donc les lancer « en parallèle » et pas « en
-  série » : lorsqu'on dira qu'on lance deux algorithmes $T$ et $T'$
-« en parallèle », cela signifie qu'on exécute une étape du calcul de
-$T$, puis une étape de $T'$, puis de nouveau une de $T$, et ainsi de
-suite en alternant entre les deux, jusqu'à ce que l'un termine et
-renvoie vrai.
+terminer.  À part pour l'intersection, on doit donc les lancer « en
+parallèle » et pas « en série » : lorsqu'on dira qu'on lance deux
+algorithmes $T$ et $T'$ « en parallèle », cela signifie qu'on exécute
+une étape du calcul de $T$, puis une étape de $T'$, puis de nouveau
+une de $T$, et ainsi de suite en alternant entre les deux, jusqu'à ce
+que l'un termine et renvoie vrai.
 
 Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
 algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps