From 1e7e4ee5c5007d4a5113fb0f942fe7649cac7772 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 29 Jan 2018 21:00:31 +0100
Subject: Make corrections suggested by Olivier.

---
 controle-20180206.tex | 40 +++++++++++++++++++++-------------------
 1 file changed, 21 insertions(+), 19 deletions(-)

(limited to 'controle-20180206.tex')

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
-- 
cgit v1.2.3

