diff options
Diffstat (limited to 'controle-20180206.tex')
| -rw-r--r-- | controle-20180206.tex | 100 |
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 |