More re-reading and discussion with Bertrand.

1 files changed, 16 insertions, 12 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index a3637f6..7d6a2bc 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -93,9 +93,8 @@ très visible dans les copies où commence chaque exercice.
 
 \medbreak
 
-Le sujet étant délibérément trop long pour le temps imparti, il sera
-possible d'obtenir la totalité des points en ne traitant qu'une partie
-des exercices.
+Le sujet étant long pour le temps imparti, il ne sera nécessaire de
+traiter toutes les questions pour obtenir la totalité des points.
 
 \medbreak
 
@@ -108,6 +107,8 @@ L'usage des calculatrices électroniques est interdit.
 
 Durée : 1h30
 
+L'énoncé comporte 4 pages.
+
 \pagebreak
 
 
@@ -150,7 +151,7 @@ rationnelle qui le dénote.  (On pourra préférer traiter la question
 
 (1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
 $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
-(Note : il est conseillé de réutiliser ces mots pour vérifier
+(Note : il est recommandé de réutiliser ces mots pour vérifier
 rapidement les réponses aux questions suivantes et ainsi détecter
 d'éventuelles erreurs lors des transformations des automates.)
 
@@ -172,9 +173,10 @@ langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.
 (6) Décrire brièvement, en français, le langage ce langage
 complémentaire $\overline{L}$.
 
-(7) Donner une expression rationnelle qui reconnaît ce langage
-complémentaire $\overline{L}$.  (Cette question est plus difficile.
-Ne pas hésiter à introduire des notations intermédiaires.)
+(7) (Question bonus, plus longue, à ne traiter qu'en dernier.)  Donner
+une expression rationnelle qui dénote ce langage
+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,
@@ -441,8 +443,8 @@ $w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
 si $L_G = \Sigma^*$.)  Indication : on peut tester tous les mots
 possibles.
 
-(3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui
-fournit en entrée un algorithme $T$ qui décide un langage $L_T
+(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on
+lui fournit en entrée un algorithme $T$ qui décide un langage $L_T
 \subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
 fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
 « faux », et $L_T$ est le langage des mots sur lesquels il répond
@@ -563,7 +565,8 @@ 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)$.
+(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,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
@@ -572,8 +575,9 @@ conséquent, $L(G,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)$.)
 
-(2) Comment décrire $L(G)$ de manière simple en fonction de $L(G,T)$ ?
-Y a-t-il inclusion de l'un dans l'autre ?
+(2) Comment décrire $L(G)$ de en fonction de $L(G,T)$ au moyen des
+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$ de $L(G)$ 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