Re-read exercise sheet.

1 files changed, 25 insertions, 23 deletions

diff --git a/exercices1.tex b/exercices1.tex
index f3a7115..d51e3b7 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -104,16 +104,15 @@ expression rationnelle qui le dénote, et montrer qu'il est
 reconnaissable en exhibant directement un automate fini qui le
 reconnaît.
 
-(2) On définit la \emph{valeur numérique} d'un mot sur $\Sigma$
-(=: mot binaire) $x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$
-(où $x_i$ vaut $0$ ou $1$ et est numéroté de $0$ pour le chiffre le
-plus à droite à $n-1$ pour le plus à gauche) ; la valeur numérique du
-mot vide $\varepsilon$ est $0$.
+(2) On définit la \emph{valeur numérique} d'un mot binaire
+$x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$ (où $x_i$ vaut
+$0$ ou $1$ et est numéroté de $0$ pour le chiffre le plus à droite
+à $n-1$ pour le plus à gauche) ; la valeur numérique du mot
+vide $\varepsilon$ est $0$.
 
-Parmi les langages suivants, certains sont rationnels, d'autres ne le
-sont pas.  Dire lesquels sont rationnels et justifier brièvement
-pourquoi (on ne demande pas de justifier pourquoi ceux qui ne sont pas
-rationnels ne le sont pas) :
+Parmi les langages suivants, certains sont rationnels.  Dire lesquels
+et justifier brièvement pourquoi ils le sont (on ne demande pas de
+justifier pourquoi ceux qui ne sont pas rationnels ne le sont pas) :
 
 (a) le langage $L_a$ des mots binaires dont la valeur numérique est
 paire,
@@ -133,8 +132,8 @@ nombre premier,
 une puissance de $2$,
 
 \begin{corrige}
-(1) On peut écrire $L_n = L_r$, langage dénoté par l'expression
-  rationnelle $r := 0|1(0|1){*}$.  Ce langage est reconnu, par
+(1) On peut écrire $L_n = L_{0|1(0|1){*}}$, langage dénoté par
+  l'expression rationnelle $0|1(0|1){*}$.  Ce langage est reconnu, par
   exemple, par le DFAI suivant :
 \begin{center}
 %%% begin ex1p1 %%%
@@ -158,7 +157,8 @@ mots binaires qui soit sont le mot vide soit finissent par $0$ : il
 est dénoté par l'expression rationnelle
 $\underline{\varepsilon}|(0|1){*}0$.\spaceout (b) On a $L_b = L_a \cap
 L_n$ et on a vu que $L_a$ et $L_n$ sont rationnels, donc $L_b$ l'est
-aussi.
+aussi (on peut aussi exhiber une expression rationnelle qui le
+dénote : $0|1(0|1){*}0$).
 
 (c) Ajouter un $0$ ou un $1$ à la fin d'un mot binaire de valeur
 numérique $n$ le transforme en un mot de valeur numérique $2n+x$
@@ -206,8 +206,8 @@ veut reconnaître les multiples de $3$.)
 (d) Le langage $L_d$ n'est pas rationnel (on pourrait le démontrer à
 l'aide du lemme de pompage, mais ce n'est pas très facile).
 
-(e) Le langage $L_e$ est rationnel car il s'agit du langage des dénoté
-par l'expression rationnelle $10{*}$.
+(e) Le langage $L_e$ est rationnel car il s'agit du langage dénoté par
+l'expression rationnelle $10{*}$.
 \end{corrige}
 
 
@@ -289,7 +289,7 @@ en (0).
 
 (1) L'automate ayant des ε-transitions, il ne peut pas être
   déterministe : on a affaire à un εNFA.  Avant de le déterminiser, on
-  élimine ses ε-transitions : la ε-fermeture de $0$ est $\{1,4\}$,
+  élimine ses ε-transitions : la ε-fermeture de $0$ est $\{0,1,4\}$,
   celle de $3$ est $\{3,7\}$ et celle de $6$ est $\{6,7\}$ ; on est
   amené au NFA suivant :
 \begin{center}
@@ -316,10 +316,12 @@ en (0).
 
 %%% end ex1p2b %%%
 \end{center}
-(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés.)
+(Les états $1$ et $4$ étant inaccessibles, ils ont été retirés.  Il ne
+faut pas oublier que $3$ et $6$ sont finaux puisqu'il sont l'état
+final $7$ dans leur ε-fermeture.)
 
-On peut maintenant procéder à la minimisation.  Pour abréger les noms
-des états, on note, par exemple, $023$ pour $\{0,2,3\}$.  En
+On peut maintenant procéder à la déterminisation.  Pour abréger les
+noms des états, on note, par exemple, $023$ pour $\{0,2,3\}$.  En
 construisant de proche en proche, on obtient le DFA suivant :
 \begin{center}
 \scalebox{0.8}{%PLEASE!  There HAS to be a better way to do this!
@@ -389,9 +391,9 @@ construisant de proche en proche, on obtient le DFA suivant :
 }
 \end{center}
 (À titre d'exemple, la transition étiquetée $b$ partant de l'état
-$023$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
-le NFA précédent et partant des états parmi $\{0,2,3\}$ sont $0\to 0$,
-$0\to 5$, $3\to 7$ et $7\to 7$.  Tous les états contenant l'un des
+$0237$ conduit à l'état $057$ car les transitions étiquetées $b$ dans
+le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to
+0$, $0\to 5$, $3\to 7$ et $7\to 7$.  Tous les états contenant l'un des
 symboles $3,6,7$ sont finaux.)
 
 (2) On a affaire à un DFA dont tous les états sont accessibles, on
@@ -400,8 +402,8 @@ partition sépare les états finaux, soit $023, 0237, 027, 056, 0567,
 057$ des non-finaux, soit $0, 02, 05$.  L'étape suivante distingue
 $02$ parce que sa $a$-transition conduit à une classe différente que
 celles de $0$ et $05$, et $05$ parce que sa $b$-transition conduit à
-une classe différente de $0$ et $02$.  Finalement, on arrive à un
-automate à quatre états :
+une classe différente de $0$ et $02$.  Les étapes suivantes ne
+changent rien.  Finalement, on arrive à un automate à quatre états :
 \begin{center}
 %%% begin ex1p2d %%%