diff options
| -rw-r--r-- | controle-20220616.tex | 79 |
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 |