summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20190328.tex91
-rw-r--r--notes-inf105.tex296
2 files changed, 372 insertions, 15 deletions
diff --git a/controle-20190328.tex b/controle-20190328.tex
index e3e1391..5632c1e 100644
--- a/controle-20190328.tex
+++ b/controle-20190328.tex
@@ -46,7 +46,7 @@
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
-\corrigetrue
+\corrigefalse
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
@@ -84,7 +84,10 @@
\noindent\textbf{Consignes.}
-\textcolor{red}{À remplir}
+Les exercices sont indépendants. Il est recommandé de les traiter
+dans l'ordre du sujet, mais ce n'est pas nécessaire ; cependant, on
+demande de faire apparaître de façon très visible dans les copies où
+commence chaque exercice.
\medbreak
@@ -97,12 +100,12 @@ L'usage des appareils électroniques est interdit.
Durée : 1h30
-Barème \emph{indicatif} : \textcolor{red}{xxx}.
+Barème \emph{indicatif} : 11+4+5.
\ifcorrige
Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse)
\else
-Cet énoncé comporte \textcolor{red}{xxx} pages (page de garde incluse)
+Cet énoncé comporte 3 pages (page de garde incluse)
\fi
\vfill
@@ -120,7 +123,7 @@ Git: \input{vcline.tex}
%
%
-\exercice
+\exercice\label{exercise-on-finite-automata}
Dans cet exercice, on pose $\Sigma = \{a,b\}$.
@@ -130,7 +133,7 @@ expression rationnelle $r_1$ dénotant le langage $L_1$.\quad(b) Donner
l'automate fini déterministe complet minimal $\mathscr{A}_1$
reconnaissant $L_1$ (on pourra préalablement passer par d'autres
sortes d'automates comme étapes intermédiaires ; pour obtenir la
-totalité des points, on passera impérativement par des constructions
+totalité des points, on utilisera impérativement des constructions
vues en cours, qu'on précisera).
\emph{Information :} L'automate $\mathscr{A}_1$ correct a trois états.
@@ -154,7 +157,7 @@ Même conseil que ci-dessus.
(3) Soit $L_3 = L_2^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L_2\}$ le
langage miroir de $L_2$, c'est-à-dire le langage formé des mots
-miroirs des mots de $L_2$ (on rappelle que le mot « moir »
+miroirs des mots de $L_2$ (on rappelle que le mot « miroir »
$w^{\mathsf{R}}$ d'un mot $w$ s'obtient en inversant l'ordre de ses
lettres).\quad(a) Déduire de $\mathscr{A}_2$ un automate fini
$\mathscr{A}_3$ reconnaissant $L_3$.\quad(b) Quel est le rapport entre
@@ -171,8 +174,8 @@ $\mathscr{A}_{4\mathrm{a}}$ ayant six états
reconnaissant $L_4$.\quad(b) Donner l'automate fini déterministe
complet minimal $\mathscr{A}_{4\mathrm{b}}$ reconnaissant $L_4$.
-\emph{Information :} L'automate $\mathscr{A}_4$ correct a quatre
-états. Même conseil que pour la question (1).
+\emph{Information :} L'automate $\mathscr{A}_{4\mathrm{b}}$ correct a
+quatre états. Même conseil que pour la question (1).
\medskip
@@ -182,10 +185,72 @@ dénotant le langage $L_4$.
\medskip
-(6) Sans raisonner sur les automates, proposer une expression
-rationnelle $r_6$ différente de celle trouvée en $r_5$ et qui dénote
-aussi le langage $L_4$ (dont on donnera au préalable une description
-en français).
+(6) Sans raisonner sur les automates, proposer directement une
+expression rationnelle $r_6$ différente de celle trouvée en $r_5$ et
+qui dénote aussi le langage $L_4$ (dont on donnera au préalable une
+description en français).
+
+
+%
+%
+%
+
+\exercice\label{exercise-two}
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.
+
+Soit $L$ le langage formé des mots de $\Sigma^*$ ayant à la fois
+$a$ comme première lettre et aussi comme dernière lettre
+(c'est-à-dire, les mots ayant $a$ comme préfixe et aussi $a$ comme
+suffixe).
+
+\smallskip
+
+(1) (a) Expliciter une grammaire hors contexte $G$
+engrendrant $L$.\quad(b) Cette grammaire $G$ est-elle déterministe ?
+(On justifiera la réponse.)
+
+\medskip
+
+(2) La langage $L$ est-il décidable ? Est-il semi-décidable ? On
+justifiera soigneusement la réponse.
+
+
+%
+%
+%
+
+\exercice\label{exercise-three}
+
+Dans cet exercice, on pose $\Sigma = \{a\}$.
+
+Soit $L = \{a, aa, aaaa, aaaaaaaa,\ldots\} = \{a^{2^k} :
+k\in\mathbb{N}\}$ le langage formé des mots de $\Sigma^*$ dont la
+longueur est une puissance de $2$.
+
+\smallskip
+
+(1) Le langage $L$ est-il rationnel ? Si oui, on explicitera une
+expression rationnelle le dénotant ; si non, on démontrera ce fait.
+
+\medskip
+
+(2) Le langage $L$ est-il algébrique (autrement dit, existe-t-il une
+grammaire hors contexte $G$ engendrant $L$) ? Si oui, on explicitera
+une grammaire hors contexte l'engendrant ; si non, on démontrera ce
+fait.
+
+\medskip
+
+(3) La langage $L$ est-il décidable ? Est-il semi-décidable ? Comme
+pour les questions précédentes, on justifiera soigneusement la
+réponse.
+
+\medskip
+
+\emph{Remarque :} Il est loisible de répondre aux questions de cet
+exercice dans un ordre différent par exemple pour éviter de répéter
+inutilement des raisonnements.
%
%
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