path: root/controle-20210618.tex

%% 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}