From 1534fd4cf5530801af78a819a563912bee16c70b Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 15 Jun 2021 23:27:26 +0200
Subject: Re-read test and fix some problems.

---
 controle-20210618.tex | 43 +++++++++++++++++++++----------------------
 1 file changed, 21 insertions(+), 22 deletions(-)

(limited to 'controle-20210618.tex')

diff --git a/controle-20210618.tex b/controle-20210618.tex
index 4993f1d..5e9b114 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -140,9 +140,9 @@ de justifier les réponses.
   automates successifs qu'on calculera.}  (Par exemple, pour un
 automate censé reconnaître le langage $L$, on vérifiera qu'il accepte
 bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux
-qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes pouvant
-être détectées par cette vérification seront plus lourdement
-sanctionnées.
+qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes qui
+auraient dû être détectées par cette vérification pourront être plus
+lourdement sanctionnées.
 
 (1) Traiter l'une \emph{ou} l'autre des questions suivantes :
 (i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
@@ -160,7 +160,8 @@ $\mathscr{A}_2$ l'automate en question.  On rappelle qu'on attend ici
 un automate fini \emph{déterministe complet}.
 
 (3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
-$\mathscr{A}_3$ l'automate canonique du langage $L$ ainsi obtenu.
+$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
+langage $L$).
 
 (4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet
 $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$
@@ -181,11 +182,10 @@ vérifient pas $r$).
 On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma =
 \{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles
 \[
-S \rightarrow \varepsilon \;|\; aSbc \;|\; abSc
+S \rightarrow abc \;|\; aSbc \;|\; abSc
 \]
-On appellera « $0$ » la règle $S \rightarrow \varepsilon$, et
-« $1$ » la règle $S \rightarrow aSbc$, et enfin « $2$ » la règle $S
-\rightarrow abSc$.
+On appellera « $0$ » la règle $S \rightarrow abc$, et « $1$ » la règle
+$S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$.
 
 (1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$
 selon cette grammaire $G$.  (On pourra d'abord lire les questions
@@ -197,22 +197,21 @@ On va maintenant montrer que $G$ est inambiguë.
 par $G$ a nécessairement $a$ pour préfixe (i.e., commence par la
 lettre $a$).
 
-(3) Montrer que tout mot de $L$ dérivé en commençant
+(3) Montrer que tout mot de $L$ dérivé en démarrant
 par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
-  selon $G$ de la forme $S \Rightarrow aSc \mathrel{\Rightarrow^*} w$
+  selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$
   où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de
-  dérivations.  Ou, ce qui revient au même (on pourra tenir ce point
-  pour acquis) : tout mot $w$ possédant un arbre d'analyse dont la
-  racine a trois fils étiquetés $a,S,b$ dans cet ordre.} la règle $1$
-a nécessairement $aa$ ou $ac$ comme préfixe.  Montrer de même que tout
-mot de $L$ dérivé en commençant par la règle $2$ a nécessairement $ab$
-comme préfixe.
-
-(4) En déduire comment, d'après la longueur d'un mot $w$ de $L$ et ses
-deux premières lettres, on peut savoir par quelle règle commence
-nécessairement une dérivation de $w$ selon $G$ (ou, ce qui revient au
-même, quels sont les fils de la racine dans tout arbre d'analyse
-de $w$).
+  dérivations immédiates.  Ou, ce qui revient au même (et on pourra
+  tenir ce point pour acquis) : tout mot $w$ possédant un arbre
+  d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet
+  ordre.} la règle $1$ a nécessairement $aa$ comme préfixe.  Montrer
+de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a
+nécessairement $aba$ comme préfixe.
+
+(4) En déduire comment, d'après les premières lettres d'un mot $w$
+de $L$, on peut savoir par quelle règle démarre nécessairement une
+dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont
+les fils de la racine dans tout arbre d'analyse de $w$).
 
 (5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$,
 expliquer comment trouver tous les arbres d'analyse du mot $awbc$
-- 
cgit v1.2.3

