diff options
| -rw-r--r-- | controle-20180206.tex | 37 |
1 files changed, 34 insertions, 3 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex index 76d150c..c4aadc5 100644 --- a/controle-20180206.tex +++ b/controle-20180206.tex @@ -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,9 +497,13 @@ 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} \smallskip |