summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex296
1 files changed, 294 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 1ac129e..6e8df9b 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -6088,7 +6088,7 @@ construits (et éventuellement les arbres eux-mêmes).
\subsection{Présentation générale}
\thingy\textbf{Discussion préalable.} On s'intéresse ici à la question
-de savoir ce qu'un \defin{algorithme} peut ou ne peut pas faire.
+de savoir ce qu'un \defin[algorithme (en calculabilité)]{algorithme} peut ou ne peut pas faire.
Pour procéder de façon rigoureuse, il faudrait formaliser la notion
d'algorithme (par exemple à travers le concept de machine de Turing) :
on a préféré rester informel sur cette définition — par exemple « un
@@ -6266,7 +6266,7 @@ temps fini, et calcule (renvoie) $f(n)$.
\smallskip
On dit qu'un ensemble $A \subseteq \mathbb{N}$ (un « langage »,
-cf. \ref{computability-all-data-are-integers}) est \defin{décidable}
+cf. \ref{computability-all-data-are-integers}) est \defin[décidable (langage)]{décidable}
(ou \index{calculable (langage)|see{décidable}}« calculable » ou
\index{récursif (langage)|see{décidable}}« récursif ») lorsque sa
fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$
@@ -7766,6 +7766,243 @@ l'expression.)
\end{corrige}
%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.
+
+On considère l'expression rationnelle $r$ suivante : $(ab|ba){*}$ (sur
+l'alphabet $\Sigma$). On appelle $L := L(r)$ le langage qu'elle
+dénote.
+
+(0) Donner quatre exemples de mots de $L$ et quatre exemples de mots
+n'appartenant pas à $L$.
+
+\begin{corrige}
+Par exemple, les mots $\varepsilon$, $ab$, $ba$ et $abba$
+appartiennent à $L$. Les mots $a$, $b$, $aa$ et $aba$ n'appartiennent
+pas à $L$.
+\end{corrige}
+
+(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.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ obtenu est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto,below] {$b$} (S3);
+\draw [->] (S2) -- node[auto] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\end{tikzpicture}
+\end{center}
+C'est l'automate de Glushkov. Si on commence par construire
+l'automate de Thompson, on obtient le suivant (à $12$ états) :
+\begin{center}
+\scalebox{0.70}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {};
+\node (S0u) at (60bp,0bp) [draw,circle,state] {};
+\node (S0a) at (120bp,40bp) [draw,circle,state] {};
+\node (S1) at (180bp,40bp) [draw,circle,state] {};
+\node (S1u) at (240bp,40bp) [draw,circle,state] {};
+\node (S3) at (300bp,40bp) [draw,circle,state] {};
+\node (S0b) at (120bp,-40bp) [draw,circle,state] {};
+\node (S2) at (180bp,-40bp) [draw,circle,state] {};
+\node (S2u) at (240bp,-40bp) [draw,circle,state] {};
+\node (S4) at (300bp,-40bp) [draw,circle,state] {};
+\node (SF) at (360bp,0bp) [draw,circle,state] {};
+\node (SFu) at (420bp,0bp) [draw,circle,state,final] {};
+\draw [->] (S0) -- (S0u);
+\draw [->] (S0u) -- (S0a);
+\draw [->] (S0a) -- node[auto] {$a$} (S1); \draw [->] (S1) -- (S1u);
+\draw [->] (S1u) -- node[auto] {$b$} (S3); \draw [->] (S3) -- (SF);
+\draw [->] (S0u) -- (S0b);
+\draw [->] (S0b) -- node[auto] {$b$} (S2); \draw [->] (S2) -- (S2u);
+\draw [->] (S2u) -- node[auto] {$a$} (S4); \draw [->] (S4) -- (SF);
+\draw [->] (SF) -- (SFu);
+\draw [->] (SF) to[out=90,in=0] (210bp,70bp) to[out=180,in=90] (S0u);
+\draw [->] (S0) to[out=270,in=180] (120bp,-70bp) -- (300bp,-70bp) to[out=0,in=270] (SFu);
+\end{tikzpicture}
+}
+\end{center}
+(où toutes les flèches non étiquetées sont des transitions spontanées,
+c'est-à-dire qu'il faut les imaginer étiquetées par $\varepsilon$) qui
+par élimination des transitions spontanées donne celui $\mathscr{A}_1$
+qu'on a tracé au-dessus (les seuls états qui subsistent après
+élimination des transitions spontanées sont l'état initial et les
+quatre états auxquels aboutissent une transition non spontanée).
+\end{corrige}
+
+(2) À partir de $\mathscr{A}_1$, construire un automate fini
+déterministe complet reconnaissant $L$. On appellera $\mathscr{A}_2$
+l'automate en question.
+
+\begin{corrige}
+L'automate $\mathscr{A}_1$ est déterministe incomplet : il s'agit donc
+simplement de lui ajouter un état « puits » pour le rendre complet, ce
+qui donne l'automate $\mathscr{A}_2$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (S3) at (150bp,35bp) [draw,circle,state,final] {$3$};
+\node (S4) at (150bp,-35bp) [draw,circle,state,final] {$4$};
+\node (Sink) at (220bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) -- node[auto,near end] {$a$} (S1);
+\draw [->] (S0) -- node[auto,below] {$b$} (S2);
+\draw [->] (S1) -- node[auto] {$b$} (S3);
+\draw [->] (S2) -- node[auto,below] {$a$} (S4);
+\draw [->] (S3) -- node[auto,above,very near end] {$b$} (S2);
+\draw [->] (S4) -- node[auto,very near end] {$a$} (S1);
+\draw [->] (S3) to[out=135,in=45] node[auto,above] {$a$} (S1);
+\draw [->] (S4) to[out=225,in=315] node[auto] {$b$} (S2);
+\draw [->] (S1) -- node[auto,very near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,very near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] 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 canonique ainsi obtenu.
+
+(On obtient un automate ayant $4$ états.)
+
+\begin{corrige}
+L'algorithme de minimisation identifie les trois états finaux
+($0,3,4$) de l'automate $\mathscr{A}_2$, ce qui donne
+l'automate $\mathscr{A}_3$ suivant (on note $0$ pour l'état résultant
+de l'identification de $0,3,4$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
+:= \Sigma^*\setminus L$ complémentaire de $L$.
+
+\begin{corrige}
+L'automate $\mathscr{A}_3$ étant un automate fini déterministe complet
+reconnaissant $L$, il suffit de marquer finaux les états non-finaux et
+vice versa pour obtenir l'automate $\mathscr{A}_4$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state,final,accepting above] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state,final,accepting below] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state,final,accepting below] {$\bot$};
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop right] node[auto] {$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des
+états, déterminer une expression rationnelle dénotant le langage $M$.
+
+\begin{corrige}
+Pour appliquer la méthode d'élimination des états, on commence par
+modifier l'automate pour avoir un unique état initial $I$, qui ne soit
+pas final, et qui n'ait aucune transition qui y aboutisse, et un
+unique état final $F$, qui ne soit pas initial, et sans aucune
+transition qui en part :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (Sink) at (140bp,0bp) [draw,circle,state] {$\bot$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) -- node[auto,near end] {$a$} (Sink);
+\draw [->] (S2) -- node[auto,below,near end] {$b$} (Sink);
+\draw [->] (Sink) to[loop above] node[auto] {$a|b$} (Sink);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\underline{\varepsilon}$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\underline{\varepsilon}$} (SF);
+\draw [->] (Sink) -- node[auto] {$\underline{\varepsilon}$} (SF);
+\end{tikzpicture}
+\end{center}
+On élimine ensuite l'état $\bot$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
+\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) to[out=75,in=180] node[auto,near end] {$a$} (S1);
+\draw [->] (S0) to[out=285,in=180] node[auto,below] {$b$} (S2);
+\draw [->] (S1) to[out=270,in=15] node[auto,above] {$b$} (S0);
+\draw [->] (S2) to[out=90,in=345] node[auto] {$a$} (S0);
+\draw [->] (S1) to[out=15,in=135] node[auto,near end] {$\underline{\varepsilon}|a(a|b){*}$} (SF);
+\draw [->] (S2) to[out=345,in=225] node[auto,near end] {$\underline{\varepsilon}|b(a|b){*}$} (SF);
+\end{tikzpicture}
+\end{center}
+Puis les états $1$ et $2$ peuvent être éliminés simultanément :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (SI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (S0) at (0bp,0bp) [draw,circle,state] {$0$};
+\node (SF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (SI) -- node[auto] {$\underline{\varepsilon}$} (S0);
+\draw [->] (S0) -- node[auto] {$a(\underline{\varepsilon}|a(a|b){*})|b(\underline{\varepsilon}|b(a|b){*})$} (SF);
+\draw [->] (S0) to[loop above] node[auto] {$ab|ba$} (S0);
+\end{tikzpicture}
+\end{center}
+Et l'expression rationnelle finalement obtenue est la suivante :
+\[
+(ab|ba){*}(a(\underline{\varepsilon}|a(a|b){*})|b(\underline{\varepsilon}|b(a|b){*}))
+\]
+On pouvait aussi donner, entre autres choses :
+\[
+(ab|ba){*}(a|aa(a|b){*}|b|bb(a|b){*})
+\]
+(obtenue en éliminant les états $1$ et $2$ avant $\bot$).
+\end{corrige}
+
+%
%
%
@@ -8666,6 +8903,61 @@ sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow
\exercice
+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\footnote{Une
+ variante consiste à considérer l'ensemble des $e$ tels que $e$
+ termine sur l'entrée $e$ : l'ensemble $H$ qu'on vient de définir s'y
+ ramène facilement.}.
+
+On considère l'ensemble $H'$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ \emph{ou bien} $(e_2,x) \in H$ (ou les deux).
+Autrement dit, au moins l'un des programmes $e_i$ termine en temps
+fini quand on l'exécute sur l'entrée $x$.
+
+(1) L'ensemble $H'$ est-il semi-décidable ?
+
+\begin{corrige}
+Nous allons montrer que $H'$ est semi-décidable.
+
+Considérons l'algorithme suivant : donné en entrée un triplet
+$(e_1,e_2,x)$, on exécute en parallèle, en fournissant à chacun
+l'entrée $x$, les programmes (codés par) $e_1$ et $e_2$ (au moyen
+d'une machine universelle), et en s'arrêtant immédiatement si l'un des
+deux s'arrête, et on renvoie alors « vrai ». Manifestement, cet
+algorithme termine (en renvoyant « vrai ») si et seulement si
+$(e_1,e_2,x) \in H'$, ce qui montre que $H'$ est semi-décidable.
+\end{corrige}
+
+(2) L'ensemble $H'$ est-il décidable ?
+
+\begin{corrige}
+Nous allons montrer que $H'$ n'est pas décidable.
+
+Supposons par l'absurde qu'il existe un algorithme $T$ qui
+décide $H'$. Soit $e'$ (le code d')un programme quelconque qui
+effectue une boucle infinie (quelle que soit son entrée) : comme $e'$
+ne termine jamais, un triplet $(e,e',x)$ appartient à $H'$ si et
+seulement si $(e,x)$ appartient à $H$. Considérons maintenant
+l'algorithme suivant : donné en entrée un couple $(e,x)$, on applique
+l'algorithme $T$ supposé exister pour décider si $(e,e',x) \in H'$ ;
+comme on vient de l'expliquer, ceci équivaut à $(e,x) \in H$. On a
+donc fabriqué un algorithme qui décide $H$, ce qui est impossible,
+d'où la contradiction annoncée.
+\end{corrige}
+
+%
+
+\exercice
+
Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions
suivantes sont indépendantes (mais on remarquera leur parallélisme).
Ne pas hésiter à décrire les algorithmes de façon succincte et