Re-read exam.

1 files changed, 29 insertions, 25 deletions

diff --git a/controle-20220616.tex b/controle-20220616.tex
index 1ecbd0a..b1be47e 100644
--- a/controle-20220616.tex
+++ b/controle-20220616.tex
@@ -84,9 +84,11 @@
 
 \noindent\textbf{Consignes.}
 
-Les exercices sont totalement indépendants.  Ils pourront être traités
-dans un ordre quelconque, mais on demande de faire apparaître de façon
-très visible dans les copies où commence chaque exercice.
+Les exercices sont totalement indépendants (le premier teste
+l'application d'algorithmes vus en cours, le second est de nature plus
+théorique).  Ils pourront être traités dans un ordre quelconque, mais
+on demande de faire apparaître de façon très visible dans les copies
+où commence chaque exercice.
 
 \medbreak
 
@@ -99,12 +101,12 @@ L'usage des appareils électroniques est interdit.
 
 Durée : 1h30
 
-Barème \emph{indicatif} : \textcolor{red}{à remplir}.
+Barème \emph{indicatif} : 10 points par exercice.
 
 \ifcorrige
-Ce corrigé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+Ce corrigé comporte 9 pages (page de garde incluse).
 \else
-Cet énoncé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+Cet énoncé comporte 4 pages (page de garde incluse).
 \fi
 
 \vfill
@@ -249,8 +251,8 @@ suivant :
 
 (4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L'
 := L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$.
-Comme ce langage, et donc cet automate, est simplement obtenu en
-échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
+Comme cette expression, et donc cet automate, sont simplement obtenus
+en échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
 directement l'automate sans passer par les questions intermédiaires.
 
 \begin{corrige}
@@ -408,7 +410,7 @@ un unique état final sans transition qui en parte :
 \draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
 \draw[->] (q2a) -- node[auto]{$b$} (q3a);
 \draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
-\draw[->] (q2a) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) -- node[auto,below]{$\varepsilon$} (qT);
 \draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT);
 \draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
 \draw[->] (q2) -- node[auto,below]{$a$} (q3);
@@ -456,13 +458,14 @@ d'élimination des états).
 
 \exercice
 
-Les parties (A), (B) et (C) de cet exercice sont indépendantes.
+Les parties (A), (B) et (C) de cet exercice sont indépendantes.  On ne
+demande pas de justifications très longues.
 
 \medskip
 
 \textbf{(A)} On se propose de montrer que la question de savoir si
-(pour un alphabet $\Sigma$ fixé) une grammaire hors contexte $G$
-vérifie $L(G) \neq \varnothing$, est décidable.  Autrement dit, on
+une grammaire hors contexte $G$ (sur un alphabet $\Sigma$ fixé)
+vérifie $L(G) \neq \varnothing$ est décidable.  Autrement dit, on
 veut montrer qu'il existe un algorithme qui prend en entrée une
 grammaire hors contexte $G$, termine toujours en temps fini, et
 renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) =
@@ -515,13 +518,13 @@ pour $G$ tout court).
 
 (3) Montrer que, quels que soient les entiers naturels $k$ et $m$, il
 n'y a qu'un nombre fini d'arbres (finis enracinés ordonnés) de
-valence $\leq k$ à chaque sommet (c'est-à-dire que chaque sommet ait
-au plus $k$ fils), dont les sommets sont étiquetés par des étiquettes
-prises dans un ensemble $\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et
-vérifiant la propriété ($\dagger$) de la question précédente.  Plus
-précisément, on pourra montrer que le nombre de tels arbres est donné
-par $N(k,m)$ défini par la récurrence $N(k,m) = m \, \sum_{r=0}^k
-N(k,m-1)^r$ en considérant l'étiquette de la racine (parmi $m$
+valence $\leq k$ (ceci signifie que chaque sommet a au plus $k$ fils),
+dont les sommets sont étiquetés par des étiquettes prises dans un
+ensemble $\{Z_1,\ldots,Z_m\}$ de cardinal $m$, et vérifiant la
+propriété ($\dagger$) de la question précédente.  Plus précisément, on
+pourra montrer que le nombre de tels arbres est donné par $N(k,m)$
+défini par la récurrence $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$ (et
+$N(k,0) = 0$) en considérant l'étiquette de la racine (parmi $m$
 possibles) et les $r \leq k$ sous-arbres qui partent de ses fils.
 
 \begin{corrige}
@@ -542,9 +545,9 @@ $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
 \textit{Indication}\quad Si $k$ est la longueur maximale d'une
 production de la grammaire $G$, on pourra chercher à construire tous
 les arbres (finis enracinés ordonnés) de valence $\leq k$, étiquetés
-par des terminaux ou nonterminaux ou $\varepsilon$, et vérifiant la
-propriété ($\dagger$), et regarder s'il y a un arbre d'analyse parmi
-eux.
+par des terminaux ou nonterminaux ou $\varepsilon$, vérifiant de plus
+la propriété ($\dagger$), et regarder s'il y a un arbre d'analyse
+parmi eux.
 
 \begin{corrige}
 Si $k$ est la longueur maximale d'une production de la grammaire $G$
@@ -557,9 +560,10 @@ effectif avec la récursion évidente sur $m$).  Il suffit ensuite de
 tester tous ces arbres concevables et de vérifie si, à chaque nœud,
 les contraintes imposées à un arbre d'analyse sont vérifiées.  Soit on
 trouve un arbre d'analyse pour $G$, auquel cas on a montré $L(G) \neq
-\varnothing$, soit il n'y a aucun arbre d'analyse pour $G$
-vérifiant ($\dagger$), donc aucun d'arbre d'analyse pour $G$ d'après
-la question (2), donc $L(G) = \varnothing$ d'après (1).
+\varnothing$ et on peut répondre « vrai » ; soit il n'y a aucun arbre
+d'analyse pour $G$ vérifiant ($\dagger$), donc aucun d'arbre d'analyse
+pour $G$ d'après la question (2), donc $L(G) = \varnothing$
+d'après (1) et on peut répondre « faux ».
 \end{corrige}
 
 \medbreak