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