Write a second exercise for the exam.

1 files changed, 194 insertions, 0 deletions

diff --git a/controle-20220616.tex b/controle-20220616.tex
index cf36e07..1ecbd0a 100644
--- a/controle-20220616.tex
+++ b/controle-20220616.tex
@@ -453,4 +453,198 @@ d'élimination des états).
 %
 %
 %
+
+\exercice
+
+Les parties (A), (B) et (C) de cet exercice sont indépendantes.
+
+\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
+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) =
+\varnothing$.
+
+(1) Expliquer pourquoi $L(G) \neq \varnothing$ si et seulement si il
+existe un arbre d'analyse $\mathscr{T}$ pour $G$.
+
+\begin{corrige}
+Tout mot de $L(G)$ a (au moins) un arbre d'analyse pour $G$, et tout
+arbre d'analyse pour $G$ est l'arbre d'analyse d'un mot de $L(G)$ :
+ainsi, si $L(G) \neq \varnothing$, il existe un arbre d'analyse
+pour $G$, et si $L(G) = \varnothing$ il n'existe pas d'arbre d'analyse
+pour $G$.
+\end{corrige}
+
+(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$ ».
+
+\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$.
+
+\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$).
+
+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$),
+sans quoi la construction qu'on vient de donner produirait un arbre
+$\mathscr{T}'$ ayant strictement moins de nœuds, contredisant la
+minimalité.  Il existe donc bien un arbre d'analyse pour $G$
+vérifiant ($\dagger$) (dès lors qu'il existe un arbre d'analyse
+pour $G$ tout court).
+\end{corrige}
+
+(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$
+possibles) et les $r \leq k$ sous-arbres qui partent de ses fils.
+
+\begin{corrige}
+Un arbre $\mathscr{T}$ de valence $\leq k$ vérifiant ($\dagger$) et
+dont les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\}$ s'obtient
+en choisissant l'étiquette $Z_i$ de la racine parmi $m$ possibles, le
+nombre $0\leq r\leq k$ de fils de la racine, et les sous-arbres
+$\mathscr{T}_1,\ldots,\mathscr{T}_r$ qui en descendent, qui sont
+eux-mêmes des arbres de valence $\leq k$ vérifiant ($\dagger$) et dont
+les étiquettes sont prises parmi $\{Z_1,\ldots,Z_m\} \setminus
+\{Z_i\}$, c'est-à-dire parmi $m-1$ possibles.  Par récurrence sur $m$,
+on montre donc que ce nombre est fini, et précisément qu'il vérifie
+$N(k,m) = m \, \sum_{r=0}^k N(k,m-1)^r$.
+\end{corrige}
+
+(4) En déduire un algorithme répondant à la question posée.
+
+\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.
+
+\begin{corrige}
+Si $k$ est la longueur maximale d'une production de la grammaire $G$
+et $m$ le nombre d'étiquettes possibles d'un arbre d'analyse selon $G$
+(c'est-à-dire le nombre de nonterminaux plus le nombre de terminaux
+plus $1$ pour $\varepsilon$, mais peu importe), on commence par
+énumérer tous les arbres de valence $\leq k$, étiquetés par les tokens
+en question, ce qui est possible d'après la question précédente (et
+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).
+\end{corrige}
+
+\medbreak
+
+\textbf{(B)} Montrer que la question de savoir si (pour un alphabet
+$\Sigma$ fixé) une grammaire hors contexte $G$ vérifie $L(G) \neq
+\Sigma^*$, est semi-décidable.  Autrement dit, montrer qu'il existe un
+algorithme qui prend en entrée une grammaire hors contexte $G$,
+termine en temps fini et renvoie « vrai » si $L(G) \neq \Sigma^*$, et
+ne termine pas si $L(G) = \Sigma^*$.
+
+\textit{Indication.}\quad On pourra pour cela énumérer tous les mots
+possibles à la recherche d'un mot qui \emph{n'appartient pas}
+à $L(G)$, et utiliser le fait que tester si $w \in L(G)$ est
+décidable.
+
+\begin{corrige}
+L'algorithme suivant convient : énumérer tous les mots $w \in
+\Sigma^*$ et, pour chacun, utiliser la procédure de décision connue
+pour déterminer en temps fini si $w \in L(G)$.  Si ce n'est pas le
+cas, on termine immédiatement en renvoyant « vrai » (on a $L(G) \neq
+\Sigma^*$) ; si c'est le cas, on continue (on passe au mot suivant).
+Cet algorithme termine (et renvoie « vrai » dans ce cas) exactement
+lorsque $L(G) \neq \Sigma^*$ : il montre donc la semi-décidabilité du
+problème considéré.
+\end{corrige}
+
+\medbreak
+
+\textbf{(C)} (1) Montrer qu'il existe un algorithme qui, donnés une
+expression rationnelle $r_1$ et une grammaire hors contexte $G_1$ (sur
+un même alphabet $\Sigma$), calcule (= renvoie) une grammaire hors
+contexte $G_2$ telle que $L(G_2) = L(G_1) \cup (\Sigma^* \setminus
+L(r_1))$.
+
+\begin{corrige}
+D'après divers résultats du cours : donnée une expression rationnelle
+$r_1$, on sait calculer algorithmiquement un NFA $A_1$ tel que $L(r_1)
+= L(A_1)$ (par exemple avec la construction de Glushkov), on sait
+calculer algorithmiquement un DFA $A_2$ tel que $L(A_1) = L(A_2)$ (en
+déterminisant $A_1$), on sait calculer algorithmiquement un DFA $A_2$
+tel que $L(A_3) = \Sigma^* \setminus L(A_2)$ (en échangeant états
+finaux et non-finaux), on sait calculer algorithmiquement une
+grammaire hors contexte $G_3$ telle que $L(G_3) = L(A_3)$ (en
+construisant une grammaire régulière), et à partir de $G_1$ et $G_3$
+on sait calculer algorithmiquement une grammaire hors contexte $G_2$
+telle que $L(G_2) = L(G_1) \cup L(G_3)$ (stabilité algorithmique des
+langages algébriques par union) : on a alors $L(G_2) = L(G_1) \cup
+(\Sigma^* \setminus L(r_1))$ comme annoncé.
+\end{corrige}
+
+(2) On \underline{admet} que le problème suivant n'est pas décidable
+(pour un alphabet $\Sigma$ fixé de cardinal $\#\Sigma \geq 2$) :
+donnés $G$ une grammaire hors contexte et $r$ une expression
+rationnelle, savoir si $L(r) \subseteq L(G)$.  En déduire que le
+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
+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
+$L(r_1) \subseteq L(G_1)$.
+
+\begin{corrige}
+Supposons par l'absurde qu'on dispose d'un algorithme $\mathfrak{A}$
+qui prend une grammaire hors contexte $G$ en entrée et décide si $L(G)
+= \Sigma^*$.  Considérons l'algorithme suivant qui prend en entrée une
+grammaire hors contexte $G_1$ et une expression rationnelle $r_1$ : on
+commence par calculer une grammaire $G_2$ telle que $L(G_2) = L(G_1)
+\cup (\Sigma^* \setminus L(r_1))$ comme expliqué en question (1), et
+on applique à $G_2$ l'algorithme $\mathfrak{A}$ qu'on a supposé
+exister pour décider si $L(G_2) = \Sigma^*$.  Comme $L(G_2) = L(G_1)
+\cup (\Sigma^* \setminus L(r_1))$, dont le complémentaire est $L(r_1)
+\setminus L(G_1)$, on a $L(G_2) = \Sigma^*$ si et seulement si $L(r_1)
+\subseteq L(G_1)$ : on peut donc renvoyer « vrai » dans ce cas et
+« faux » sinon.  Ceci montre l'existence d'un algorithme décidant si
+$L(r_1) \subseteq L(G_1)$, ce qui est impossible (résultat admis).
+C'est donc que l'hypothèse de l'existence de $\mathfrak{A}$ était
+absurde, et le problème en question n'est pas décidable.
+\end{corrige}
+
+
+%
+%
+%
 \end{document}