diff options
| -rw-r--r-- | controle-20180322.tex | 60 |
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 |