diff options
author | David A. Madore <david+git@madore.org> | 2017-03-03 19:54:56 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2017-03-03 19:54:56 +0100 |
commit | c072689feb858766cda5630ac790a2a3df5272fb (patch) | |
tree | 9bc99d97b243d373e793686692fd916187c4cc26 | |
parent | 582b317811b947b1f715ca411263f2b9c14a537c (diff) | |
download | inf105-c072689feb858766cda5630ac790a2a3df5272fb.tar.gz inf105-c072689feb858766cda5630ac790a2a3df5272fb.tar.bz2 inf105-c072689feb858766cda5630ac790a2a3df5272fb.zip |
Various additional comments.
-rw-r--r-- | controle-20170207.tex | 22 |
1 files changed, 19 insertions, 3 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index 2d09bc0..24c4d27 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -442,7 +442,10 @@ l'expression.) sévèrement). (3) La consigne sur la présentation de l'automate a été presque - universellement ignorée (pourquoi ?). + universellement ignorée (pourquoi ?). Plus grave, certains ont + oublié de fournir un automate déterministe \emph{complet} (pourtant, + l'algorithme de déterminisation fournit assez naturellement un + automate complet). (5) De nombreuses copies essaient de construire un automate reconnaissant $\overline{L}$ autrement qu'en échangeant états finaux @@ -455,7 +458,10 @@ l'expression.) 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. + erreur. Enfin, beaucoup de copies utilisent une description + tellement vague qu'il est impossible de savoir ce qu'elle veut dire + (par exemple « les mots pour lesquels le nombre d'occurrence des + lettres qui s'y trouvent est supérieur ou égal à $2$ »). \end{commentaire} @@ -770,7 +776,7 @@ Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ : on a une factorisation en mots de $L(T)\cup\{b\}$ et à chaque fois le premier facteur est défini comme le seul préfixe possible appartenant à $L(T)\cup\{b\}$. (On utilise le fait que $bz\not\in -L(T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a +L(T)$, qui découle du (1), pour voir que $bu'_1\cdots u'_\ell$ n'a pas de préfixe dans $L(T)$.) \smallbreak @@ -789,6 +795,13 @@ $a$ initial et le $c$ final. incorrecte, mais on n'a pas sanctionné trop sévèrement les imprécisions). +Un nombre étonnant de copies commettent l'erreur de croire que pour +montrer quelque chose pour tout $w$ de $L(S)$ ou bien $L(T)$, +lorsqu'on a $L(T) \subseteq L(S)$, il suffit de le montrer pour $w\in +L(T)$ : c'est au contraire $w \in L(S)$ qu'on peut supposer. (Il est +vrai que comme $L(S) = L(T)^*$, il n'est pas non plus difficile de +passer de $L(T)$ à $L(S)$, mais il faut au moins dire un mot.) + (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 @@ -808,6 +821,9 @@ 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. + +(6) La seconde sous-question (celle portant sur $u_1\cdots u_k +bu'_1\cdots u'\ell$) n'a quasiment pas été traitée. \end{commentaire} |