From a50511048da51816d3683ca79371fa79731b5226 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 19 Oct 2017 14:46:15 +0200
Subject: Comments on exam.  [Forgotten commit, changes made on 2017-05-28.]

---
 controle-20170330.tex | 74 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 71 insertions(+), 3 deletions(-)

diff --git a/controle-20170330.tex b/controle-20170330.tex
index 443d25e..304df9e 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -280,6 +280,25 @@ rationnelle $(a|b)^{*}$ (nous notons ici $|$ pour la disjonction, qu'on
 peut aussi noter $+$).
 \end{corrige}
 
+\begin{commentaire}
+Cet exercice a été noté sur $8$ (dans une note finale sur $21$
+considérée comme sur $20$).
+
+La question (4) a fait l'objet de beaucoup d'erreurs : beaucoup de
+copies affirment qu'on « ne peut pas » minimiser l'automate, ou que
+l'algorithme de Moore « échoue » ou encore qu'il « termine
+immédiatement » et que l'automate est déjà minimal (ce que, de toute
+évidence, il n'est pas).  À cause de cela, la question (5) a été
+rendue beaucoup plus compliquée (ce qui n'était pas dans l'intention
+de l'auteur du sujet).
+
+De façon plus générale, il est dommage qu'une expression aussi simple
+que $a^{*}(ba^{*})^{*}$ ne soit pas immédiatement déchiffrée comme
+dénotant le langage $\Sigma^*$ de tous les mots sur $\Sigma =
+\{a,b\}$, ce qui aurait permis de répondre immédiatement à la
+question (5), ou au moins de vérifier cette réponse.
+\end{commentaire}
+
 
 %
 %
@@ -340,9 +359,11 @@ propriétés « rationnel », « algébrique », « décidable »,
 question.
 
 \begin{corrige}
-(1) Le mot $babbabbab$ appartient à $L$ (prendre $w=babb$ et $n=1$)
-  mais pas à $L'$ ; le mot $babbababb$ appartient à $L'$ (idem) mais
-  pas à $L$.
+(1) Le mot $abba$ appartient à $L$ (prendre $w=ab$ et $n=0$) mais pas
+  à $L'$ ; le mot $abab$ appartient à $L'$ (idem) mais pas à $L$.
+  Autre exemple : le mot $babbabbab$ appartient à $L$ (prendre
+  $w=babb$ et $n=1$) mais pas à $L'$ ; le mot $babbababb$ appartient à
+  $L'$ (idem) mais pas à $L$.
 
 \smallbreak
 
@@ -452,6 +473,40 @@ semi-décidable ?&oui&oui&oui&oui&oui\\
 \vskip-\baselineskip\vskip-1ex\strut
 \end{corrige}
 
+\begin{commentaire}
+Cet exercice a été noté sur $9$ (dans une note finale sur $21$
+considérée comme sur $20$).
+
+La question (2) révèle une grande incompréhension de ce qu'est une
+grammaire hors-contexte : certains proposent par exemple des règles du
+genre $C \rightarrow A^{\mathsf{R}}$ (on ne sait même pas ce que ça
+pourrait vouloir dire).
+
+Dans les questions (3) à (5) (qui étaient basées sur le fait que $M =
+L\cap N$ et $M' = L'\cap N$, cf. corrigé), beaucoup ont observé que $M
+\subseteq L$ et/ou que $M' \subseteq L'$ (ce qui est correct) et ont
+cru pouvoir en déduire que $L'$ n'est pas algébrique ou que $M$ l'est,
+ou autres conclusions du même genre.  Rappelons donc clairement :
+\emph{un sous-langage d'un langage algébrique n'est pas nécessairement
+  algébrique} (et de même avec « rationnel », ou avec
+« sur-langage ») ; d'ailleurs, étant donné que tous les langages sont
+des sous-langages de $\Sigma^*$, cela rendrait la théorie très peu
+intéressante !
+
+Pour la question (4a), dans l'application du lemme de pompage, très
+peu nombreux sont ceux qui ont compris que quand on utilise ce lemme,
+on \emph{choisit} le mot $x$ dont on va demander une factorisation
+$x=uvw$ (en revanche, on ne choisit pas la factorisation !).
+
+Pour la question (7), il suffisait pour avoir les points de dresser un
+tableau compatible avec les implications « rationnel implique
+algébrique implique décidable implique semi-décidable » (donc ne pas
+affirmer qu'un langage serait, par exemple, algébrique mais non
+décidable) ainsi qu'avec les résultats explicitement affirmés dans les
+questions précédentes.  Malgré cela, \emph{une seule copie} a
+correctement dressé un tel tableau !
+\end{commentaire}
+
 
 %
 %
@@ -554,6 +609,19 @@ algorithmiquement le problème de l'arrêt, ce qui est une
 contradiction.  C'est donc que $H'$ n'était, en fait, pas décidable.
 \end{corrige}
 
+\begin{commentaire}
+Cet exercice a été noté sur $4$ (dans une note finale sur $21$
+considérée comme sur $20$).
+
+Quelques réponses correctes (ou largement correctes) ont été trouvées.
+La principale erreur commise par ceux qui ont abordé l'exercice sans
+le traiter correctement était de penser que $H' \subseteq H$ avec $H$
+semi-décidable implique $H'$ semi-décidable (l'énoncé signalait
+pourtant explicitement que cette inclusion n'était pas utile !) ;
+cf. les commentaires sur les questions (3) à (5) de l'exercice
+précédent.
+\end{commentaire}
+
 
 
 %
-- 
cgit v1.2.3