diff options
Diffstat (limited to 'controle-20210618.tex')
| -rw-r--r-- | controle-20210618.tex | 672 |
1 files changed, 672 insertions, 0 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex new file mode 100644 index 0000000..aa30be9 --- /dev/null +++ b/controle-20210618.tex @@ -0,0 +1,672 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning} +\usepackage{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{18 juin 2021} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 1h30 + +Barème \emph{indicatif} : 8+7+5. + +\ifcorrige +Ce corrigé comporte 9 pages (page de garde incluse). +\else +Cet énoncé comporte 3 pages (page de garde incluse). +\fi + +\vfill + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On considère +l'expression rationnelle $r := bb{*}a(a|b){*}$, et soit $L := L(r)$ le +langage qu'elle dénote (autrement dit, c'est le langage constitué des +mots qui commencent par un nombre $\geq 1$ de fois la lettre $b$, +immédiatement suivis par la lettre $a$, puis n'importe quoi). + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$. On ne demande pas +de justifier les réponses. + +\begin{corrige} +Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas +à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$. +\end{corrige} + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être plus +lourdement sanctionnées. + +(1) Traiter l'une \emph{ou} l'autre des questions suivantes : +(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; +(ii) construire l'automate de Thompson de $r$, puis éliminer les +transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ +l'automate ainsi obtenu. + +(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$. +À défaut de donner l'automate de Glushkov ou de Thompson, donner un +NFA reconnaissant $L$ pourra apporter une partie des points.) + +\begin{corrige} +L'automate $\mathscr{A}_1$ trouvé est le suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera +$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici +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 +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$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q2) at (120bp,0bp) [draw,circle,state] {$2$}; +\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$}; +\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$}; +\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$b$} (q2); +\draw[->] (q2) to[loop above] node[auto]{$b$} (q2); +\draw[->] (q2) -- node[auto]{$a$} (q3); +\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3); +\draw[->] (q3) -- node[auto]{$a$} (q4); +\draw[->] (q3) -- node[auto,below]{$b$} (q5); +\draw[->] (q4) to[loop above] node[auto]{$a$} (q4); +\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5); +\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4); +\draw[->] (q5) to[loop below] node[auto]{$b$} (q5); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(3) Minimiser l'automate $\mathscr{A}_2$. On appellera +$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du +langage $L$). + +\begin{corrige} +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 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$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$}; +\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (Sink); +\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +(4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet +$\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ +complémentaire de $L$. + +\begin{corrige} +Il suffit d'échanger les états finaux et non-finaux +dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$ +suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$}; +\node (q3) at (120bp,0bp) [draw,circle,state] {$3$}; +\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q1) -- node[auto]{$a$} (q3); +\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ); +\end{tikzpicture} +\end{center} +(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur +ce nouvel automate, en revanche $3$ en est un. Ces nom sont, bien +sûr, sans aucun impact sur le fonctionnement de l'automate.) +\end{corrige} + +(5) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le +langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne +vérifient pas $r$). +\begin{corrige} +Pour procéder à l'algorithme d'élimination des états, on commence par +donner à l'automate un unique état final sans aucune transition qui en +part, appelons-le $\infty$. On peut aussi d'ores et déjà éliminer +l'état $3$ qui est maintenant inutile, et remplacer les deux +transitions $Z\to Z$ étiquetées $a$ et $b$ par une seule +étiquetée $a|b$ (ce qui, dans un RNFA, revient au même) : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (q1) at (60bp,0bp) [draw,circle,state] {$1$}; +\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$}; +\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$}; +\draw[->] (q0) -- node[auto]{$b$} (q1); +\draw[->] (q1) to[loop above] node[auto]{$b$} (q1); +\draw[->] (q0) -- node[auto,swap]{$a$} (qZ); +\draw[->] (qZ) to[loop left] node[auto]{$a|b$} (qZ); +\draw[->] (q0) -- node[auto]{$\varepsilon$} (final); +\draw[->] (q1) -- node[auto]{$\varepsilon$} (final); +\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final); +\end{tikzpicture} +\end{center} +L'élimination de l'état $1$ conduit à remplacer la transition +$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et +l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$. +Finalement, on a affaire à un automate ayant les seuls états $0$ +(initial) et $\infty$ (final) avec la seule transition $0\to\infty$ +étiquetée par l'expression rationnelle $s$ recherchée : +\[ +\varepsilon \,|\, bb{*} \,|\, a(a|b){*} +\] +qui dénote le langage $M$ complémentaire de $L$. (Autrement dit : un +mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$ +suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit +formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de +n'importe quoi.) +\end{corrige} + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma = +\{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles +\[ +S \rightarrow abc \;|\; aSbc \;|\; abSc +\] +On appellera « $0$ » la règle $S \rightarrow abc$, et « $1$ » la règle +$S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$. + +(1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$ +selon cette grammaire $G$. (On pourra d'abord lire les questions +suivantes si on a du mal à trouver comment dériver ce mot.) + +\begin{corrige} +L'arbre d'analyse est le suivant : +% S<a.b.S<a.S<a.b.c.>b.c.>c.> +\begin{center} +\begin{tikzpicture}[line join=bevel,baseline=(S0.base)] +\node (S0) at (68.750bp,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 (95.000bp,-30.000bp) [draw=none] {$S$}; \draw (S0) -- (S1); +\node (a1) at (40.000bp,-60.000bp) [draw=none] {$a$}; \draw (S1) -- (a1); +\node (S2) at (80.000bp,-60.000bp) [draw=none] {$S$}; \draw (S1) -- (S2); +\node (a2) at (60.000bp,-90.000bp) [draw=none] {$a$}; \draw (S2) -- (a2); +\node (b1) at (80.000bp,-90.000bp) [draw=none] {$b$}; \draw (S2) -- (b1); +\node (c0) at (100.000bp,-90.000bp) [draw=none] {$c$}; \draw (S2) -- (c0); +\node (b2) at (120.000bp,-60.000bp) [draw=none] {$b$}; \draw (S1) -- (b2); +\node (c1) at (140.000bp,-60.000bp) [draw=none] {$c$}; \draw (S1) -- (c1); +\node (c2) at (160.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c2); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-1ex\strut +\end{corrige} + +On va maintenant montrer que $G$ est inambiguë. + +(2) Expliquer pourquoi tout mot non-vide du langage $L := L(G)$ +engendré par $G$ a nécessairement $a$ pour préfixe (i.e., commence par +la lettre $a$). + +\begin{corrige} +Les trois règles $0,1,2$ ont toutes le terminal $a$ comme premier +symbole de leur membre de droite. Le fils le plus à gauche de la +racine (étiquetée $S$) dans n'importe quel arbre d'analyse selon $G$ +est nécessairement étiqueté $a$, et le mot analysé commence donc +nécessairement par $a$. (Si on préfère, toute dérivation selon $G$ +commence par une règle produisant $a$ comme symbole le plus à gauche, +qui ne peut ensuite jamais être effacé ni réécrit puisqu'il s'agit +d'un terminal.) +\end{corrige} + +(3) Montrer que tout mot de $L$ dérivé en démarrant +par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation + selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$ + où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de + dérivations immédiates. Ou, ce qui revient au même (et on pourra + tenir ce point pour acquis) : tout mot $w$ possédant un arbre + d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet + ordre.} la règle $1$ a nécessairement $aa$ comme préfixe. Montrer +de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a +nécessairement $aba$ comme préfixe. + +\begin{corrige} +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$, 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 +commence par $a$, si bien que le mot commence par $aba$. +\end{corrige} + +(4) En déduire comment, d'après les premières lettres d'un mot $w$ +de $L$, on peut savoir par quelle règle démarre nécessairement une +dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont +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 (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 +\item on peut savoir si un mot $w \in L$ appartient à $L_0$, $L_1$ + ou $L_2$ en regardant s'il commence par $abc$, $aa$ ou $aba$. +\end{itemize} +Ce qui répond à la question posée. +\end{corrige} + +(5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$, +expliquer comment trouver tous les arbres d'analyse du mot $awbc$ +d'une part, et du mot $abwc$ d'autre part. + +\begin{corrige} +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 +d'analyse selon $G$, et proposer (sur la base des questions +précédentes) un algorithme qui le calcule. + +\begin{corrige} +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, 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$ 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 + $\mathbf{R}_0$ ; +\item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$ + (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'$, 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 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'$, 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$), abandonner avec une erreur + d'analyse. +\end{itemize} +(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} + + +% +% +% + +\exercice + +(Les deux questions suivantes sont indépendantes.) + +\smallskip + +(1) Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas +algébrique\footnote{Ce fait est démontré dans le poly, dans la section + consacrée au lemme de pompage pour les langages algébriques et comme + illustration de ce dernier ; on ne demande bien sûr pas ici de le + redémontrer.}. Est-il rationnel ? Est-il décidable ? Est-il +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 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) 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} + +\smallskip + +(2) On rappelle la définition du problème de l'arrêt : c'est +l'ensemble $H$ des couples\footnote{Pour être rigoureux, on a fixé un + codage permettant de représenter les programmes $e$, les entrées $x$ + à ces programmes, et les couples $(e,x)$, comme des éléments + de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet + $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de + faire apparaître ce codage dans la description des algorithmes + proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme +(= algorithme) $e$ et d'une entrée $x$, tels que l'exécution du +programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en +cours que $H$ était semi-décidable mais non décidable. + +On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que +$(e_1,x) \in H$ et $(e_2,x) \not\in H$. Autrement dit, le programme +$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais +le programme $e_2$, lui, ne termine pas sur cette même entrée. +L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera +soigneusement. + +\begin{corrige} +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 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} + + +% +% +% +\end{document} |