summaryrefslogtreecommitdiffstats
path: root/controle-20180206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'controle-20180206.tex')
-rw-r--r--controle-20180206.tex100
1 files changed, 94 insertions, 6 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex
index f9a66b9..c4aac4c 100644
--- a/controle-20180206.tex
+++ b/controle-20180206.tex
@@ -24,9 +24,9 @@
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
-\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
-\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\DeclareUnicodeCharacter{00A0}{~}
@@ -110,7 +110,7 @@ Durée : 1h30
Barème \emph{indicatif} : 7 points par exercice
\ifcorrige
-Ce corrigé comporte 9 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
@@ -141,6 +141,11 @@ donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \;
$(a|b){*}\,(aa|bb)\,(a|b){*}$.
\end{corrige}
+\begin{commentaire}
+La principale erreur sur cette question a été d'écrire
+$(a|b){*}\,aa|bb\,(a|b){*}$, en oubliant la priorité des opérations.
+\end{commentaire}
+
(2) Indépendamment de la question (1), expliquer brièvement pourquoi
l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ :
@@ -206,6 +211,15 @@ déterminisation conduit à l'automate $\mathscr{A}_3$ suivant :
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}
+\begin{commentaire}
+Un nombre étonnant de copies aboutissent à des variations du même
+résultat erroné sur cette question, à savoir faire pointer la
+transition étiquetée $b$ partant de l'état $SA$ vers l'état $S$ plutôt
+que vers $SB$ (et symétriquement, la transition étiquetée $a$ partant
+de l'état $SB$ vers l'état $S$ plutôt que vers $SA$). Il serait
+intéressant de comprendre d'où vient cette erreur.
+\end{commentaire}
+
(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu
en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique)
résultant.
@@ -315,6 +329,19 @@ $\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon
et ainsi de suite).
\end{corrige}
+\begin{commentaire}
+Cette question a donné lieu à très peu de réponses correctes.
+Certains trichent et devinent l'expression rationnelle à trouver
+(généralement en oubliant le mot vide et/ou les mots de longueur $1$)
+au lieu d'appliquer l'algorithme d'élimination des états. Ceux qui
+ont l'honnêteté de l'appliquer oublient souvent de se ramener à un
+automate ayant un unique état initial (c'était déjà le cas) et un
+unique état final (ce n'était pas le cas). Le choix de l'ordre
+d'élimination des états est rarement réfléchi (notamment, même parmi
+ceux qui appliquent correctement l'algorithme, beaucoup ne se rendent
+pas compte qu'éliminer le puits peut se faire immédiatement).
+\end{commentaire}
+
%
@@ -470,11 +497,27 @@ s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$
\begin{corrige}
(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que
- $@$ est prioritaire sur $\#$.\quad (b) L'arbre d'analyse (a) de la
- question (1) montre que $\#$ s'associe à gauche.\quad (c) L'arbre
- d'analyse (d) de la question (1) montre que $@$ s'associe à droite.
+ l'opération $@$ est prioritaire sur $\#$ (elle est toujours plus
+ profonde dans l'arbre, c'est-à-dire appliquée en premier aux
+ opérandes).\quad (b) L'arbre d'analyse (a) de la question (1) montre
+ que $\#$ s'associe à gauche (le $\#$ entre les deux opérandes gauche
+ est plus profond, c'est-à-dire appliqué en premier).\quad
+ (c) Symétriquement, l'arbre d'analyse (d) de la question (1) montre
+ que $@$ s'associe à droite.
\end{corrige}
+\begin{commentaire}
+Beaucoup de copies affirment, par exemple, que l'opération $\#$ est
+prioritaire sur $@$ parce que $\#$ est plus haut dans l'arbre ou se
+rencontre en premier dans l'analyse : en réalité, l'opération
+prioritaire est celle qui se calcule en premier, c'est-à-dire de la
+façon la plus \emph{profonde} (on a précisé que $\boxtimes$ est
+prioritaire sur $\boxplus$ lorsque « $u\boxtimes v\boxplus w$ » se
+comprend comme « $(u\boxtimes v)\boxplus w$ » : c'est bien $\boxtimes$
+qui est imbriqué le plus profondément dans les parenthèses, et la
+comparaison avec l'arbre (e) aurait dû lever tout doute).
+\end{commentaire}
+
\smallskip
(La question (3) est indépendante de (1) et (2). Par ailleurs, on
@@ -539,6 +582,27 @@ rationnel ?\quad (c) Le langage $L$ est-il rationnel ?
pas rationnel.
\end{corrige}
+\begin{commentaire}
+Dans la question (a), beaucoup de copies montrent correctement une
+seule implication (que tout mot de la forme « ${(}^i\, x\, {)}^j$ »
+appartient à $L\cap M$, ou bien que tout mot de $L\cap M$ a cette
+forme), mais oublient qu'il est essentiel de traiter les deux.
+
+Pour ce qui est de la question (b), certains se sont rendu la vie
+inutilement compliquée en prenant certes un mot de la forme $a^i x
+b^i$ mais en ne choisissant pas $i=k$ (ou au moins $i\geq k$), ce qui
+oblige à des discussions de cas qui n'avaient pas lieu d'être. On
+rappelle donc que lorsqu'on applique le lemme de pompage, on choisit
+le mot $t$ auquel on va appliquer la propriété (la seule contrainte
+étant de devoir prendre $|t|\geq k$).
+
+La question (c) a été étonnamment peu traitée eu égard à sa
+simplicité. Beaucoup ne montrent pas, ne pensent pas à montrer, ou ne
+savent pas montrer, que $M$ est rationnel (ce qui devrait pourtant
+sauter aux yeux...). Certains arrivent à des conclusions fantaisistes
+comme « $L$ est rationnel ».
+\end{commentaire}
+
%
%
@@ -629,6 +693,18 @@ l'entrée $x$, on ne termine pas non plus). Ceci montre que $L$ est
semi-décidable. Le même raisonnement s'applique pour $M$.
\end{corrige}
+\begin{commentaire}
+Certains pensent pouvoir déduire la semi-décidabilité de $L$ et $M$ de
+celle du problème de l'arrêt : la situation est effectivement proche,
+mais à moins d'une explication précise sur le fait qu'on peut calculer
+la valeur $\varphi_e(x)$ une fois qu'on s'est assuré qu'elle est bien
+définie, ce n'est pas légitime ; d'ailleurs, la semi-décidabilité du
+problème de l'arrêt est quelque chose de tellement simple (une fois
+acquise l'existence d'une machine universelle) qu'on ne devrait jamais
+l'invoquer, car il sera essentiellement toujours plus simple de dire
+« il suffit de lancer l'exécution du programme... ».
+\end{commentaire}
+
(5) En imitant la démonstration du théorème de Turing sur
l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun
algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours
@@ -654,6 +730,12 @@ $2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une
contradiction.
\end{corrige}
+\begin{commentaire}
+Il n'y a eu à peu près qu'une réponse correcte à cette question.
+Quelques points partiels ont été attribués à ceux qui tentaient au
+moins de dire quelque chose et qui avaient un semblant d'idée.
+\end{commentaire}
+
(6) Conclure.
\begin{corrige}
@@ -664,6 +746,12 @@ disjoints et semi-décidables. On a donc bien montré l'existence de
langages semi-décidables disjoints et calculablement inséparables.
\end{corrige}
+\begin{commentaire}
+Bien qu'elle fût essentiellement triviale (il suffisait de redire les
+résultats des questions précédentes), cette question n'a quasiment pas
+été traitée.
+\end{commentaire}
+
\smallskip
{\footnotesize (Remarque culturelle :\quad La construction de langages