diff options
| -rw-r--r-- | controle-20210618.tex | 272 |
1 files changed, 176 insertions, 96 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex index 585b9c1..aa30be9 100644 --- a/controle-20210618.tex +++ b/controle-20210618.tex @@ -102,7 +102,7 @@ Durée : 1h30 Barème \emph{indicatif} : 8+7+5. \ifcorrige -Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse). +Ce corrigé comporte 9 pages (page de garde incluse). \else Cet énoncé comporte 3 pages (page de garde incluse). \fi @@ -193,7 +193,8 @@ un automate fini \emph{déterministe complet}. \begin{corrige} L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet : pour le transformer en automate déterministe complet, on se contente -de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ : +pour obtenir l'automate $\mathscr{A}_2$ de lui ajouter un puits vers +lequel on fait pointer la seule transition manquante : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton] \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; @@ -230,11 +231,11 @@ L'automate $\mathscr{A}_2$ est déterministe complet sans état inaccessible. On commence l'algorithme de minimisation en séparant les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$. On sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$ -selon que la transition étiquetée $a$ conduit à un état final. Enfin, -la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux. -Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$, -$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$ -suivant : +selon que la transition étiquetée $a$ conduit à un état final ou non. +Enfin, la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en +deux. Finalement, on aboutit aux classes suivantes : $\{0\}$, +$\{1,2\}$, $\{3,4,5\}$ et $\{\bot\}$ (qu'on rebaptise $0,1,3,\bot$ +respectivement), et à l'automate minimal $\mathscr{A}_3$ suivant : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton] \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; @@ -394,14 +395,17 @@ nécessairement $aba$ comme préfixe. Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine (étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre (i.e., en démarrant par la règle $1$), les descendants du deuxième -fils (celui étiqueté $S$) forment eux-mêmes un arbre d'analyse -$\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ (d'après la -question précédente) commence par $a$, si bien que le mot $w = aw'bc$ -analysé par $\mathscr{T}$ commence par $aa$. (Si on préfère : une -dérivation de la forme $S \buildrel 1\over\Rightarrow aSbc -\mathrel{\Rightarrow^*} w$ a nécessairement $w = aw'bc$ où $w'$ est le -mot obtenu en appliquant les mêmes règles à $S$, qui commence donc -par $a$, si bien que $w$ commence par $aa$.) +fils (celui étiqueté $S$, y compris lui-même) forment eux-mêmes un +arbre d'analyse $\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ +commence par $a$ (d'après la question précédente), si bien que le mot +$w = aw'bc$ analysé par $\mathscr{T}$ commence par $aa$. (Avec la +notation qui sera introduite ci-dessous, on a $\mathscr{T} = +\mathbf{R}_1(\mathscr{T}')$.) + +Si on préfère : une dérivation de la forme $S \buildrel +1\over\Rightarrow aSbc \mathrel{\Rightarrow^*} w$ a nécessairement $w += aw'bc$ où $w'$ est le mot obtenu en appliquant les mêmes règles +à $S$, qui commence donc par $a$, si bien que $w$ commence par $aa$. Un raisonnement analogue conduit à conclure que tout mot dérivé en démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc @@ -415,10 +419,10 @@ les fils de la racine dans tout arbre d'analyse de $w$). \begin{corrige} Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots -ayant une dérivation selon $G$ démarrant par les règles $0,1,2$ -respectivement, on a trivialement $L_0 = \{abc\}$ et on vient de voir -que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ ont -$aba$ comme préfixe. Notamment : +ayant (au moins) une dérivation selon $G$ démarrant par les règles +$0,1,2$ respectivement, on a trivialement $L_0 = \{abc\}$ et on vient +de voir que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ +ont $aba$ comme préfixe. Notamment : \begin{itemize} \item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle démarre une dérivation de $w$ est déterminée par $w$), et @@ -433,22 +437,90 @@ expliquer comment trouver tous les arbres d'analyse du mot $awbc$ d'une part, et du mot $abwc$ d'autre part. \begin{corrige} -Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, on obtient -un arbre d'analyse $\mathscr{T}^\sharp$ de $w^\sharp := awbc$ de la -façon suivante : les quatre fils de la racine (étiquetée $S$) de -$\mathscr{T}^\sharp$ sont étiquetés $a,S,b,c$ respectivement (i.e., on -démarre par la règle $1$), et le second fils (celui étiqueté $S$) a -pour descendance une copie de $\mathscr{T}$ : ceci forme manifestement -un arbre d'analyse selon $G$, dont le mot analysé est $w^\sharp := -awbc$. \emph{Réciproquement}, comme $w^\sharp := awbc$ commence -par $aa$ (i.e., a $aa$ pour préfixe), on vient de voir que toute -dérivation de ce mot selon $G$ démarre nécessairement par la -règle $1$, donc a la forme qu'on vient de décrire. (Autrement dit : -$\mathscr{T} \mapsto \mathscr{T}^\sharp$ définit une bijection entre -les arbres d'analyse de $w$ et ceux de $awbc$.) - -Les mêmes considérations valent, \textit{mutatis mutandis} pour les -mots de la forme $w^\flat := abwc$ en commençant par la règle $2$. +Afin de s'épargner des répétitions fastidieuses, on définit pour toute +la suite de ce corrigé des notations pour les arbres d'analyse +selon $G$ démarrant par les règles $0,1,2$ respectivement, à savoir : +\begin{itemize} +\item on notera $\mathbf{R}_0$ l'arbre d'analyse associé à la + règle $0$, c'est-à-dire l'arbre dont la racine, étiquetée $S$, a + exactement trois fils, qui sont des feuilles, et qui sont étiquetés + $a,b,c$ dans cet ordre ; +\item si $\mathscr{T}$ est un arbre d'analyse selon $G$, on notera + $\mathbf{R}_1(\mathscr{T})$ l'arbre d'analyse associé à la règle $1$ + suivie des règles décrites par $\mathscr{T}$, c'est-à-dire l'arbre + dont la racine, étiquetée $S$, a exactement quatre fils, étiquetés + $a,S,b,c$ dans cet ordre, où le premier et les deux derniers sont + des feuilles et où les descendants du second (y compris lui-même) + forment une copie de l'arbre d'analyse $\mathscr{T}$ ; +\item de façon analogue, si $\mathscr{T}$ est un arbre d'analyse + selon $G$, on notera $\mathbf{R}_2(\mathscr{T})$ l'arbre d'analyse + associé à la règle $2$ suivie des règles décrites par $\mathscr{T}$, + c'est-à-dire l'arbre dont la racine, étiquetée $S$, a exactement + quatre fils, étiquetés $a,b,S,c$ dans cet ordre, où les deux + premiers et le dernier sont des feuilles et où les descendants du + troisième (y compris lui-même) forment une copie de l'arbre + d'analyse $\mathscr{T}$. +\end{itemize} + +Soit graphiquement : +\begin{center} +\begin{tabular}{c|c|c} +$\mathbf{R}_0$&$\mathbf{R}_1(\mathscr{T})$&$\mathbf{R}_2(\mathscr{T})$\\ +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (20.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (c0) at (40.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +& +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (S1) at (20.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1); +\node (b0) at (40.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +& +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$}; +\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0); +\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0); +\node (S1) at (40.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1); +\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0); +\end{tikzpicture} +\end{tabular} +\end{center} +(par exemple, l'arbre d'analyse répondant à la question $1$ est +l'arbre $\mathbf{R}_2(\mathbf{R}_1(\mathbf{R}_0))$). + +Manifestement, tout arbre d'analyse selon $G$ est soit l'arbre +$\mathbf{R}_0$, soit de la forme $\mathbf{R}_1(\mathscr{T})$ ou +$\mathbf{R}_2(\mathscr{T})$ avec $\mathscr{T}$ un autre arbre +(strictement plus petit). + +Répondons maintenant à la question posée. + +Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, alors +$\mathbf{R}_1(\mathscr{T})$ est un arbre d'analyse de $awbc$ (toujours +selon $G$). Mais réciproquement, comme $awbc$ commence par $aa$ +(i.e., a $aa$ pour préfixe), on a vu en (4) que toute dérivation du +mot $awbc$ selon $G$ démarre nécessairement par la règle $1$, +c'est-à-dire que tout arbre d'analyse de $awbc$ est de la +forme $\mathbf{R}_1(\mathscr{T})$, et $\mathscr{T}$ est alors +uniquement défini (comme ce qui descend du deuxième fils de la +racine). Bref : $\mathbf{R}_1$ définit une bijection entre les arbres +d'analyse de $w$ et ceux de $awbc$. + +De même, si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, +alors $\mathbf{R}_2(\mathscr{T})$ est un arbre d'analyse de $abwc$. +Mais réciproquement, comme $abwc$ commence par $aba$ (i.e., a $aba$ +pour préfixe), on a vu en (4) que toute dérivation du mot $abwc$ +selon $G$ démarre nécessairement par la règle $2$, c'est-à-dire que +tout arbre d'analyse de $abwc$ est de la +forme $\mathbf{R}_2(\mathscr{T})$, et $\mathscr{T}$ est alors +uniquement défini (comme ce qui descend du troisième fils de la +racine). Bref : $\mathbf{R}_2$ définit une bijection entre les arbres +d'analyse de $w$ et ceux de $awbc$. \end{corrige} (6) En déduire que tout mot $w \in L$ possède un unique arbre @@ -456,57 +528,60 @@ d'analyse selon $G$, et proposer (sur la base des questions précédentes) un algorithme qui le calcule. \begin{corrige} -D'après les questions suivantes, tout mot de $L$ est dans un et un -seul des trois cas suivants : soit c'est le mot $abc$ produit par la -règle $abc$, soit il commence par $aa$ et c'est un mot de la forme -$awbc$ produit par une dérivation démarrant par la règle $1$ puis en -suivant une dérivation de $w$, soit il commence par $aba$ et c'est un -mot de la forme $abwc$ produit par une dérivation démarrant par la -règle $2$ puis en suivant une dérivation de $w$. (Si on veut, $L$ est -réunion disjointe de $L_0,L_1,L_2$ où $L_0 = \{abc\}$ et $w \mapsto -awbc$ est une bijection $L \to L_1$ et $w \mapsto abwc$ est une -bijection $L \to L_2$.) +En reformulant les conclusions des questions suivantes, tout mot $w$ +de $L$ est dans un et un seul des trois cas suivants : +\begin{itemize} +\item soit $w$ est le mot $abc$ et son unique arbre d'analyse selon $G$ + est $\mathbf{R}_0$, +\item soit $w$ commence par $aa$ et alors $w$ est de la forme $aw'bc$ + et tout arbre d'analyse de $w$ selon $G$ est de la forme + $\mathbf{R}_1(\mathscr{T}')$ pour un unique arbre d'analyse + $\mathscr{T}'$ de $w'$, +\item soit $w$ commence par $aba$ et alors $w$ est de la forme $abw'c$ + et tout arbre d'analyse de $w$ selon $G$ est de la forme + $\mathbf{R}_2(\mathscr{T}')$ pour un unique arbre d'analyse + $\mathscr{T}'$ de $w'$. +\end{itemize} Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un -unique arbre d'analyse selon $G$ : en effet, il est soit de la forme -$abc$, soit de la forme $aw'bc$, soit de la forme $abw'c$ avec dans -les deux derniers cas $|w'| < |w|$ (précisément $|w'| = |w|-3$), donc -$w'$ a un unique arbre d'anayse selon $G$ par récurrence, d'où il -résulte que $w$ a un unique arbre d'analyse (qui s'obtient à partir de -celui de $w'$ en mettant la règle $1$ ou $2$ au sommet comme expliqué -dans la question (5)). +unique arbre d'analyse selon $G$ : en effet, dans le premier des trois +cas ci-dessus, $w$ a pour unique arbre d'analyse $\mathbf{R}_0$, et +dans les deux derniers cas on a $|w'| < |w|$ (précisément $|w'| = +|w|-3$), donc $w'$ a un unique arbre d'anayse $\mathscr{T}'$ selon $G$ +par l'hypothèse de récurrence, d'où il résulte que $w$ a lui aussi un +unique arbre d'analyse (à savoir $\mathbf{R}_1(\mathscr{T}')$ ou +$\mathbf{R}_2(\mathscr{T}')$). + +La grammaire $G$ est donc inambiguë. Cette démonstration est constructive, c'est-à-dire qu'on a -l'algorithme suivant qui analyse un mot $w$ : +l'algorithme suivant qui analyse un mot $w$ et renvoie l'unique arbre +d'analyse de $w$ selon $G$ (s'il existe, ou signale une erreur +d'analyse dans le cas contraire) : \begin{itemize} -\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre de la - règle $0$ (c'est-à-dire ayant une racine étiquetée $S$ avec trois - fils, tous des feuilles, étiquetés $a,b,c$ respectivement) ; +\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre + $\mathbf{R}_0$ ; \item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$ - (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot + (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot obtenu en effaçant le $a$ initial et le $bc$ final, appliquer récursivement l'algorithme qu'on est en train de définir au - mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer - l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $1$ et - de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine - étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,S,b,c$ - respectivement, et le second fils a pour descendance une copie - de $\mathscr{T}'$) ; + mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer, + et renvoyer $\mathbf{R}_1(\mathscr{T}')$ ; \item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$ - (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot + (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot obtenu en effaçant le $ab$ initial et le $c$ final, appliquer récursivement l'algorithme qu'on est en train de définir au - mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer - l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $2$ et - de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine - étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,b,S,c$ - respectivement, et le troisième fils a pour descendance une copie - de $\mathscr{T}'$) ; + mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer, + et renvoyer $\mathbf{R}_2(\mathscr{T}')$ ; \item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence - par autre chose que $aa$ ou $aba$), terminer avec une erreur + par autre chose que $aa$ ou $aba$), abandonner avec une erreur d'analyse. \end{itemize} -\vskip-\baselineskip\strut +(L'algorithme termine en temps fini parce que les appels récursifs se +font sur des mots de longueur strictement plus courte. Il s'agit d'un +algorithme par « descente récursive », qui se transforme facilement, +quitte à remplacer la pile des appels récursifs en une pile en tant +que structure de données, en un analyseur LL.) \end{corrige} @@ -530,11 +605,11 @@ semi-décidable ? On justifiera soigneusement les réponses. \begin{corrige} Le langage proposé n'est pas rationnel car il n'est pas algébrique. -Il est décidable car il est évident qu'on peut algorithmiquement -vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci +Il est décidable car il est évident qu'on peut algorithmiquement d'une +part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable -par automate fini) puis vérifier qu'il a autant de $a$ que de $b$ que -de $c$. +par automate fini) et d'autre part vérifier qu'il a autant de $a$ que +de $b$ que de $c$. Étant décidable, il est notamment semi-décidable. \end{corrige} @@ -561,28 +636,33 @@ L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera soigneusement. \begin{corrige} -L'ensemble $J$ n'est pas semi-décidable. En effet, supposons par -l'absurde qu'on dispose d'un algorithme $T$ qui semi-décide $J$ (où -« semi-décider » un ensemble $Z$ signifie : terminer en renvoyant $1$ -(=vrai) si l'entrée $z$ fournie appartient à $Z$, et ne pas terminer -sinon). Fixons une fois pour toutes $f$ (le code d')un programme qui, -donnée une entrée $x$, termine immédiatement (en ignorant $x$). Alors -trivialement $(f,x) \in H$ quel que soit $x$ ; donc, par définition -de $J$, on a $(f,e,x) \in J$ si et seulement si $(e,h) \not \in H$. -On dispose alors d'un algorithme $T'$ qui semi-décide le -complémentaire de $H$, défini de la manière suivante : donnés $(e,x)$, -on applique l'algorithme $T$ (qu'on a supposé exister) au triplet -$(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in J$), on -renvoie $1$ (sinon, bien sûr, on ne termine jamais) ; par +L'ensemble $J$ n'est pas semi-décidable. + +Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme +$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$ +signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie +appartient à $Z$, et ne pas terminer sinon). Fixons une fois pour +toutes (le code d')un programme $f$ qui, donnée une entrée $x$, +termine immédiatement (en ignorant $x$). Alors trivialement $(f,x) +\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x) +\in J$ si et seulement si $(e,h) \not \in H$. + +On considère alors l'algorithme $T'$, défini de la manière suivante : +donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister) +au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in +J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais). Par construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si $(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne -termine pas ; ceci signifie justement que $T'$ semi-décide le -complémentaire de $H$. Or le complémentaire de $H$ n'est pas -semi-décidable (car si le complémentaire de $H$ était semi-décidable, -on aurait à la fois $H$ et son complémentaire semi-décidables, donc -$H$ serait décidable, et on sait qu'il ne l'est pas). C'est une -contradiction : $J$ n'est donc pas semi-décidable. \textit{A - fortiori}, $J$ n'est pas décidable. +termine pas. Ceci signifie que $T'$ semi-décide le complémentaire +de $H$. + +Or le complémentaire de $H$ n'est pas semi-décidable (car si le +complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et +son complémentaire semi-décidables, donc $H$ serait décidable, et on +sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas +exister. C'est une contradiction : $J$ n'est donc pas semi-décidable. + +\textit{A fortiori}, $J$ n'est pas décidable. \end{corrige} |