path: root/exercices3.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[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\newcommand\exercicenobreak{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\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\relax\else\egroup\fi\par}
%
%
% 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{Exercices divers — Corrigé}
\else
\title{Exercices divers}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000



%
%
%

\bigskip
\centerline{\textbf{Langages rationnels et automates}}
\penalty8000
\exercicenobreak

Soit $\Sigma = \{a,b\}$.

(1) Tracer l'automate de Thompson de l'expression rationnelle
$a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?

(2) En éliminer les transitions spontanées.

(3) Déterminiser l'automate obtenu (on demande un automate complet).

(4) Minimiser l'automate obtenu (on demande un automate complet).

(5) Vérifier le résultat en décrivant en français le langage dénoté
par l'expression rationnelle initiale et reconnu par l'automate
finalement obtenu.

\begin{corrige}
(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$
  états puisque cette expression rationnelle contient $7$ symboles
  parenthèses non comptées.  Il est le suivant (où on a omis les
  $\varepsilon$ sur les transitions spontanées) :
\begin{center}
\scalebox{0.34}{%
%%% begin ex3p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,45bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q3) at (255bp,18bp) [draw,circle,state] {$3$};
  \node (q2) at (176bp,45bp) [draw,circle,state] {$2$};
  \node (q5) at (413bp,48bp) [draw,circle,state] {$5$};
  \node (q4) at (334bp,18bp) [draw,circle,state] {$4$};
  \node (q7) at (571bp,86bp) [draw,circle,state] {$7$};
  \node (q6) at (492bp,86bp) [draw,circle,state] {$6$};
  \node (q9) at (729bp,86bp) [draw,circle,state] {$9$};
  \node (q8) at (650bp,86bp) [draw,circle,state] {$8$};
  \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$};
  \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$};
  \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$};
  \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$};
  \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp)  .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp)  .. node[auto] {{}} (q3);
  \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp)  .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp)  .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp)  .. node[auto] {{}} (q5);
  \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp)  .. node[auto] {{}} (q3);
  \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp)  .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp)  .. node[auto] {$a$} (q8);
  \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp)  .. node[auto] {{}} (q12);
  \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp)  .. node[auto] {{}} (q9);
  \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp)  .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp)  .. node[auto] {{}} (q12);
  \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp)  .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp)  .. node[auto] {{}} (q1);
  \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp)  .. node[auto] {{}} (q7);
  \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp)  .. node[auto] {{}} (q13);
  \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp)  .. node[auto] {{}} (q10);
  \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp)  .. node[auto] {{}} (q4);
  \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp)  .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp)  .. node[auto] {{}} (q10);
  \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp)  .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp)  .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp)  .. node[auto] {{}} (q13);
  \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp)  .. node[auto] {{}} (q1);
  \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp)  .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp)  .. node[auto] {{}} (q5);
%
\end{tikzpicture}

%%% end ex3p1 %%%
}
\end{center}

Cet automate n'est pas déterministe : un automate comportant des
ε-transitions est forcément non-déterministe.

\smallbreak

(2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$
(car des transitions non spontanées y aboutissent) vont disparaître ;
les ε-fermetures $C(q)$ de ces états sont les suivantes :

\begin{center}
\begin{tabular}{r|l}
$q$&ε-fermeture $C(q)$\\
\hline
$0$&$\{0,1,3,4,5,13\}$\\
$2$&$\{1,2,3,4,5,13\}$\\
$6$&$\{6,7\}$\\
$8$&$\{5,8,9,10,12,13\}$\\
$11$&$\{5,10,11,12,13\}$\\
\end{tabular}
\end{center}

En remplaçant chaque transition $q^\sharp \to q'$ étiquetée
d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour
chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient le NFA
suivant :

\begin{center}
%%% begin ex3p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$};
  \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$};
  \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$};
  \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$};
  \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
  \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q11) to[loop above] node[auto] {$a$} (q11);
  \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp)  .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp)  .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp)  .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp)  .. node[auto,below] {$b$} (q6);
  \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp)  .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp)  .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp)  .. node[auto] {$a$} (q8);
%
\end{tikzpicture}

%%% end ex3p1b %%%
\end{center}

Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
leur ε-fermeture.

\smallbreak

(3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le
déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la
seule transition qui manque, c'est-à-dire une transition étiquetée par
$b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même
étiquetées $a$ et $b$).  Nous ne représentons pas l'automate à $6$
états ainsi fabriqué.

\smallbreak

(4) On part de l'algorithme déterministe complet obtenu à la
question (3), et on lui applique l'algorithme de minimisation.  On
sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et
les non-finaux $\{6,\bot\}$.  La transition étiquetée $a$ sépare les
états $6$ et $\bot$ car le premier aboutit dans la classe
$\{0,2,8,11\}$ tandis que le second aboutit dans la classe
$\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
états.  L'automate minimal est donc le suivant :
\begin{center}
%%% begin ex3p1c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$};
  \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$};
  \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$};
  \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$a$} (qF);
  \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$b$} (qbot);
  \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot);
  \draw [->] (qF) to[loop above] node[auto] {$a$} (qF);
  \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q6);
%
\end{tikzpicture}

%%% end ex3p1c %%%
\end{center}
où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.

\smallbreak

(5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$
consécutifs ni de $b$ final,
c'est-à-dire des mots dans lesquels chaque $b$ est suivi
d'au moins un $a$ : l'expression rationnelle initiale le présente
comme le langage constitués des mots formés d'un nombre quelconque de
$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au
moins un $a$.  L'automate final interdit les suites de deux $b$
consécutifs comme ceci : l'état $F$ correspond à la situation où on ne
vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou
bien on vient de commencer le mot) et on n'en a jamais rencontré deux,
l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en
a jamais rencontré deux, et l'état $\bot$ à la situation où on a
rencontré au moins une fois deux $b$ consécutifs.  Avec cette
description, il est clair que l'automate fait ce qui était demandé.
\end{corrige}


%
%
%

\exercice

Donner plusieurs (au moins trois) expressions rationnelles
équivalentes dénotant le langage reconnu par l'automate suivant sur
l'alphabet $\Sigma = \{a,b\}$ :

\begin{center}
%%% begin ex3p2 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$};
  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q2) to[loop right] node[auto] {$b$} (q2);
  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q0) to[loop left] node[auto] {$a$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
%
\end{tikzpicture}


%%% end ex3p2 %%%
\end{center}
(On pourra considérer les ordres suivants d'élimination des états :
(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.)

\begin{corrige}
(A) Si on commence par éliminer l'état $2$ (en considérant l'automate
comme un automate à transitions étiquetées par des expressions
rationnelles), l'état $1$ reçoit une transition vers lui-même
étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$,
qu'on peut fusionner avec la transition vers lui-même déjà existante
étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$.
Quitte éventuellement à ajouter un nouvel état initial (conduisant à
$0$ par une transition spontanée) et un nouvel état final (vers lequel
$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on
obtient finalement l'expression rationnelle
\[
(a|b(ab{*}a){*}b){*}
\]

\smallbreak

(B) Si on commence par éliminer l'état $1$, il apparaît une transition
$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
par $\bot$, symbole d'expression rationnelle qui dénote le lagange
vide, et l'expression rationnelle $\bot{*}$ est équivalente
à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit
lui aussi une transition vers lui-même (en passant par $1$) étiquetée
$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
existante étiquetée par $b$ pour obtenir une transition étiquetée
$b|aa$ ; de même, l'état $0$ reçoit une transition étiquetée $bb$,
qu'on peut fusionner avec celle existante pour obtenir $a|bb$.
L'élimination de l'état $2$ fait alors apparaître une transition de
$0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut fusionner avec
la transition vers lui-même déjà étiquetée par $a|bb$ pour une seule
étiquetée par $a|bb|ba(b|aa){*}ab$.  On obtient finalement
\[
(a|bb|ba(b|aa){*}ab){*}
\]
(en particulier, cette expression est équivalente à celle obtenue
précédemment).

\smallbreak

(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable
ajouter un nouvel état initial $I$ (conduisant à $0$ par une
transition spontanée) et un nouvel état final $F$ (vers lequel $0$
conduit par une transition spontanée).  L'élimination de l'état $0$
fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une
transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état
$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$
vers $F$ étiquetée $a{*}$.  L'élimination de l'état $2$ fait
apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$,
qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour
obtenir une transition $(ab{*}a|ba{*}b)$.  Finalement, l'élimination
de l'état $1$ done l'expression rationnelle
\[
a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
\]
(toujours équivalente aux précédentes).
\end{corrige}



%
%
%

\penalty-2000\vskip24ptplus600ptminus12pt
\centerline{\textbf{Langages algébriques et grammaires hors contexte}}
\penalty8000

\exercicenobreak

On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
sur l'alphabet $\Sigma = \{a,b\}$ :
\[
S \rightarrow aSS \;|\; b
\]
Soit $L = L(G)$ le langage algébrique qu'elle engendre.

(0) Donner quelques exemples de mots dans $L$.

(1) Expliquer pourquoi un $w\in \Sigma^*$ appartient à $L$ si et
seulement si : soit $w = b$, soit il existe $u,v\in L$ tels que $w =
auv$.

(2) En déduire par récurrence sur la longueur $|w|$ de $w$ que si $w
\in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$
(c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$).  Autrement
dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un
mot qui n'appartient jamais à $L$.  (Indication : si on a $auvz =
au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
(iii) $|u'|=|u|$.)

(3) En déduire que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
et $v=v'$.  (Indication analogue.)

(4) En déduire que $G$ est inambiguë, c'est-à-dire que chaque mot
$w\in L$ a un unique arbre d'analyse pour $G$ (on pourra reprendre
l'analyse de la question (1) et procéder de nouveau par récurrence
sur $|w|$).

(5) En s'inspirant des questions précédentes, décrire un algorithme
simple (en une seule fonction récursive) qui, donné un mot
$w\in\Sigma^*$ renvoie la longueur du préfixe de $w$ appartenant à $L$
s'il existe (il est alors unique d'après la question (2)) ou bien
« échec » s'il n'existe pas ; expliquer comment s'en servir pour
décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux
selon que $w\in L$ ou $w\not\in L$).

\begin{corrige}
(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
  $ababb$ ou encore $aabbabb$.

(1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$
  pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés
  selon l'une des deux règles de la grammaire, soit $S\rightarrow b$
  ou bien $S\rightarrow aSS$, autrement dit, soit elle a un unique
  fils étiqueté $b$, soit elle a trois fils étiquetés respectivement
  $a,S,S$.  Dans le premier cas, le mot $w$ est simplement $b$ ; dans
  le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour
  racine les deux fils étiquetés $S$ sont encore des arbres d'analyse
  pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des
  arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles
  de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de
  profondeur), alors on a $w = auv$ et $u,v\in L$ (puisqu'ils ont des
  arbres d'analyse pour $G$).

La réciproque est analogue : le mot $b$ appartient trivialement à $L$,
et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
\mathscr{V}$ pour $G$, et on peut fabriquer un arbre d'analyse pour $w
:= auv$ qui a une racine étiquetée $S$ ayant trois fils étiquetés
$a,S,S$, ces deux derniers ayant pour descendants des sous-arbres
donnés par $\mathscr{U}$ et $\mathscr{V}$.

\smallbreak

(2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz
\not\in L$ pour tout $z \in \Sigma^+$.  La récurrence permet de
supposer la conclusion déjà connue pour tout mot de longueur $<|w|$.
D'après la question (1), le mot $w$ est soit $b$ soit de la forme
$auv$ avec $u,v\in L$ et trivialement $|u|<|w|$ et $|v|<|w|$.  Si
$w=b$, il est évident qu'aucun mot de la forme $bz$ ne peut appartenir
à $L$ (la question (1) montre que les seuls mots de $L$ sont le mot
$b$ et des mots commençant par $a$).  Il reste le cas $w = auv$ : on
veut montrer que $wz$, c'est-à-dire $auvz$, n'appartient pas à $L$.
Mais s'il y a appartenait, toujours d'après la question (1), il serait
de la forme $au'v'$ (le cas $b$ étant trivialement exclu), où $u',v'
\in L$ ; notamment, $uvz = u'v'$.  Distinguons trois cas : (i) soit
$|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, c'est-à-dire
que $u'$ peut s'écrire sous la forme $u' = ut$ pour un $t\in
\Sigma^+$, et par l'hypothèse de récurrence, on a $u'\not\in L$, une
contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
u't$ pour un $t\in\Sigma^+$, et par l'hypothèse de récurrence (puisque
$|u'|<|u|<|w|$), on a $u\not\in L$, de nouveau une contradiction ;
(iii) soit $|u'|=|u|$, donc $u'=u$ (puisqu'ils sont préfixes de même
longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais
comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$,
encore une contradiction.

\smallbreak

(3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
et $v=v'$.  On a notamment $uv = u'v'$.  Distinguons trois cas :
(i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$,
c'est-à-dire que $u'$ peut s'écrire sous la forme $u' = ut$ pour un
$t\in \Sigma^+$, et par la question (2), on a $u'\not\in L$, une
contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
u't$ pour un $t\in\Sigma^+$, et par la question (2), on a $u\not\in
L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$
(puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$),
et on a alors $v' = v$, la conclusion annoncéee.

\smallbreak

(4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse
pour $G$.  On procède par récurrence sur $|w|$, ce qui permet de
supposer la conclusion connue pour tout mot de longueur $<|w|$.  Comme
on l'a expliqué en (1), il y a deux possibilités pour un arbre
d'analyse de $w$ : soit la racine a un unique fils étiqueté $b$ et le
mot analysé est $w=b$, soit la racine a trois fils étiquetés $a,S,S$,
et des deux derniers fils partent des arbres d'analyse
$\mathscr{U},\mathscr{V}$ de mots $u,v\in L$ tels que $w=auv$.  Ces
deux cas sont évidemment incompatibles : il reste donc simplement à
expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont
uniquement déterminés.  Or la question (3) assure que $u,v$ (tels que
$w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence
permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres
d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement
déterminés, comme on le voulait.

\smallbreak

(5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe
  dans $L$ » suivante renvoie la longueur du préfixe de $w$
appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
\begin{itemize}
\item si $w=\varepsilon$, renvoyer échec,
\item si la première lettre de $w$ est $b$, renvoyer $1$,
\item sinon (la première lettre de $w$ est $a$), soit $x$ le suffixe
  de $w$ correspondant (c'est-à-dire $w = ax$, ou si on préfère, $x$
  enlève la première lettre de $w$),
\item appeler la fonction elle-même (rechercher préfixe dans $L$)
  sur $x$ :
\item si elle échoue, renvoyer échec,
\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur
  $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, ou si
  on préfère, $y$ enlève les $k$ premières lettres de $x$),
\item appeler la fonction elle-même (rechercher préfixe dans $L$)
  sur $y$ :
\item si elle échoue, renvoyer échec,
\item si elle retourne $\ell$, retourner $1+k+\ell$ (en effet, on a $w
  = auvz$ où $u$ est de longueur $k$ et $v$ est de longueur $\ell$).
\end{itemize}

Pour savoir si un mot appartient à $w$, il s'agit simplement de
vérifier que la valeur retournée (=la longueur du préfixe appartenant
à $L$) n'est pas un échec et est égale à la longueur $|w|$.

La terminaison de cet algorithme est claire par récurrence sur la
longueur (chaque appel récursif est fait sur un mot de longueur
strictement plus courte), et sa correction est garantie par les
questions précédentes : les cas $b$ et $auv$ sont disjoints et dans le
dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce
qu'affirme la non-ambiguïté de la grammaire).

(Il s'agit ici du cas le plus simple d'un analyseur LL, et
l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1)
camouflé sous forme d'analyseur par descente récursive.)
\end{corrige}


%
%
%

\exercice

On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
sur l'alphabet $\Sigma = \{a,b\}$ :
\[
S \rightarrow SaS \;|\; b
\]
Soit $L = L(G)$ le langage algébrique qu'elle engendre.

(0) Donner quelques exemples de mots dans $L$.

(1) Cette grammaire $G$ est-elle ambiguë ?

(2) Décrire simplement le langage $L$.

(3) Donner une grammaire inambiguë engendrant le même langage $L$
que $G$.

\begin{corrige}
(0) Quelques exemples de mots dans $L$ sont $b$, $bab$, $babab$, et
  ainsi de suite (cf. (2)).

(1) La grammaire $G$ est ambiguë : le mot $babab$ a deux arbres
  d'analyse différents, à savoir
\begin{center}
\tikzstyle{automaton}=[scale=0.5]
%%% begin ex3pt1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (S3) at (27bp,90bp) [draw,draw=none] {$S$};
  \node (S2) at (243bp,162bp) [draw,draw=none] {$S$};
  \node (S1) at (99bp,162bp) [draw,draw=none] {$S$};
  \node (S0) at (171bp,234bp) [draw,draw=none] {$S$};
  \node (S4) at (171bp,90bp) [draw,draw=none] {$S$};
  \node (a1) at (99bp,90bp) [draw,draw=none] {$a$};
  \node (a0) at (171bp,162bp) [draw,draw=none] {$a$};
  \node (b0) at (243bp,90bp) [draw,draw=none] {$b$};
  \node (b1) at (27bp,18bp) [draw,draw=none] {$b$};
  \node (b2) at (171bp,18bp) [draw,draw=none] {$b$};
  \draw [] (S1) ..controls (70.042bp,132.85bp) and (55.714bp,118.92bp)  .. (S3);
  \draw [] (S0) ..controls (142.04bp,204.85bp) and (127.71bp,190.92bp)  .. (S1);
  \draw [] (S0) ..controls (171bp,204.85bp) and (171bp,190.92bp)  .. (a0);
  \draw [] (S2) ..controls (243bp,132.85bp) and (243bp,118.92bp)  .. (b0);
  \draw [] (S1) ..controls (99bp,132.85bp) and (99bp,118.92bp)  .. (a1);
  \draw [] (S0) ..controls (199.96bp,204.85bp) and (214.29bp,190.92bp)  .. (S2);
  \draw [] (S3) ..controls (27bp,60.846bp) and (27bp,46.917bp)  .. (b1);
  \draw [] (S4) ..controls (171bp,60.846bp) and (171bp,46.917bp)  .. (b2);
  \draw [] (S1) ..controls (127.96bp,132.85bp) and (142.29bp,118.92bp)  .. (S4);
%
\end{tikzpicture}

%%% end ex3pt1 %%%
\end{center}
et son symétrique par rapport à l'axe vertical.

\smallbreak

(2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par
l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse
entrevoir.  Pour cela, il suffit de voir que l'ensemble des
pseudo-mots (:= mots sur l'ensemble des terminaux et des nonterminaux)
qu'on peut dériver de $S$ dans $G$ est le langage $((S|b)a){*}(S|b)$
constitué des pseudo-mots de la forme $xaxax\cdots ax$ où chaque $x$
est soit un $S$ soit un $b$, indépendamment les uns des autres.  Or il
est clair que remplacer un $x$ (et notamment, remplacer un $S$) par
$SaS$ (qui est de la forme $xax$) dans un pseudo-mot de cette forme
donne encore un pseudo-mot de cette forme : ceci montre qu'une
dérivation de $G$, quelle que soit l'application faite de la règle
$S\rightarrow SaS$, donne des pseudo-mots de cette forme, donc tout
pseudo-mot obtenu par dérivation de $S$ dans la grammaire $G$ est de
la forme qu'on vient de dire ; et réciproquement, il est facile de
produire n'importe quel nombre $n$ de répéritions du motif $aS$ en
appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on
peut ensuite librement transformer certains $S$ en $b$.

\smallbreak

(3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le
même langage que $G$ d'après la question précédente ; et il est
évident que cette grammaire est inambiguë : toutes les dérivations
sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
(ba)^n S$ suivie éventuellement de $\Rightarrow (ba)^n b$.
\end{corrige}



%
%
%

\penalty-2000\vskip24ptplus600ptminus12pt
\centerline{\textbf{Calculabilité}}
\penalty8000

\exercicenobreak

(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
= \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?

(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
est-il décidable ?  Semi-décidable ?

(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
de l'arrêt.)

\begin{corrige}
(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
  de l'algorithme suivant pour décider si $w\in L$ : si
  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
  commençant à la position $i \ell$) : s'ils sont tous égaux, renvoyer
  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
    fortiori} semi-décidable).

\smallbreak

(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
  évidemment calculable.  On peut ensuite lancer l'exécution du
  $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
  exemple, en simulant la $e$-ième machine de Turing sur une machine
  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
  est bien décidable (et \textit{a fortiori} semi-décidable).

\smallbreak

(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
  différence est que le problème de l'arrêt est l'ensemble des couples
  $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
  que cette limitation ne rend pas pour autant calculable l'ensemble
  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
  un tel $e'$ se calcule algorithmiquement\footnote{Techniquement, on
    invoque ici le théorème s-m-n ; mais dans les faits, il s'agit
    essentiellement d'ajouter une ligne « \texttt{let
      n=}(représentation décimale de $n$) » au début d'un programme,
    ce qui est certainement faisable.} à partir de $e$ et $n$.
  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
  autre entrée) se comporte donc comme l'exécution du programme $e$
  sur l'entrée $n$, et notamment, termine si et seulement si elle
  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
  dans cette question si et seulement si $(e,n)$ appartient au
  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
  semi-décidable : il suffit de lancer l'exécution du programme $e$
  sur l'entrée $42$ et renvoyer vrai si elle termine (si elle ne
  termine pas, on ne termine pas).
\end{corrige}


%
%
%

\exercice

Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
des langages sur $\Sigma$.

(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors
$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer
que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce
dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un
mot de longueur $n$, comment énumérer toutes les façons de le
factoriser en mots de longueur non nulle).

(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
semi-décidables ; montrer que si un langage $L$ est semi-décidable
alors $L^*$ est semi-décidable.

\begin{corrige}
(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
  $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$,
  l'algorithme $T_i$ termine toujours en temps fini, en répondant oui
  si $w\in L_i$ et non si $w\not\in L_i$).

Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot
$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si
l'un des deux répond oui, on répond oui, sinon on répond non
(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et
$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur
« ou » logique).  De même pour décider $L_1\cap L_2$, il suffit de
lancer successivement $T_1$ et $T_2$, si les deux répondent oui on
répond oui, sinon on répond non (i.e., on calcule les valeurs de
vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on
calcule ensuite leur « et » logique).

Pour décider $L_1 L_2$, on effectue une boucle sur toutes les
factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les
longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe
de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$,
et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$
pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine
l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune
paire ne convient, on répond non.

L'algorithme pour décider $L^*$ est semblable : il s'agit de tester
toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs
de longueur non nulle.  (On peut d'ores et déjà exclure
$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.)
Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de
facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
boucles emboîtées pour déterminer les limites des facteurs
$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
lorsque $i_1+\cdots+i_k = n$, appeler $u_j$ le facteur de $w$ de
longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$).  Pour
chaque factorisation comme on vient de le dire, on teste si tous les
$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on
renvoie faux.

(Dans l'algorithme qui précède, on a écarté les factorisations faisant
intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en
faisant intervenir le mot vide, quitte à retirer celui-ci, il est
encore factorisable en mots non vides de $L$.)

\smallbreak

(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
terminer.  À part pour l'intersection, on doit donc les lancer « en
parallèle » et pas « en série » : lorsqu'on dira qu'on lance deux
algorithmes $T$ et $T'$ « en parallèle », cela signifie qu'on exécute
une étape du calcul de $T$, puis une étape de $T'$, puis de nouveau
une de $T$, et ainsi de suite en alternant entre les deux, jusqu'à ce
que l'un termine et renvoie vrai.

Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps
fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour
semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et
$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on
termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).

Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
calcul dans son ensemble ne terminera pas.

Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A)
en lançant en parallèle les algorithmes pour tester toutes les
différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots
u_k$ (en mots non vides) du mot $w$.
\end{corrige}

%
%
%

\exercice

On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
programme pour une machine de Turing) prenant en entrée un
$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
change rien).

Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
équivalence entre les affirmations suivantes :
\begin{enumerate}
\item la fonction $f$ est calculable,
\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
\end{enumerate}

(Montrer que (3) implique (1) est le plus difficile : on pourra
commencer par s'entraîner en montrant que (2) implique (1).  Pour
montrer que (3) implique (2), on pourra chercher une façon de tester
en parallèle un nombre croissant de valeurs de $p$ de manière à
s'arrêter si l'une quelconque convient.)

\begin{corrige}
Montrons que (1) implique (2) : si on dispose d'un algorithme capable
de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
algorithme capable de décider si $p=f(n)$ (il suffit de calculer
$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
faux/$0$ sinon).

Le fait que (2) implique (3) est évident car tout ensemble décidable
est semi-décidable.

Montrons que (2) implique (1) même si ce ne sera au final pas utile :
supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
de $T$.

\smallbreak

Reste à montrer que (3) implique (1) : supposons qu'on ait un
algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
termine en temps fini et répond oui si $p=f(n)$, et ne termine pas
sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
et faire tendre $M$ vers l'infini : plus exactement, on utilise
l'algorithme $U$ suivant :
\begin{itemize}
\item pour $M$ allant de $0$ à l'infini,
\begin{itemize}
\item pour $p$ allant de $0$ à $M$,
\begin{itemize}
\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
  plus $M$ étapes,
\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
  (sinon, continuer les boucles).
\end{itemize}
\end{itemize}
\end{itemize}

(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
valeurs de $p$ de plus en plus grand et en attendant de plus en plus
longtemps pour voir si l'une d'elles termine.)

Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
et on renvoie la valeur en question) ; il reste à expliquer pourquoi
$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
connaît pas) car la fonction $f$ était supposée définie partout, et
lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
prise par $p$ dans la boucle intérieure, et pour cette valeur,
l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
étapes, ce qui assure que $U$ termine effectivement.

L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
prouve (1).
\end{corrige}

%
%
%

\exercice

Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
équivalence entre :
\begin{itemize}
\item l'ensemble $A$ est décidable,
\item il existe une fonction calculable \emph{strictement croissante}
  $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$.
\end{itemize}

\begin{corrige}
Supposons $A$ décidable : on va construire $f$ comme indiqué.  Plus
exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre
croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$,
et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter
que $A$ est infini donc cette fonction est bien définie).  Montrons
que $f$ est calculable : donné un entier $n$, on teste successivement
si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque
fois en utilisant un algorithme décidant $A$ (qui est censé exister
par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus
exactement :
\begin{itemize}
\item initialiser $m \leftarrow 0$,
\item pour $k$ allant de $0$ à l'infini,
\begin{itemize}
\item interroger l'algorithme qui décide si $k\in A$,
\item s'il répond « oui » :
\begin{itemize}
\item si $m=n$, terminer et renvoyer $k$,
\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$).
\end{itemize}
\end{itemize}
\end{itemize}
La boucle termine car $A$ est infini.

Réciproquement, supposons $f$ strictement croissante calculable et
posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable.
Or pour décider si $k \in A$, il suffit de calculer successivement
$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$
atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a
trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a
été sautée par la fonction $f$ et ne sera donc jamais atteinte).
L'algorithme est donc explicitement :
\begin{itemize}
\item pour $n$ allant de $0$ à l'infini,
\begin{itemize}
\item calculer $f(n)$,
\item si $f(n) = k$, renvoyer vrai,
\item si $f(n) > k$, renvoyer faux.
\end{itemize}
\end{itemize}
La boucle termine car toute fonction strictement croissante
$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc
$f(n)$ finit forcément par atteindre ou dépasser $k$).
\end{corrige}

%
%
%

\exercice

Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
fournit le nombre $n$ en entrée, à supposer que cette exécution
termine ; sinon, $S(e,n)$ n'est pas défini.

Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
terminent.

Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
calculable par un algorithme) : on pourra pour cela montrer que la
connaissance de $M$ permet de résoudre le problème de l'arrêt.
Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
M(k)$ pour tout $k$ n'est calculable.  Montrer que même si $M'$
vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
pas calculable.

\emph{Remarque :} La fonction $M$, ou différentes variantes de
celle-ci, s'appelle fonction du « castor affairé ».  On peut montrer
encore plus fort : si $F$ est une fonction calculable quelconque,
alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$
(autrement dit, la fonction $M$ finit par dépasser n'importe quelle
fonction calculable : Radó, 1962, \textit{On Non-Computable
  Functions}).

\begin{corrige}
Supposons que $M$ soit calculable.  On peut alors résoudre le problème
de l'arrêt de la manière suivante : donné un algorithme $T$, de
numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
faux (il ne terminera jamais).  Cette résolution du problème de
l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
$M(k)$ étapes, il ne terminera jamais.

Exactement le même argument montre que $M'$ n'est pas calculable sous
l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
convient.

Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
changer la valeur en un point d'une fonction calculable donne toujours
une fonction calculable (même si on « ne connaît pas » la valeur à
changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
partout supérieure ou égale à $M$.
\end{corrige}


%
%
%
\end{document}