summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer David A. Madore 2020-01-21 15:35:07 +0100 David A. Madore 2020-01-21 15:35:07 +0100 7bbca3c401a4ba1088cd7b806460cd68d06aa14f (patch) 002a5efcc0adb6e4d791b4eaac874002b446064d de989e56485767a771bbf81525cc3434b95ae894 (diff) inf105-7bbca3c401a4ba1088cd7b806460cd68d06aa14f.zipinf105-7bbca3c401a4ba1088cd7b806460cd68d06aa14f.tar.gzinf105-7bbca3c401a4ba1088cd7b806460cd68d06aa14f.tar.bz2
Finish writing answers to exercise on unary languages.
-rw-r--r--controle-20200123.tex228
1 files changed, 217 insertions, 11 deletions
 diff --git a/controle-20200123.tex b/controle-20200123.texindex 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