diff options
| -rw-r--r-- | notes-inf105.tex | 296 |
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 |