summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20180322.tex60
1 files changed, 32 insertions, 28 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex
index 8db45ea..94058dd 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -158,13 +158,13 @@ automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to
intercalées d'un nombre quelconque de transitions d'un état vers
lui-même, étiquetées par une lettre quelconque : la lecture de ses
étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et
-réciproquement, tout tel mot étiquette au moins un chemin de $0$ à $3$
-(une fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront
-aux transitions changeant d'état).
+réciproquement, tout tel mot étiquette un chemin de $0$ à $3$ (une
+fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront aux
+transitions changeant d'état).
\emph{Remarque :} il est correct de donner directement l'automate
-déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout NFA
-est, en particulier, un DFA), à condition de justifier proprement
+déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout DFA
+est, en particulier, un NFA), à condition de justifier proprement
qu'il convient.
\end{corrige}
@@ -176,7 +176,7 @@ En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' :=
\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui
correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$
qu'on vient d'indiquer, la déterminisation conduit à l'automate
-$\mathscr{A}_1$ suivant :
+$\mathscr{A}_2$ suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$};
@@ -203,14 +203,14 @@ résultant.
On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans
état inaccessible. La première étape de l'algorithme de minimisation
sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et
-$3'$ (finaux) de l'autre. Ensuite on sépare $0',1'$ d'une part et
-$2'$ de l'autre (car les premiers ne conduisent qu'à des états non
-finaux, tandis que $2'$ conduit à un état final par la transition
+$3'$ (final) de l'autre. Ensuite on sépare $0',1'$ d'une part et $2'$
+de l'autre (car les premiers ne conduisent qu'à des états non finaux,
+tandis que $2'$ conduit à un état final par la transition
étiquetée $c$). L'étape suivante sépare $0'$ et $1'$ (car le premier
-ne conduit qu'à un état de la classe $0',1'$ de l'étape précédente,
-tandis que $1'$ conduit à un état de la classe $2'$ par la transition
-étiquetée $b$). On a donc séparé tous les états, ce qui montre que
-$\mathscr{A}_3 = \mathscr{A}_2$ est minimal.
+ne conduit qu'à un état de la classe $\{0',1'\}$ de l'étape
+précédente, tandis que $1'$ conduit à un état de la classe $\{2'\}$
+par la transition étiquetée $b$). On a donc séparé tous les états, ce
+qui montre que $\mathscr{A}_3 = \mathscr{A}_2$ est minimal.
\emph{Remarque :} on pouvait aussi invoquer l'argument suivant :
puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots
@@ -249,7 +249,7 @@ $\mathscr{A}_3$ suivant :
états, déterminer une expression rationnelle dénotant le langage $M$.
(Si on souhaite obtenir une expression plus compacte, il est
recommandé de commencer l'élimination des états par ceux qui sont
-plutôt proches de l'état final.)
+le plus loin de l'état initial.)
\begin{corrige}
On va manipuler des automates finis à transitions étiquetées par des
@@ -258,12 +258,13 @@ donne à l'automate un unique état final $F$ en faisant pointer vers
lui une transition spontanée (i.e., étiquetée
par $\underline{\varepsilon}$) depuis tout état qui était final, et un
unique état initial $I$ depuis lequel on fait partir une transition
-spontanée vers $0$. L'état $3'$ peut être éliminé d'emblée puisqu'il
+spontanée vers $0'$. L'état $3'$ peut être éliminé d'emblée puisqu'il
est inutile (il n'est pas co-accessible : c'est un puits !). Par
ailleurs, deux transitions entre les mêmes états sont remplacées par
une seule étiquetée par la disjonction des étiquettes (par exemple,
-les deux transitions $0'\to 0'$ étiquetées $b,c$ sont remplacées par
-une seule étiquetée $b|c$). On a donc affaire à l'automate suivant :
+les deux transitions $0'\to 0'$ étiquetées $b$ et $c$ sont remplacées
+par une seule étiquetée $b|c$). On a donc affaire à l'automate
+suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
@@ -427,7 +428,7 @@ dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j
\begin{corrige}
Considérons la propriété « avoir (au total) au moins autant de $a$ que
-de $b$ », si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
+de $b$ », ou si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup
N = \{a,b,S\}$). Cette propriété est vérifiée par le pseudo-mot $S$.
Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou
@@ -448,7 +449,8 @@ rationnel. Appliquons le lemme de pompage pour les langages
rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de
pompage garantit l'existence. Considérons le mot $t := a^k b^k$ (qui
appartient bien à $P$ et est bien de longueur $\geq k$) : il doit
-alors exister une factorisation $t = uvw$ pour laquelle on a
+alors exister une factorisation $t = uvw$ (avec $u,v,w \in \Sigma^*$,
+non nécessairement dans $P$) pour laquelle on a
(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour
tout $i\geq 0$. La propriété (ii) assure que $uv$ est formé d'un
certain nombre de répétitions de la lettre $a$ (car tout préfixe de
@@ -482,14 +484,16 @@ n'est pas rationnel. C'est donc que $L$ ne l'est pas.
\exercice
Dans cet exercice, on s'intéresse au langage $L$ formé des
-programmes $e$ (codés, dans un langage Turing-complet fixé quelconque,
-comme des entiers naturels ou comme des mots sur un alphabet fixé sans
-importance) qui, quel que soit le paramètre $n$ qu'on leur fournit
-en entrée, terminent en temps fini et retournent la valeur $0$ : soit
-$L = \{e : (\forall n) {\varphi_e(n)\downarrow} = 0\}$. Si l'on
-préfère, $L$ est l'ensemble de toutes les façons de coder la fonction
-constante égale à $0$. On appellera aussi $M$ le complémentaire
-de $L$. On se demande si $L$ ou $M$ sont semi-décidables.
+programmes $e$ (codés, dans une formalisation quelconque de la
+calculabilité\footnote{Par exemple, un langage de programmation
+ (Turing-complet) quelconque.}, comme des entiers naturels ou comme
+des mots sur un alphabet fixé sans importance) qui, quel que soit le
+paramètre $n$ qu'on leur fournit en entrée, terminent en temps fini et
+retournent la valeur $0$ : soit $L = \{e : (\forall n)
+{\varphi_e(n)\downarrow} = 0\}$. Si l'on préfère, $L$ est l'ensemble
+de toutes les façons de coder la fonction constante égale à $0$. On
+appellera aussi $M$ le complémentaire de $L$. On se demande si $L$ ou
+$M$ sont semi-décidables.
\smallskip
@@ -561,7 +565,7 @@ finie au bout de ce temps.
\medskip
(2) Achille et Patrocle se disputent pour savoir si $M$ (le
-complémentaire de $L$) est semi-décidable. Achile pense qu'il l'est,
+complémentaire de $L$) est semi-décidable. Achille pense qu'il l'est,
et il tient le raisonnement suivant pour l'expliquer :
{\narrower