summaryrefslogtreecommitdiffstats
path: root/controle-20180206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'controle-20180206.tex')
-rw-r--r--controle-20180206.tex40
1 files changed, 21 insertions, 19 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex
index 4503e0a..8ab48c3 100644
--- a/controle-20180206.tex
+++ b/controle-20180206.tex
@@ -107,7 +107,7 @@ L'usage des appareils électroniques est interdit.
Durée : 1h30
-Barème \emph{indicatif} : 7 points par exercices
+Barème \emph{indicatif} : 7 points par exercice
\ifcorrige
Ce corrigé comporte 8 pages (page de garde incluse)
@@ -215,9 +215,10 @@ On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans
état inaccessible. La première étape de l'algorithme de minimisation
sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et
$SAT,SBT$ de l'autre. Ensuite on sépare $S$ et $SA$ et $SB$ (car le
-premier ne conduit qu'à des états non finaux, le second conduit à des
-états finaux par la transition étiquetée $a$, et le troisième conduit
-à des états finaux par la transition étiquetée $b$). On obtient
+premier ne conduit qu'à des états non finaux, le deuxième conduit à un
+état final par la transition étiquetée $a$, et le troisième conduit à
+un état final par la transition étiquetée $b$). Les étapes suivantes
+ne conduisent pas à d'autres séparations d'états. On obtient
finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut
appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ :
\begin{center}
@@ -334,13 +335,13 @@ V &\rightarrow x \;|\; y \;|\; z\\
\end{aligned}
\]
(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les
-parenthèses servent comme on s'y attend, et $x,y,z$ sont trois choses
+parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes
auxquelles on peut vouloir appliquer ces opérations.)
La grammaire en question est inambiguë (on ne demande pas de le
démontrer).
-(1) Donner les arbres d'analyse des mots suivants :
+(1) Donner les arbres d'analyse (=de dérivation) des mots suivants :
(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$,
(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$,
(e) $(x\mathbin{\#}y)\mathbin{@}z$.
@@ -454,17 +455,18 @@ On obtient les arbres d'analyse suivants :
\end{corrige}
(2) En considérant que $(w)$ a le même effet / la même valeur
-que $w$ : (a) Quelle opération parmi $\#$ et $@$ est
+que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle
prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est
\emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus
w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » et
« $u\boxplus v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».}
-sur l'autre ?\quad (b) L'opération $\#$ s'associe-t-elle\footnote{On dit
- qu'une opération binaire $\boxdot$ \emph{s'associe à gauche} lorsque
- « $u\boxdot v\boxdot w$ » se comprend comme « $(u\boxdot v)\boxdot
- w$ », et \emph{s'associe à droite} lorsque « $u\boxdot v\boxdot w$ »
- se comprend comme « $u\boxdot (v\boxdot w)$ ».} à gauche ou à
-droite ?\quad (c) L'opération $@$ s'associe-t-elle à gauche ou à droite ?
+sur l'autre ? Laquelle ?\quad (b) L'opération $\#$
+s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$
+ \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se
+ comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à
+ droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme
+ « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad
+(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ?
\begin{corrige}
(a) Les arbres d'analyse (b) et (c) de la question (1) montrent que
@@ -487,13 +489,13 @@ exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$
Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$
(cf. le paragraphe précédent). On dira que deux langages $L,M$
disjoints (c'est-à-dire $L\cap M = \varnothing$) sont
-\emph{calculablement séparables} lorsqu'il existe un $E$ décidable tel
-que $L \subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où
-$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le
-cas contraire, on les dit \emph{calculablement inséparables}.
+\emph{calculablement séparables} lorsqu'il existe un langage $E$
+décidable tel que $L \subseteq E$ et $M \subseteq (\mathbb{N}\setminus
+E)$ (où $\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ;
+dans le cas contraire, on les dit \emph{calculablement inséparables}.
(1) Expliquer pourquoi deux langages $L,M$ disjoints sont
-calculablement séparables si et seulement si il existe un algorithme
+calculablement séparables si et seulement s'il existe un algorithme
qui, prenant en entrée un élément $x$ de $\mathbb{N}$ :
\begin{itemize}
\item termine toujours en temps fini,
@@ -527,7 +529,7 @@ que $M$ est disjoint de $E=L$).
On cherche maintenant à montrer qu'il existe deux langages $L,M$
\emph{semi-décidables} disjoints et calculablement inséparables.
-Pour cela, appelle $L$ l'ensemble des couples\footnote{Pour être
+Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être
rigoureux, on a fixé un codage permettant de représenter les
programmes $e$, les entrées $x$ à ces programmes, et les couples
$(e,x)$ comme des éléments de $\mathbb{N}$. Il n'est pas nécessaire