Rephrase and clarify a number of questions in first part of second exercise.

1 files changed, 47 insertions, 32 deletions

diff --git a/controle-20220616.tex b/controle-20220616.tex
index b1be47e..de686d6 100644
--- a/controle-20220616.tex
+++ b/controle-20220616.tex
@@ -472,7 +472,9 @@ renvoie « vrai » si $L(G) \neq \varnothing$ et « faux » si $L(G) =
 \varnothing$.
 
 (1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il
-existe un arbre d'analyse $\mathscr{T}$ pour $G$.
+existe un arbre d'analyse $\mathscr{T}$ pour $G$.  (Un « arbre
+d'analyse pour $G$ » désigne un arbre d'analyse d'un mot quelconque
+selon $G$.)
 
 \begin{corrige}
 Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout
@@ -482,30 +484,40 @@ pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse
 pour $G$.
 \end{corrige}
 
+$\bullet$ Pour les questions suivantes, on introduit la terminologie
+suivante : si $\mathscr{T}$ est un arbre et $n$ un nœud (=sommet)
+de $\mathscr{T}$, on dit qu'un nœud $n'$ est un \textbf{descendant} de
+$n$ lorsque $n'$ est soit égal à $n$, soit est un fils de $n$, soit
+est un fils d'un fils de $n$, etc., à n'importe quelle profondeur.
+L'ensemble des descendants de $n$ (y compris $n$ lui-même) est donc un
+arbre ayant $n$ pour racine, qu'on appelle \textbf{sous-arbre qui
+  descend} de $n$.
+
 (2) Montrer que s'il existe un arbre d'analyse $\mathscr{T}$ pour $G$,
 il en existe un vérifiant la propriété additionnelle suivante :
-($\dagger$) « aucun nœud $n'$ descendant d'un nœud $n$ étiqueté par un
-nonterminal $X$ ne porte lui-même l'étiquette $X$ ».
+($\dagger$) « si un nœud $n$ est étiqueté par un nonterminal $X$,
+alors aucun nœud $n' \neq n$ descendant de $n$ ne porte la même
+étiquette $X$ ».
 
-\textit{Indication}\quad Pour cela, on pourra remarquer que si un
-arbre ne vérifie pas ($\dagger$), on peut en construire un autre ayant
-strictement moins de nœuds, en remplaçant le sous-arbre descendant
-de $n$ par celui descendant de $n'$, et expliquer pourquoi c'est
-encore un arbre d'analyse pour $G$.
+\textit{Indication.}\quad Pour cela, on pourra remarquer que si un
+arbre $\mathscr{T}$ ne vérifie pas ($\dagger$), on peut en construire
+un autre ayant strictement moins de nœuds, en remplaçant le sous-arbre
+qui descend de $n$ par celui qui descend de $n'$, et expliquer
+pourquoi c'est encore un arbre d'analyse pour $G$ si $\mathscr{T}$ en
+est un.
 
 \begin{corrige}
 Si $\mathscr{T}$ est un arbre d'analyse pour $G$ dans lequel un nœud
 $n'$ descendant d'un autre nœud $n$ est étiqueté par le même
 symbole $X$, alors on peut fabriquer un arbre $\mathscr{T}'$ en
-remplaçant $n$ par $n'$, c'est-à-dire plus exactement en remplaçant le
-sous-arbre descendant de $n$ par celui descendant de $n'$.  Cet arbre
-$\mathscr{T}'$ a strictement moins de nœuds que $\mathscr{T}$ car ses
-nœuds sont exactement ceux de $\mathscr{T}$ à l'exception de ceux qui
-descendent de $n$ mais pas de $n'$.  Par ailleurs, c'est toujours un
-arbre d'analyse pour $G$ car chaque nœud a des fils étiquetés
-exactement de la même manière (le seul pour lequel ce n'est pas
-évident est le parent de $n$, mais c'est bien vrai car $n'$ et $n$ ont
-la même étiquette $X$).
+remplaçant le sous-arbre qui descend de $n$ par celui qui descend
+de $n'$.  Cet arbre $\mathscr{T}'$ a strictement moins de nœuds
+que $\mathscr{T}$ car ses nœuds sont exactement ceux de $\mathscr{T}$
+à l'exception de ceux qui descendent de $n$ mais pas de $n'$.  Par
+ailleurs, c'est toujours un arbre d'analyse pour $G$ car chaque nœud a
+des fils étiquetés exactement de la même manière (le seul pour lequel
+ce n'est pas évident est le nœud parent de $n$, mais c'est bien vrai
+car $n'$ et $n$ ont la même étiquette $X$).
 
 Si on considère maintenant $\mathscr{T}$ l'arbre d'analyse pour $G$
 ayant le nombre minimal de nœuds, il vérifie forcément ($\dagger$),
@@ -516,16 +528,19 @@ vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse
 pour $G$ tout court).
 \end{corrige}
 
+$\bullet$ Pour la question suivante, on dira qu'un arbre $\mathscr{T}$
+est de \textbf{valence} $\leq k$ lorsque chaque nœud de $\mathscr{T}$
+a au plus $k$ fils.
+
 (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$ (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.
+n'y a qu'un nombre fini d'arbres de valence $\leq k$, 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 descendent de ses fils.
 
 \begin{corrige}
 Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et
@@ -542,12 +557,12 @@ $N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
 
 (4) En déduire un algorithme répondant à la question posée.
 
-\textit{Indication}\quad Si $k$ est la longueur maximale d'une
+\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$, vérifiant de plus
-la propriété ($\dagger$), et regarder s'il y a un arbre d'analyse
-parmi eux.
+les arbres de valence $\leq k$, étiquetés 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$
@@ -623,7 +638,7 @@ problème suivant (qui en est un cas particulier) n'est lui-même pas
 décidable : donnée $G$ une grammaire hors contexte, savoir si $L(G) =
 \Sigma^*$.
 
-\textit{Indication}\quad Pour cela, on pourra supposer par l'absurde
+\textit{Indication.}\quad Pour cela, on pourra supposer par l'absurde
 que le problème de reconnaître si $L(G) = \Sigma^*$ est décidable et,
 donnés $G_1$ et $r_1$, construire algorithmiquement une grammaire hors
 contexte $G_2$ telle que $L(G_2) = \Sigma^*$ si et seulement si