diff options
Diffstat (limited to 'controle-20170207.tex')
-rw-r--r-- | controle-20170207.tex | 87 |
1 files changed, 84 insertions, 3 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index 0a77b4e..2d09bc0 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -52,6 +52,11 @@ \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\relax\else\egroup\fi\par} % % % NOTE: compile dot files with @@ -110,7 +115,7 @@ Durée : 1h30 Barème \emph{indicatif} : 8 points par exercices \ifcorrige -Ce corrigé comporte 10 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 @@ -426,6 +431,33 @@ pouvait utiliser directement ce raisonnement pour produire l'expression.) \end{corrige} +\begin{commentaire} +(0) De nombreuses copies parlent d'« automate déterministe à + transitions spontanées ». Cette notion n'existe tout simplement + pas et n'a pas de sens. + +(1b) De nombreuses erreurs dans la manipulation des automates, qui + auraient pu être attrapées par l'utilisation ce ces mots-tests ne + l'ont pas été, et c'est dommage (ces erreurs ont été comptées plus + sévèrement). + +(3) La consigne sur la présentation de l'automate a été presque + universellement ignorée (pourquoi ?). + +(5) De nombreuses copies essaient de construire un automate + reconnaissant $\overline{L}$ autrement qu'en échangeant états finaux + et non-finaux dans un automate \underline{déterministe complet}. + +(6) Beaucoup de gens croient à tort que la négation de « contenir + unique $a$ ou bien contenir un unique $b$ » est « être le mot vide + ou bien contenir au moins deux $a$ ou bien au moins deux $b$ » : + le mot $aab$ de la question (1b) aurait dû permettre d'éviter cette + erreur. À l'inverse, certains croient que cette négation est « être + le mot vide ou bien contenir au moins deux $a$ \emph{et} au moins + deux $b$ » : le mot $aa$ aurait dû permettre d'éviter cette + erreur. +\end{commentaire} + % % @@ -542,7 +574,7 @@ ne termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de $A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt. -Variante de la même idée : on appelle « trace d'exécution » de $S$ sur +\textit{Variante de la même idée :} on appelle « trace d'exécution » de $S$ sur $x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur $x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état courant et le contenu du ruban à chaque étape), du début à l'arrêt. @@ -559,6 +591,13 @@ algorithmiquement si $S$ termine sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt. \end{corrige} +\begin{commentaire} +Cet exercice a été très peu traité, ce qui est dommage car la +question (1) consistait essentiellement à dire « oui : on a vu dans le + cours tous les algorithmes nécessaires ». +\end{commentaire} + + % % @@ -664,7 +703,22 @@ L(T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S préservée par toute dérivation immédiate pour $G$ puisqu'elle est préservée en remplaçant $S$ par $TS$ ou par le mot vide et en remplaçant $T$ par $aSbSc$. Elle est donc vérifiée pour tout mot de -$L(S)$ (et en particulier, pour tout mot de $L(T)$). +$L(S)$ (et en particulier, pour tout mot de $L(T)$), ce qu'il fallait +démontrer. + +\textit{Autre possibilité :} il suffit de montrer $|w|_a = |w|_b = +|w|_c$ pour tout mot $w\in L(S)$ (puisque $L(T) \subseteq L(S)$) : on +va procéder par récurrence sur la longueur $|w|$. D'après (1), on +peut écrire $w = u_1\cdots u_k$ avec $u_i\in L(T)$ : si $k>1$, alors +chaque $u_i$ est de longueur strictement plus petite, donc l'hypothèse +de récurrence assure que la propriété est vraie pour eux, donc elle +l'est pour $w$ car $|w|_x = \sum_{i=1}^k |u_i|_x$ pour chaque +$x\in\{a,b,c\}$. Reste le cas $k=1$, c'est-à-dire, $w\in L(T)$ : mais +on a alors (toujours d'après (1)) $w = avbv'c$ avec $v,v'\in L(S)$ qui +sont de longueur strictement plus petite que $w$, donc l'hypothèse de +récurrence assure que la propriétée st vraie pour $v$ et $v'$, et +comme $|w|_x = 1 + |v|_x + |v'|_x$ pour chaque $x\in\{a,b,c\}$, on a +la propriété voulue pour $w$. \smallbreak @@ -729,6 +783,33 @@ conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le $a$ initial et le $c$ final. \end{corrige} +\begin{commentaire} +(3) Les deux démonstrations proposées dans le corrigé ci-dessus ont + effectivement été trouvées (rédigées de façon généralement + incorrecte, mais on n'a pas sanctionné trop sévèrement les + imprécisions). + +(4) Malgré la note \ref{prefix-note} en bas de page, la plupart des + copies pensent qu'un préfixe de $au_1\cdots u_k bu'_1\cdots u'\ell + c$ est de la forme $au_1\cdots u_i$ ou bien $au_1\cdots u_k + bu'_1\cdots u'_i$, et oublient que le dernier facteur peut lui-même + être coupé (c'était bien ça le sens de la note). Cette erreur n'a + pas été sanctionnée trop sévèrement. + +(5) Cette question comportait deux sous-questions. La première (si + $u\in L(T)$ et $v$ préfixe de $u$ différent de $u$ alors $v\not\in + L(T)$) a été correctement traitée à ceci près que beaucoup oublient + le cas $v=\varepsilon$ qui n'était pas couvert par la question (4) ; + la seconde (concernant les préfixes de $uz$) a été souvent oubliée, + et certains oublient de considérer le cas d'un préfixe de + longueur $>|u|$. + +En outre, pour l'application à la question (6), certains parlent de +« unique préfixe de $w$ » pour « unique préfixe de $w$ qui appartienne + à $L(T)$ ». Il n'est pas clair s'il s'agit d'une confusion ou d'un +oubli. +\end{commentaire} + % |