diff options
| -rw-r--r-- | controle-20170330.tex | 74 |
1 files 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} + % |