diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 390 |
1 files changed, 349 insertions, 41 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 1ac129e..b56b958 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1167,7 +1167,7 @@ L'extension la plus fréquente est celle des \emph{références arrière} facteur du mot se retrouve aussi à un autre emplacement. Par exemple, pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage -$\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots +$\{a^nba^n : n\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la \emph{même suite de $a$} (le « \texttt{\char"5C\relax 1} » désigne « une copie de la chaîne de caractères qui a été capturée par le @@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher « \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début -de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le +de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le \texttt{a} soit à la fin de la chaîne donnée, et rechercher « \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée soit exactement \texttt{a} (cet exemple n'est donc pas très utile, @@ -1547,7 +1547,7 @@ accepte exactement les mots contenant un $a$ suivi, pas forcément immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un sous-mot (cf. \ref{definition-subword}). Ce langage est donc reconnaissable. (Il est aussi rationnel puisque dénoté par -l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) +l'expression rationnelle $(b|c){*}a(a|c){*}b(a|b|c){*}$.) \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA est dit \defin[accessible (état)]{accessible} lorsqu'il existe un mot @@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe -de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$, -puis en éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$ -et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui -vient d'être dit.) +de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$ +(qui cessent d'être initiaux), puis en éliminant les ε-transitions +qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi +que les états $q_1$ et $q_2$ devenus inutiles. Cela donne le même +résultat que ce qui vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un @@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant chaque transition sortant de $q_2$ par une transition identiquement étiquetée, et de même cible, partant de \emph{chaque} état final -de $A_1$. Graphiquement : +de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final +dans $A_2$). Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2852,19 +2853,20 @@ et De façon plus formelle, considérons un nouvel ensemble d'états $Q' = (Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion disjointe. On définit alors l'automate $A'$ dont l'ensemble d'états -est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la -relation de transition $\delta$ est la réunion de $\delta_1$, de -l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, -et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') -\in \delta_2$ et que $q\in F_1$. +est $Q'$, l'état initial est $q_1$, l'ensemble $F'$ des états finaux +est $F_2$ si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si +$q_2$ était final dans $A_2$, la relation de transition $\delta'$ +est la réunion de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in +\delta_2$ tels que $q\neq q_2$, et enfin de l'ensemble des triplets +$(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une -ε-transition de chaque état final de $A_1$ vers $q_2$, puis en -éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$ -devenu inutile. Cela donne le même résultat que ce qui vient d'être -dit.) +ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse +d'être initial), puis en éliminant les ε-transitions qu'on vient +d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état +$q_2$ devenu inutile. Cela donne le même résultat que ce qui vient +d'être dit.) Il est alors clair qu'un chemin de l'état initial $q_1$ à un état final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état @@ -3639,21 +3641,35 @@ Symboliquement : \end{tikzpicture} \end{center} -Cette transformation doit être effectuée \emph{simultanément pour - toute paire} $(q_1,q_2)$ d'états de $A$ pour laquelle -$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque -telle paire, on remplace l'étiquette de la transition $r_{12}$ entre -eux par $(r_{12}|r_1(s){*}r_2)$. Ceci ne change pas le fonctionnement -de l'automate, car tout chemin dans $A$ peut être remplacé par un -chemin dans $A'$ en effaçant simplement les $q$ (si on considère -$q_1$ et $q_2$ les états avant un bloc de $q$ dans le chemin, on -voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se -transformer en $q_1 \to q_2$ en consommant un mot qui vérifie -l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). - -En éliminant (dans n'importe quel ordre) tous les états autres que -$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique -transition $(q_0,r,q_\infty)$, qui est donc essentiellement +Pour éliminer l'état $q$, cette transformation doit être effectuée +\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec +$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il +existe une transition de $q_1$ vers $q$ et une transition de +$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une +transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ : +pour \emph{chaque} telle paire, on remplace l'étiquette de la +transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$. (On +prendra garde aux cas particuliers suivants : si la transition de $q$ +vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors +on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du +fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et +si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à +prendre $r_{12}=\bot$, alors on la crée avec l'étiquette +$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers, +s'il n'y avait ni transition de $q$ vers lui-même ni de +$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.) + +La transformation qui vient d'être décrite ne change pas le +fonctionnement de l'automate, car tout chemin dans $A$ peut être +remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on +considère $q_1$ et $q_2$ les états avant un bloc de $q$ dans le +chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to +q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui +vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$). + +En éliminant (successivement dans n'importe quel ordre) tous les états +autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant +une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement l'expression rationnelle $r$. \end{proof} @@ -4271,7 +4287,7 @@ Voici comment on peut le mettre en œuvre de façon plus concrète : état inaccessible}} (si nécessaire, déterminiser l'automate s'il n'est pas déterministe, le compléter s'il est incomplet, et supprimer les états inaccessibles s'il y en a) ; -\item appeler $\Pi$ la partition des automates en deux classes : les +\item appeler $\Pi$ la partition des états en deux classes : les états finaux d'un côté, et les non-finaux de l'autre ; \item répéter l'opération suivante tant que la partition $\Pi$ change : pour chaque classe $C$ de $\Pi$ et chaque lettre $x \in @@ -5028,7 +5044,7 @@ langage $L(G)$ que la précédente (elle est donc faiblement équivalente l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire (d'axiome $S$) \[ \begin{aligned} -S &\rightarrow U \;|\; V \;|\; \varepsilon\\ +S &\rightarrow U \;|\; V\\ U &\rightarrow aUb \;|\; ab\\ V &\rightarrow aVbb \;|\; abb\\ \end{aligned} @@ -5154,8 +5170,8 @@ Un raisonnement analogue montre que la grammaire $G'$ donnée par \[ \begin{aligned} S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\ -U &\rightarrow aUbU\\ -V &\rightarrow bVaV\\ +U &\rightarrow aUbU \;|\; \varepsilon\\ +V &\rightarrow bVaV \;|\; \varepsilon\\ \end{aligned} \] engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que @@ -6088,7 +6104,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 +6282,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 +7782,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 +8919,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 @@ -8950,7 +9258,7 @@ 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 +tester : si $T_1$ termine, on lance ensuite $T_2$ 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. |