diff options
| -rw-r--r-- | controle-20200123.tex | 228 |
1 files changed, 217 insertions, 11 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex index 7042a81..e719177 100644 --- a/controle-20200123.tex +++ b/controle-20200123.tex @@ -221,6 +221,39 @@ $9$ états. À défaut de donner l'automate de Glushkov ou de Thompson, donner un NFA reconnaissant $L$ pourra apporter une partie des points.) +\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 (60bp,35bp) [draw,circle,state] {$1$}; +\node (S2) at (120bp,35bp) [draw,circle,state] {$2$}; +\node (S3) at (180bp,35bp) [draw,circle,state,final] {$3$}; +\node (S1p) at (60bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$1'$\hss}}\phantom{$1$}}; +\node (S2p) at (120bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$2'$\hss}}\phantom{$2$}}; +\node (S3p) at (180bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$3'$\hss}}\phantom{$3$}}; +\node (S4p) at (240bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$4'$\hss}}\phantom{$4$}}; +\node (S5p) at (300bp,-35bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$5'$\hss}}\phantom{$5$}}; +\draw [->] (S0) -- node[auto] {$a$} (S1); +\draw [->] (S1) -- node[auto] {$a$} (S2); +\draw [->] (S2) -- node[auto] {$a$} (S3); +\draw [->] (S0) -- node[auto,below] {$a$} (S1p); +\draw [->] (S1p) -- node[auto,below] {$a$} (S2p); +\draw [->] (S2p) -- node[auto,below] {$a$} (S3p); +\draw [->] (S3p) -- node[auto,below] {$a$} (S4p); +\draw [->] (S4p) -- node[auto,below] {$a$} (S5p); +\draw [->] (S3) -- node[auto,above,near end] {$a$} (S1p); +\draw [->] (S5p) -- node[auto,below,very near end] {$a$} (S1); +\draw [->] (S3) to[out=90,in=0] (130bp,70bp) -- node[auto,below] {$a$} (110bp,70bp) to[out=180,in=90] (S1); +\draw [->] (S5p) to[out=210,in=0] (190bp,-70bp) -- node[auto,above] {$a$} (170bp,-70bp) to[out=180,in=330] (S1p); +\end{tikzpicture} +\end{center} +C'est l'automate de Glushkov. Si on commence par construire +l'automate de Thompson, celui-ci a $20$ états, et l'élimination des +transitions spontanées conduit à l'automate $\mathscr{A}_1$ qu'on +vient d'écrire. +\end{corrige} + (2) Déterminiser l'automate $\mathscr{A}_1$. On appellera $\mathscr{A}_2$ l'automate (déterministe complet) en question. @@ -235,38 +268,194 @@ correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$ de façon que, autant que possible, l'état résultant de la lecture du mot $a^i$ par l'automate soit numéroté $i$. +\begin{corrige} +On travaille sur des ensembles d'états en suivant l'algorithme de +déterminisation : partant de l'ensemble $\{0\}$ des états initiaux de +l'automate $\mathscr{A}_1$, il n'y a à chaque fois qu'une seule +transition à construire, ce qui construit successivement les états +suivants (colonne du milieu de la table) : +\begin{center} +\begin{tabular}{c|l|c} +$0$&$\{0\}$&F\\\hline +$1$&$\{1,1'\}$&\\\hline +$2$&$\{2,2'\}$&\\\hline +$3$&$\{3,3'\}$&F\\\hline +$4$&$\{1,1',4'\}$&\\\hline +$5$&$\{2,2',5'\}$&F\\\hline +$6$&$\{1,1',3,3'\}$&F\\\hline +$7$&$\{1,1',2,2',4'\}$&\\\hline +$8$&$\{2,2',3,3',5'\}$&F\\\hline +$9$&$\{1,1',3,3',4'\}$&F\\\hline +$10$&$\{1,1',2,2',4',5'\}$&F\\\hline +$11$&$\{1,1',2,2',3,3',5'\}$&F\\\hline +$12$&$\{1,1',2,2',3,3',4'\}$&F\\\hline +$13$&$\{1,1',2,2',3,3',4',5'\}$&F\\ +\end{tabular} +\end{center} +Le procédé de calcul de la table est le suivant : à chaque ligne à +partir de la deuxième, on incrémente tous les numéros avec et sans +prime, sauf que $3$ ou $5'$ deviennent $1,1'$ (les deux à la fois, +puisqu'il y a des transitions de $3$ et $5'$ vers $1$ et $1'$ +dans $\mathscr{A}_1$). Ceci permet de ne pas se tromper (d'où +l'intérêt d'avoir judicieusement étiqueté les états +de $\mathscr{A}_1$). L'unique transition de l'automate (évidemment +étiquetée $a$) conduit de chaque ligne à la ligne suivante, sauf la +dernière ligne qui boucle sur elle-même. Les états finaux sont ceux +qui contiennent un des états finaux de $\mathscr{A}_1$, c'est-à-dire +$0$ ou $3$ ou $5'$ (ou encore, les lignes qui précèdent une ligne +avec $1,1'$). On peut bien sûr tracer graphiquement l'automate comme +d'habitude : c'est juste une ligne de $14$ états, toutes les +transitions étant étiquetées $a$, menant de chaque état vers le +suivant, sauf du dernier sur lui-même, avec certains états finaux +comme on vient de le dire. + +On renumérote alors les états comme selon la colonne de gauche de la +table, c'est-à-dire en suivant l'ordre des lignes. La transition +étiquetée $a$ mène alors de l'état $i$ vers l'état $i+1$ sauf pour +$i=13$ où elle mène vers lui-même. L'ensemble des états finaux est $F += \{0,3,5,6,8,9,10,11,12,13\}$ comme indiqué par la table. + +(Dans la notation introduite à la question (6) ci-dessous, l'automate +$\mathscr{A}_2$ est décrit par $j_2 = 14$, $j_1 = 13$ et $F = +\{0,3,5,6,8,9,10,11,12,13\}$.) +\end{corrige} + (3) Minimiser l'automate $\mathscr{A}_2$. On appellera $\mathscr{A}_3$ l'automate canonique ainsi obtenu. (On obtient un automate ayant $9$ états.) +\begin{corrige} +On a bien affaire pour commencer à un automate $\mathscr{A}_2$ +déterministe complet sans état inaccessible. + +L'algorithme de minimisation commence par partitionner l'ensemble +$\{0,\ldots,13\}$ des états en deux classes, les finaux +$\{0,3,5,6,8,9,10,11,12,13\}$ et les non-finaux $\{1,2,4,7\}$. Une +première itération sépare les finaux en $\{5,8,9,10,11,12,13\}$ et +$\{0,3,6\}$ (selon que l'état vers lequel aboutit l'unique transition +est lui-même final ou non) et les non-finaux en $\{2,4,7\}$ et $\{1\}$ +(idem). La seconde itération sépare chacun de $0$, $2$ et $5$ des +autres états de leur classe respective : les classes sont alors +$\{0\}$, $\{1\}$, $\{2\}$, $\{3,6\}$, $\{4,7\}$ et +$\{8,9,10,11,12,13\}$. La troisième itération sépare $4$ et $7$ +tandis que la quatrième sépare $3$ et $6$. Finalement, on obtient un +automate $\mathscr{A}_3$ canonique ayant $9$ états : un pour chaque +état de l'automate $\mathscr{A}_2$ entre $0$ et $7$ inclus, et un pour +tous les états de $8$ à $13$ inclus. + +On pouvait aussi arguër de manière plus abstraite : il est clair que +tous les états $8$ à $13$ devront être fusionnés puisqu'ils sont +finaux et que leurs transitions arbitrairement itérées ne conduisent +qu'à des états finaux, tandis que les états $0$ à $7$ inclus devront +être tous séparés puisqu'ils sont distingués par le nombre de +transitions à partir desquelles on n'arrive plus qu'à des états +finaux. + +On peut bien sûr tracer graphiquement l'automate $\mathscr{A}_3$ comme +d'habitude : c'est juste une ligne de $9$ états, toutes les +transitions étant étiquetées $a$, menant de chaque état vers le +suivant, sauf du dernier sur lui-même, les états finaux étant ceux +numérotés $0,3,5,6,8$ si on numérote les états de $0$ à $8$ dans +l'ordre des transitions. (Dans la notation introduite à la +question (6) ci-dessous, l'automate $\mathscr{A}_3$ est décrit par +$j_2 = 9$, $j_1 = 8$ et $F = \{0,3,5,6,8\}$.) +\end{corrige} + (4) Construire un automate déterministe complet $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire de $L$. Ce langage $M$ est fini : énumérer exhaustivement les mots qu'il contient. +\begin{corrige} +Il suffit d'échanger états finaux et non-finaux dans un automate +déterministe complet quelconque reconnaissant $L$, disons l'automate +$\mathscr{A}_3$ (on pouvait aussi utiliser $\mathscr{A}_2$ si on n'a +pas réussi à calculer $\mathscr{A}_3$). On peut bien sûr tracer +graphiquement l'automate $\mathscr{A}_4$ comme d'habitude : c'est +juste une ligne de $9$ états, toutes les transitions étant +étiquetées $a$, menant de chaque état vers le suivant, sauf du dernier +sur lui-même, les états finaux étant ceux numérotés $1,2,4,7$ si on +numérote les états de $0$ à $8$ dans l'ordre des transitions. (Dans +la notation introduite à la question (6) ci-dessous, l'automate +$\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F = +\{1,2,4,7\}$.) + +L'état $8$ (i.e., le dernier) étant un puits dans +l'automate $\mathscr{A}_4$, les seuls mots acceptés le sont avant le +puits, et ce sont les mots $a$, $aa$, $aaaa = a^4$ et $aaaaaaa = a^7$ +comme donnés par les états finaux de $\mathscr{A}_4$. +\end{corrige} + (5) En utilisant la question précédente, dire quels sont les (quatre) entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$. +\begin{corrige} +Si $n = 3m+5m'$ alors le mot $a^n = (aaa)^m(aaaaa)^{m'}$ appartient +à $L$, c'est-à-dire qu'il vérifie $r$ puisqu'il est manifestement +concaténation de mots de la forme $aaa$ ou $aaaaa$. Réciproquement, +la longueur d'un mot de $L$, c'est-à-dire vérifiant $r$, donc +concaténation de mots de la forme $aaa$ et de la forme $aaaaa$, disons +$m$ de l'un et $m'$ de l'autre (en tout) a pour longueur $n := 3m+5m'$ +et sur l'alphabet $\{a\}$ le seul mot de cette longueur est le +mot $a^n$. Bref, les mots de $L$ sont exactement les $a^n$ avec $n$ +de la forme $3m+5m'$ ; et les mots qui ne sont pas dans $L$ (i.e., +sont dans $M$) sont exactement les $a^n$ avec $n$ ne pouvant pas +s'écrire de la forme $3m+5m'$ : on a vu que ce sont $a$, $aa$, $aaaa = +a^4$ et $aaaaaaa = a^7$. Ainsi, les quatre entiers naturels ne +pouvant pas s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$ +sont : $1$, $2$, $4$ et $7$. +\end{corrige} + \medbreak \textbf{Seconde partie : considérations générales.} (6) Expliquer rapidement pourquoi un automate déterministe complet -$\mathscr{A}$ sur $\Sigma$ prend nécessairement la forme suivante : si -on note $j_2$ son nombre d'états, on peut numéroter ses états de -$0$ à $j_2-1$, avec $0$ l'état initial, et de façon qu'il y ait une -unique transition étiquetée $a$ de l'état $i$ vers l'état $i+1$ pour -chaque $0\leq i<j_2-1$, ainsi qu'une transition étiquetée $a$ de -l'état $j_2-1$ vers l'état $j_1$ pour un certain $0\leq j_1<j_2$. -Remarquer que l'automate $\mathscr{A}$ est alors complètement décrit -par les entiers $0\leq j_1<j_2$ et par le sous-ensemble $F$ de -$\{0,\ldots,j_2-1\}$ formé des états finaux. +sans état inaccessible $\mathscr{A}$ sur $\Sigma$ prend nécessairement +la forme suivante : si on note $j_2$ son nombre d'états, on peut +numéroter ses états de $0$ à $j_2-1$, avec $0$ l'état initial, et de +façon qu'il y ait une unique transition étiquetée $a$ de l'état $i$ +vers l'état $i+1$ pour chaque $0\leq i<j_2-1$, ainsi qu'une transition +étiquetée $a$ de l'état $j_2-1$ vers l'état $j_1$ pour un +certain $0\leq j_1<j_2$. Remarquer que l'automate $\mathscr{A}$ est +alors complètement décrit par les entiers $0\leq j_1<j_2$ et par le +sous-ensemble $F$ de $\{0,\ldots,j_2-1\}$ formé des états finaux. + +\begin{corrige} +Numérotons les états de $\mathscr{A}$ à partir de l'état initial $0$ +et en numérotant successivement les états selon la fonction de +transition $q\mapsto \delta(q,a)$, c'est-à-dire qu'on numérote $i$ +l'état $\delta^*(0,a^i)$ résultant de la lecture du mot $a^i$ par +l'automate, et ce, jusqu'à retomber sur un état $j_1$ déjà rencontré +(=numéroté). Si $j_2$ est le nombre total d'états, on a ainsi +complètement décrit l'automate par $\delta(i,a) = i+1$ sauf pour le +dernier état $j_2 - 1$ qui est envoyé sur $\delta(j_2 - 1, a) = j_1$. + +(Les notations choisies sont censées rappeler la démonstration du +lemme de pompage, qui utilise la même idée.) +\end{corrige} (7) Une fois un automate déterministe complet sur $\Sigma$ présenté -comme décrit à la question (6), à quelle condition (sur $j_1,j_2,F$) -le langage qu'il reconnaît est-il fini ? +comme décrit à la question (6), à quelle condition nécessaire et +suffisante (sur $j_1,j_2,F$) le langage qu'il reconnaît est-il fini ? + +\begin{corrige} +Les états $i$ tels que $j_1\leq i<j_2$ avec la notation introduite +en (6) sont des états résultat de la lecture d'un nombre infini de +mots distincts (à savoir $a^i$, $a^{i+(j_2-j_1)}$, et plus +généralement $a^{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$). Si l'un +quelconque de ces états est acceptant (=final), le langage reconnu par +l'automate est infini. À l'inverse, si aucun de ces états n'est +acceptant, le langage est fini et est constitué des $a^i$ pour $i\in +F$ (et $i<j_1$). + +Bref, la condition nécessaire et suffisante de finitude du langage +reconnu par $\mathscr{A}$ est que $F \cap \{j_1,\ldots,j_2-1\} = +\varnothing$, et le cas échéant, le langage est constitué des $a^i$ +pour $i\in F$ (et $i<j_1$). +\end{corrige} (8) Déduire de l'ensemble de cet exercice que le problème suivant est calculable algorithmiquement\footnote{Autrement dit, montrer qu'il @@ -277,6 +466,23 @@ nombre fini d'entiers naturels qui ne peuvent pas s'écrire sous la forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in \mathbb{N}$, et, le cas échéant, les énumérer. +\begin{corrige} +Il suffit d'appliquer la même méthode qui a été utilisée dans les +questions précédentes : donnés $\ell_1,\ldots,\ell_r \in \mathbb{N}$, +on fabrique l'expression rationnelle +$(a^{\ell_1}|\cdots|a^{\ell_r}){*}$ sur $\Sigma$, on construit son +automate de Glushkov (ou de Thompson dont on élimine ensuite les +transitions spontanées), on le déterminise, on peut éventuellement le +minimiser même si ce n'est pas nécessaire pour cette question, on +échange états finaux et non-finaux pour obtenir un automate +reconnaissant le langage complémentaire, et enfin on utilise le +critère trouvé en (7) pour savoir si ce langage est fini et, le cas +échéant, l'énumérer. Par le même raisonnement qu'en (5), ceci donne +exactement les $a^n$ pour les $n$ qui ne peuvent pas s'écrire sous la +forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in +\mathbb{N}$. +\end{corrige} + % % |