1 files changed, 84 insertions, 3 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex
index 0a77b4e..2d09bc0 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -52,6 +52,11 @@
 \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
 {{\hbox{}\nobreak\hfill\checkmark}%
 \ifcorrige\relax\else\egroup\fi\par}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\relax\else\egroup\fi\par}
 %
 %
 % NOTE: compile dot files with
@@ -110,7 +115,7 @@ Durée : 1h30
 Barème \emph{indicatif} : 8 points par exercices
 
 \ifcorrige
-Ce corrigé comporte 10 pages (page de garde incluse)
+%Ce corrigé comporte 10 pages (page de garde incluse)
 \else
 Cet énoncé comporte 4 pages (page de garde incluse)
 \fi
@@ -426,6 +431,33 @@ pouvait utiliser directement ce raisonnement pour produire
 l'expression.)
 \end{corrige}
 
+\begin{commentaire}
+(0) De nombreuses copies parlent d'« automate déterministe à
+    transitions spontanées ».  Cette notion n'existe tout simplement
+  pas et n'a pas de sens.
+
+(1b) De nombreuses erreurs dans la manipulation des automates, qui
+  auraient pu être attrapées par l'utilisation ce ces mots-tests ne
+  l'ont pas été, et c'est dommage (ces erreurs ont été comptées plus
+  sévèrement).
+
+(3) La consigne sur la présentation de l'automate a été presque
+  universellement ignorée (pourquoi ?).
+
+(5) De nombreuses copies essaient de construire un automate
+  reconnaissant $\overline{L}$ autrement qu'en échangeant états finaux
+  et non-finaux dans un automate \underline{déterministe complet}.
+
+(6) Beaucoup de gens croient à tort que la négation de « contenir
+    unique $a$ ou bien contenir un unique $b$ » est « être le mot vide
+    ou bien contenir au moins deux $a$ ou bien au moins deux $b$ » :
+  le mot $aab$ de la question (1b) aurait dû permettre d'éviter cette
+  erreur.  À l'inverse, certains croient que cette négation est « être
+    le mot vide ou bien contenir au moins deux $a$ \emph{et} au moins
+    deux $b$ » : le mot $aa$ aurait dû permettre d'éviter cette
+  erreur.
+\end{commentaire}
+
 
 %
 %
@@ -542,7 +574,7 @@ ne termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de
 $A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
 sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
 
-Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
+\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur
 $x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
 $x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
 courant et le contenu du ruban à chaque étape), du début à l'arrêt.
@@ -559,6 +591,13 @@ algorithmiquement si $S$ termine sur $x$, ce qui contredit
 l'indécidabilité du problème de l'arrêt.
 \end{corrige}
 
+\begin{commentaire}
+Cet exercice a été très peu traité, ce qui est dommage car la
+question (1) consistait essentiellement à dire « oui : on a vu dans le
+  cours tous les algorithmes nécessaires ».
+\end{commentaire}
+
+
 
 %
 %
@@ -664,7 +703,22 @@ L(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(S)$ (et en particulier, pour tout mot de $L(T)$).
+$L(S)$ (et en particulier, pour tout mot de $L(T)$), ce qu'il fallait
+démontrer.
+
+\textit{Autre possibilité :} il suffit de montrer $|w|_a = |w|_b =
+|w|_c$ pour tout mot $w\in L(S)$ (puisque $L(T) \subseteq L(S)$) : on
+va procéder par récurrence sur la longueur $|w|$.  D'après (1), on
+peut écrire $w = u_1\cdots u_k$ avec $u_i\in L(T)$ : si $k>1$, alors
+chaque $u_i$ est de longueur strictement plus petite, donc l'hypothèse
+de récurrence assure que la propriété est vraie pour eux, donc elle
+l'est pour $w$ car $|w|_x = \sum_{i=1}^k |u_i|_x$ pour chaque
+$x\in\{a,b,c\}$.  Reste le cas $k=1$, c'est-à-dire, $w\in L(T)$ : mais
+on a alors (toujours d'après (1)) $w = avbv'c$ avec $v,v'\in L(S)$ qui
+sont de longueur strictement plus petite que $w$, donc l'hypothèse de
+récurrence assure que la propriétée st vraie pour $v$ et $v'$, et
+comme $|w|_x = 1 + |v|_x + |v'|_x$ pour chaque $x\in\{a,b,c\}$, on a
+la propriété voulue pour $w$.
 
 \smallbreak
 
@@ -729,6 +783,33 @@ conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
 $a$ initial et le $c$ final.
 \end{corrige}
 
+\begin{commentaire}
+(3) Les deux démonstrations proposées dans le corrigé ci-dessus ont
+  effectivement été trouvées (rédigées de façon généralement
+  incorrecte, mais on n'a pas sanctionné trop sévèrement les
+  imprécisions).
+
+(4) Malgré la note \ref{prefix-note} en bas de page, la plupart des
+  copies pensent qu'un préfixe de $au_1\cdots u_k bu'_1\cdots u'\ell
+  c$ est de la forme $au_1\cdots u_i$ ou bien $au_1\cdots u_k
+  bu'_1\cdots u'_i$, et oublient que le dernier facteur peut lui-même
+  être coupé (c'était bien ça le sens de la note).  Cette erreur n'a
+  pas été sanctionnée trop sévèrement.
+
+(5) Cette question comportait deux sous-questions.  La première (si
+  $u\in L(T)$ et $v$ préfixe de $u$ différent de $u$ alors $v\not\in
+  L(T)$) a été correctement traitée à ceci près que beaucoup oublient
+  le cas $v=\varepsilon$ qui n'était pas couvert par la question (4) ;
+  la seconde (concernant les préfixes de $uz$) a été souvent oubliée,
+  et certains oublient de considérer le cas d'un préfixe de
+  longueur $>|u|$.
+
+En outre, pour l'application à la question (6), certains parlent de
+« unique préfixe de $w$ » pour « unique préfixe de $w$ qui appartienne
+  à $L(T)$ ».  Il n'est pas clair s'il s'agit d'une confusion ou d'un
+oubli.
+\end{commentaire}
+
 
 
 %