From 7bbca3c401a4ba1088cd7b806460cd68d06aa14f Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 21 Jan 2020 15:35:07 +0100
Subject: Finish writing answers to exercise on unary languages.

---
 controle-20200123.tex | 228 +++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 217 insertions(+), 11 deletions(-)

(limited to 'controle-20200123.tex')

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}
+
 
 %
 %
-- 
cgit v1.2.3