Take into account Akim's remarks.

1 files changed, 86 insertions, 80 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index 1d42a3e..dae78cd 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -101,7 +101,7 @@ de traiter toutes les questions pour obtenir la totalité des points.
 L'usage de tous les documents (notes de cours manuscrites ou
 imprimées, feuilles d'exercices, livres) est autorisé.
 
-L'usage des calculatrices électroniques est interdit.
+L'usage des appareils électroniques est interdit.
 
 \medbreak
 
@@ -118,7 +118,7 @@ L'énoncé comporte 4 pages (page de garde incluse)
 
 \exercice
 
-On considère l'automate fini sur l'alphabet $\Sigma = \{a,b\}$
+On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$
 représenté par la figure suivante :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
@@ -145,7 +145,7 @@ représenté par la figure suivante :
 déterministe ou non ? avec transitions spontanées ou non ?)
 
 (1a) Décrire brièvement, en français, le langage $L$ reconnu
-(=accepté) par l'automate en question, puis donner une expression
+(=accepté) par l'automate $M$, puis donner une expression
 rationnelle qui le dénote.  (On pourra préférer traiter la question
 (1b) d'abord.)
 
@@ -155,17 +155,21 @@ $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
 rapidement les réponses aux questions suivantes et ainsi détecter
 d'éventuelles erreurs lors des transformations des automates.)
 
-(2) Éliminer les transitions spontanées de l'automate.
-(On supprimera les états devenus inutiles.)
+(2) Éliminer les transitions spontanées de l'automate $M$.  (On
+supprimera les états devenus inutiles.)  On appellera $M_2$ l'automate
+obtenu.
 
-(3) Déterminiser l'automate ainsi obtenu, si nécessaire.  (On demande
-un automate déterministe complet.)  Pour simplifier le travail du
-correcteur, on demande de faire en sorte que les transitions
-étiquetées par $a$ soient, dans la mesure du possible, horizontales de
-la gauche vers la droite, et celles étiquetées par $b$, verticales du
-haut vers le bas.
+(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire.  (On
+demande un automate déterministe complet.)  On appellera $M_3$
+l'automate déterminisé.
 
-(4) Minimiser l'automate ainsi obtenu, si nécessaire (justifier).
+Pour simplifier le travail du correcteur, on demande de représenter
+$M_3$ de sorte que les transitions étiquetées par $a$ soient, dans la
+mesure du possible, horizontales de la gauche vers la droite, et
+celles étiquetées par $b$, verticales du haut vers le bas.
+
+(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire
+(justifier).
 
 (5) Donner un automate (de n'importe quelle sorte) qui reconnaît le
 langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.
@@ -179,22 +183,23 @@ complémentaire $\overline{L}$.  (Ne pas hésiter à introduire des
 notations intermédiaires.)
 
 \begin{corrige}
-(0) Il s'agit d'un automate non-déterministe à transitions spontanées,
-  ou ε-NFA (il n'y a pas de notion d'automate déterministe à
-  transitions spontanées).
+(0) L'automate $M$ est un automate fini non-déterministe à transitions
+  spontanées, ou ε-NFA (le concept d'« automate déterministe à
+  transitions spontanées » n'aurait tout simplement pas de sens).
 
 \smallbreak
 
 (1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
 un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le chemin par
 les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
-c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate dans son
-ensemble accepte les mots comportant exactement un $a$ ou (inclusif)
-exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1
+c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate $M$ dans
+son ensemble accepte les mots comportant exactement un $a$ ou
+(inclusif) exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1
 \penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le
 nombre total d'occurrences de la lettre $x$ dans le mot $w$).  C'est
-le langage dénoté par l'expression rationnelle $b{*}ab{*} |
-a{*}ba{*}$.
+le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$
+(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi
+noter $+$).
 
 (1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à
 $L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y
@@ -202,11 +207,11 @@ appartiennent pas.
 
 \smallbreak
 
-(2) La ε-fermeture de l'état $X$ est $\{X,A,B\}$ ; la ε-fermeture de
-  l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est $\{B',Y\}$ ;
-  les autres états sont leur propre ε-fermeture (i.e., celle-ci est un
-  singleton).  L'élimination des transitions spontanées conduit donc à
-  l'automate suivant :
+(2) La ε-fermeture (arrière) de l'état $X$ est $\{X,A,B\}$ ; la
+ε-fermeture de l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est
+$\{B',Y\}$ ; les autres états sont leur propre ε-fermeture (i.e.,
+celle-ci est un singleton).  L'élimination des transitions spontanées
+conduit donc à l'automate $M_2$ suivant :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
@@ -231,8 +236,8 @@ non-spontanée n'y conduit.)
 
 \smallbreak
 
-(3) L'algorithme de déterminisation conduit à l'automate suivant où,
-pour plus de lisibilité, les états finaux ont été marqués en les
+(3) L'algorithme de déterminisation conduit à l'automate $M_3$ suivant
+où, pour plus de lisibilité, les états finaux ont été marqués en les
 entourant deux fois plutôt que par une flèche sortante :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
@@ -267,7 +272,7 @@ entourant deux fois plutôt que par une flèche sortante :
 \end{center}
 
 Pour la commodité de la suite de la correction, on renomme les états
-de cet automate de la façon suivante :
+de cet automate $M_3$ de la façon suivante :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
@@ -307,7 +312,7 @@ lettre $b$.
 
 \smallbreak
 
-(4) L'automate obtenu est déjà minimal.  En effet, l'algorithme de
+(4) L'automate $M_3$ est déjà minimal.  En effet, l'algorithme de
 minimisation commence par séparer les classes $\{01,10,11,12,21\}$
 (états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la
 transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en
@@ -327,6 +332,7 @@ automate fini déterministe complet, il suffit d'échanger états finaux
 et non-finaux : on peut donc prendre l'automate dessiné en (3) avec,
 cette fois, la convention que les états simplement entourés sont
 finaux (et les doublement entourés sont non-finaux).
+Appelons-le $M_5$.
 
 \emph{Attention :} échanger états finaux et non-finaux ne marche pas
 pour reconnaître le complémentaire du langage reconnu par un automate
@@ -337,17 +343,17 @@ non-final »).
 
 \smallbreak
 
-(6) Puisque $L$ est le langage formé des mots ayant comportant
-exactement un $a$ ou (inclusif) exactement un $b$, son complémentaire
-$\overline{L}$ est formé des mots ayant un nombre différent de $1$
-de $a$ \emph{et} un nombre différent de $1$ de $b$ ; si on préfère, il
-s'agit du langage comportant ($0$ ou au moins $2$ fois la lettre $a$)
-\emph{et} ($0$ ou au moins $2$ fois la lettre $b$).
+(6) Puisque $L$ est le langage formé des mots comportant exactement un
+$a$ ou (inclusif) exactement un $b$, son complémentaire $\overline{L}$
+est formé des mots ayant un nombre différent de $1$ de $a$ \emph{et}
+un nombre différent de $1$ de $b$ ; si on préfère, il s'agit du
+langage comportant ($0$ ou au moins $2$ fois la lettre $a$) \emph{et}
+($0$ ou au moins $2$ fois la lettre $b$).
 
 \smallbreak
 
-(7) L'élimination des états n'est pas trop complexe car l'automate a
-très peu de boucles.  Éliminons simultanément tous les états
+(7) L'élimination des états n'est pas trop complexe car l'automate
+$M_5$ a très peu de boucles.  Éliminons simultanément tous les états
 non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour
 créer un nouvel (et unique) état final $F$ :
 \begin{center}
@@ -563,33 +569,33 @@ S &\rightarrow TS \;|\; \varepsilon\\
 T &\rightarrow aSbSc\\
 \end{aligned}
 \]
-On notera $L(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,T)$ le
+On notera $L(S) = L_G$ le langage qu'elle engendre, et $L(T)$ le
 langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère, le
 langage engendré par la grammaire identique à $G$ mais ayant $T$ pour
 axiome).
 
-(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,T)$ (au
+(0) Donner quelques exemples de mots de $L(S)$ et de $L(T)$ (au
 moins deux de chaque).
 
-(1) Expliquer brièvement pourquoi $L(G)$ est l'ensemble des mots de la
-forme $u_1\cdots u_k$ avec $u_i \in L(G,T)$, et pourquoi $L(G,T)$ est
-l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(G)$.  (Par
-conséquent, $L(G,T)$ est l'ensemble des mots de la forme $a u_1 \cdots
+(1) Expliquer brièvement pourquoi $L(S)$ est l'ensemble des mots de la
+forme $u_1\cdots u_k$ avec $u_i \in L(T)$, et pourquoi $L(T)$ est
+l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(S)$.  (Par
+conséquent, $L(T)$ est l'ensemble des mots de la forme $a u_1 \cdots
 u_k b u'_1\cdots u'_{\ell} c$ avec
-$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(G,T)$.)
+$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(T)$.)
 
-(2) Comment exprimer $L(G)$ à partir de $L(G,T)$ au moyen d'une ou
+(2) Comment exprimer $L(S)$ à partir de $L(T)$ au moyen d'une ou
 plusieurs opérations rationnelles\footnote{C'est-à-dire : union,
   concaténation, étoile de Kleene.} ?  Y a-t-il inclusion de l'un dans
 l'autre ?
 
-(3) Montrer que tout mot $w$ appartenant à $L(G)$ ou à $L(G,T)$ a le
+(3) Montrer que tout mot $w$ appartenant à $L(S)$ ou à $L(T)$ a le
 même nombre de $a$, de $b$ et de $c$, c'est-à-dire $|w|_a = |w|_b =
 |w|_c$ où $|w|_x$ désigne le nombre total d'occurrences de la
 lettre $x$ dans le mot $w$.
 
 (4) Montrer par récurrence sur la longueur $|u|$ d'un mot $u\in
-L(G,T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$,
+L(T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$,
 alors on a $|v|_c < |v|_a$.  Pour cela, on pourra écrire $u$ sous la
 forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ obtenue en (1),
 considérer un préfixe\footnote{\label{prefix-note}On signale à toutes
@@ -599,50 +605,50 @@ considérer un préfixe\footnote{\label{prefix-note}On signale à toutes
   de $t_i$.} d'une telle expression, et appliquer la question (3) et
 l'hypothèse de récurrence.
 
-(5) Déduire des questions (3) et (4) que si $u \in L(G,T)$ et si $v$
+(5) Déduire des questions (3) et (4) que si $u \in L(T)$ et si $v$
 est un préfixe de $u$ autre que $u$ lui-même, alors $u \not\in
-L(G,T)$.  En déduire que $u\in L(G,T)$ et $z \in \Sigma^*$, alors $u$
+L(T)$.  En déduire que $u\in L(T)$ et $z \in \Sigma^*$, alors $u$
 est l'\emph{unique} préfixe du mot $w := uz$ qui appartienne
-à $L(G,T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$
-ni ${>}|u|$ n'appartient à $L(G,T)$).
+à $L(T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$
+ni ${>}|u|$ n'appartient à $L(T)$).
 
 (6) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec
-$u_1,\ldots,u_k \in L(G,T)$ alors cette factorisation est unique.
+$u_1,\ldots,u_k \in L(T)$ alors cette factorisation est unique.
 (Comment peut-on caractériser $u_1$ comme préfixe de $w$ ?)  Montrer
 de même la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots
-u'_\ell$ (on pourra noter que $bz\not\in L(G,T)$ quel que
+u'_\ell$ (on pourra noter que $bz\not\in L(T)$ quel que
 soit $z\in\Sigma^*$).
 
 (7) En déduire que la grammaire $G$ est inambiguë.
 
 \begin{corrige}
-(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(G,T)$.
-  Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(G)$.
+(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(T)$.
+  Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(S)$.
 
 \smallbreak
 
 (1) En bref : il s'agit simplement d'une reformulation des règles de
   la grammaire.  En plus détaillé : si on considère un arbre d'analyse
-  d'un mot $w$ de $L(G)$, soit il est la dérivation triviale du mot
+  d'un mot $w$ de $L(S)$, soit il est la dérivation triviale du mot
   vide, soit sa racine a deux fils étiquetés $T$ et $S$, l'un dont
-  descend un arbre d'analyse d'un mot $u_1$ de $L(G,T)$ et l'autre
-  dont descend un arbre d'analyse d'un autre mot $w'$ de $L(G)$, avec
+  descend un arbre d'analyse d'un mot $u_1$ de $L(T)$ et l'autre
+  dont descend un arbre d'analyse d'un autre mot $w'$ de $L(S)$, avec
   $w = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot
   vide, on voit que $w = u_1 u_2 \cdots u_k$ pour des mots $u_i \in
-  L(G,T)$ ; et réciproquement, tout mot de cette forme a un arbre
+  L(T)$ ; et réciproquement, tout mot de cette forme a un arbre
   d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse
   des $u_i$ (en les associant deux par deux par la droite).  Le cas
-  d'un mot $u$ de $L(G,T)$ est plus simple : son arbre d'analyse donne
+  d'un mot $u$ de $L(T)$ est plus simple : son arbre d'analyse donne
   directement une écriture sous la forme $awbw'c$ avec $w,w'$ les mots
   analysés par les arbres qui descendent des deux fils étiquetés $S$
   de la racine (étiquetée $T$).
 
 \smallbreak
 
-(2) La description faite en (1) signifie notamment que $L(G) =
-L(G,T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
+(2) La description faite en (1) signifie notamment que $L(S) =
+L(T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
 \rightarrow TS \,|\, \varepsilon$ peut s'interpréter comme $S
-\rightarrow T{*}$.)  En particulier, on a $L(G,T) \subseteq L(G)$.
+\rightarrow T{*}$.)  En particulier, on a $L(T) \subseteq L(S)$.
 
 \smallbreak
 
@@ -651,14 +657,14 @@ L(G,T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
 préservée par toute dérivation immédiate pour $G$ puisqu'elle est
 préservée en remplaçant $S$ par $TS$ ou par le mot vide et en
 remplaçant $T$ par $aSbSc$.  Elle est donc vérifiée pour tout mot de
-$L(G)$ (et en particulier, pour tout mot de $L(G,T)$).
+$L(S)$ (et en particulier, pour tout mot de $L(T)$).
 
 \smallbreak
 
 (4) On procède par récurrence sur $|u|$, ce qui permet de supposer la
 propriété déjà connue pour tout préfixe $v$ d'un mot de longueur
 strictement plus courte que $u$.  Si $v$ est un préfixe d'un mot $u
-\in L(G,T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b
+\in L(T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b
 u'_1\cdots u'_{\ell} c$, et si $0<|v|<|u|$, on a soit $v = a u_1
 \cdots u_{i-1} y$ où $y \neq \varepsilon$ est un préfixe de $u_i$,
 soit $v = a u_1\cdots u_k b u'_1\cdots u'_{i-1} y$ où $y \neq
@@ -674,44 +680,44 @@ récurrence.
 
 \smallbreak
 
-(5) Si $u \in L(G,T)$ et si $v$ est un préfixe de $u$ autre que $u$
+(5) Si $u \in L(T)$ et si $v$ est un préfixe de $u$ autre que $u$
 lui-même, alors soit $v = \varepsilon$, qui n'appartient pas à
-$L(G,T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel
-cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(G,T)$
-d'après (3).  Dans tous les cas, $v\not\in L(G,T)$.
+$L(T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel
+cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(T)$
+d'après (3).  Dans tous les cas, $v\not\in L(T)$.
 
-Si maintenant $u\in L(G,T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$
+Si maintenant $u\in L(T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$
 est soit un préfixe de $u$ soit de la forme $uz'$ avec $z'$ un préfixe
 non vide de $z$ (cf. la note \ref{prefix-note}).  Un préfixe de $w$ de
-longueur ${<}|u|$ n'appartient pas à $L(G,T)$ d'après le paragraphe
+longueur ${<}|u|$ n'appartient pas à $L(T)$ d'après le paragraphe
 précédent, et un mot de la forme $uz'$ ne peut pas y appartenir non
 plus car c'est alors $u$ lui-même qui serait un préfixe strict de $uz'
-\in L(G,T)$ appartenant à $L(G,T)$, ce qui contredit de nouveau le
+\in L(T)$ appartenant à $L(T)$, ce qui contredit de nouveau le
 paragraphe précédent.
 
 \smallbreak
 
 (6) D'après la question précédente, on peut définir $u_1$ comme
-l'unique préfixe de $w$ qui appartient à $L(G,T)$ (tout préfixe
+l'unique préfixe de $w$ qui appartient à $L(T)$ (tout préfixe
 strictement plus court ou strictement plus long n'appartient pas à
-$L(G,T)$).  Une fois que $u_1$ est défini, en appliquant le même
+$L(T)$).  Une fois que $u_1$ est défini, en appliquant le même
 raisonnement au suffixe correspondant $u_2\cdots u_k$, on voit que
 $u_2$ est défini de façon unique.  En procédant ainsi (par récurrence
 sur $k$ si on veut), les $u_i$ sont définis de façon unique.
 
 Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ :
-on a une factorisation en mots de $L(G,T)\cup\{b\}$ et à chaque fois
+on a une factorisation en mots de $L(T)\cup\{b\}$ et à chaque fois
 le premier facteur est défini comme le seul préfixe possible
-appartenant à $L(G,T)\cup\{b\}$.  (On utilise le fait que $bz\not\in
-L(G,T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a
-pas de préfixe dans $L(G,T)$.)
+appartenant à $L(T)\cup\{b\}$.  (On utilise le fait que $bz\not\in
+L(T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a
+pas de préfixe dans $L(T)$.)
 
 \smallbreak
 
 (7) En reprenant l'analyse du (1), il s'agit de montrer que la
-factorisation $u_1\cdots u_k$ d'un mot de $L(G)$ est unique et que la
+factorisation $u_1\cdots u_k$ d'un mot de $L(S)$ est unique et que la
 factorisation $a u_1\cdots u_k b u'_1\cdots u'_\ell c$ d'un mot
-de $L(G,T)$ l'est aussi.  La première partie est exactement une
+de $L(T)$ l'est aussi.  La première partie est exactement une
 conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
 $a$ initial et le $c$ final.
 \end{corrige}