From ca644c1d85015e1c4bce66d42db4922edd8729b0 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 21 Jan 2020 20:28:06 +0100
Subject: Re-read test and answers.

---
 controle-20200123.tex | 150 +++++++++++++++++++++++++++++---------------------
 1 file changed, 87 insertions(+), 63 deletions(-)

diff --git a/controle-20200123.tex b/controle-20200123.tex
index 374f3d3..00792d7 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -106,7 +106,7 @@ Durée : 1h30
 Barème \emph{indicatif} : 2+(7+6)+5.
 
 \ifcorrige
-Ce corrigé comporte 8 pages (page de garde incluse)
+Ce corrigé comporte 9 pages (page de garde incluse)
 \else
 Cet énoncé comporte 3 pages (page de garde incluse)
 \fi
@@ -128,7 +128,7 @@ Git: \input{vcline.tex}
 
 \exercice
 
-Soit $\mathscr{A}$ l'automate suivant sur l'alphabet $\Sigma :=
+Soit $\mathscr{A}$ l'automate fini suivant sur l'alphabet $\Sigma :=
 \{a,b,c\}$ :
 
 \begin{center}
@@ -170,7 +170,7 @@ $\varepsilon\;|\;(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$ (il se
 trouve que le premier terme est inutile et que cette expression
 rationnelle est équivalente à
 simplement $(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$, mais la
-méthode d'élimination conduit à ce qui a été dit).
+méthode d'élimination proprement menée conduit à ce qui a été dit).
 
 Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant :
 \begin{center}
@@ -198,12 +198,16 @@ d'élimination.
 
 \exercice\label{exercise-on-unary-languages}
 
-Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule lettre).
+Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule
+lettre), de sorte que $\Sigma^* = \{a^n : n\in\mathbb{N}\}$ ; on va
+appliquer les automates finis à un problème arithmétique.
 
 \medskip
 
 \textbf{Première partie : étude d'un cas particulier.}
 
+\nobreak
+
 Dans cette partie, on considère l'expression rationnelle $r$
 suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$).  On appelle $L
 := L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son
@@ -255,12 +259,11 @@ 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.
-
-(On obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On
-n'hésitera pas à introduire des notations simplificatrices si on le
-juge utile ; il pourra être judicieux de réfléchir au préalable à une
-façon de nommer les états de $\mathscr{A}_1$ qui rend la construction
+$\mathscr{A}_2$ l'automate (déterministe complet) en question.  (On
+obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On n'hésitera
+pas à introduire des notations allégées si on le juge utile ; il
+pourra être judicieux de réfléchir au préalable à une façon de nommer
+les états de $\mathscr{A}_1$ qui rend la construction
 de $\mathscr{A}_2$ plus facile à mener sans se tromper.)
 
 Pour simplifier les questions suivantes (ainsi que le travail du
@@ -272,8 +275,8 @@ mot $a^i$ par l'automate soit numéroté $i$.
 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) :
+transition (étiquetée par $a$) à considérer, ce qui construit
+successivement les états suivants (colonne du milieu de la table) :
 \begin{center}
 \begin{tabular}{c|l|c}
 $0$&$\{0\}$&F\\\hline
@@ -303,10 +306,13 @@ de $\mathscr{A}_1$).  L'unique transition de l'automate (évidemment
 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
+avec $1,1'$), on les a marqués par un F dans la colonne de droite de
+la table ci-dessus.
+
+On peut bien sûr préférer 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
+suivant, sauf du dernier sur lui-même, certains états étant finaux
 comme on vient de le dire.
 
 On renumérote alors les états comme selon la colonne de gauche de la
@@ -314,15 +320,13 @@ 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
+(Dans la notation introduite à la question (6) plus bas, 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}
@@ -358,11 +362,11 @@ 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
+question (6) plus bas, 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$
+(4) Construire un automate fini 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.
@@ -377,7 +381,7 @@ 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
+la notation introduite à la question (6) plus bas, l'automate
 $\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F =
 \{1,2,4,7\}$.)
 
@@ -395,46 +399,63 @@ $m,m'\in\mathbb{N}$.
 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
+si le mot $a^n$ appartient à $L$, c'est-à-dire vérifie $r$, i.e.,
 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$.
+$m$ de l'un et $m'$ de l'autre (en tout), il a pour longueur $n =
+3m+5m'$.  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
-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.
+\nobreak
+
+(6) Expliquer rapidement pourquoi un automate fini déterministe
+complet sans état inaccessible $\mathscr{A}$ sur $\Sigma = \{a\}$
+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$.
+Appelons $q_0$ l'état initial de $\mathscr{A}$, et par récurrence
+sur $i$, posons $q_{i+1} = \delta(q_i,a)$ l'état vers lequel pointe la
+transition sortante depuis l'état $q_i$ étiquetée par la lettre $a$
+(cette transition étant unique puisqu'on a affaire à un automate
+déterministe complet) ; ou, pour dire les choses autrement, appelons
+$q_i = \delta^*(q_0, a^i)$ (pour tout $i\in \mathbb{N}$) l'état
+résultant de la lecture du mot $a^i$ par l'automate.  L'automate
+$\mathscr{A}$ étant fini, les états $q_0,q_1,q_2,\ldots$ ne peuvent
+pas être tous distincts : il existe $j_1\neq j_2$ tels que $q_{j_1} =
+q_{j_2}$ ; appelons $j_2$ l'indice de la première répétition, i.e., le
+plus petit entier tel que $q_{j_2}$ coïncide avec un état $q_{j_1}$
+avec $0\leq j_1<j_2$.  Alors (puisque $j_2$ est l'indice de la
+première répétition) les états $q_0,\ldots,q_{j_2-1}$ sont tous
+distincts.  En nommant simplement $i$ l'état $q_i$ (pour $0\leq i<j_2$
+uniquement), on a, par construction, $\delta(i,a) = i+1$ pour $0\leq
+i<j_2-1$ tandis que $\delta(j_2-1,a) = j_1$, comme annoncé.  De plus,
+les états $0,\ldots,j_2-1$ étant tous ceux qu'on peut atteindre en
+partant de $0$ et an suivant les transitions, ce sont tous les états
+de l'automate (car on l'a supposé sans état inaccessible), donc $j_2$
+est le nombre d'états, et l'automate a bien la forme demandée.
 
 (Les notations choisies sont censées rappeler la démonstration du
-lemme de pompage, qui utilise la même idée.)
+lemme de pompage, qui utilise la même idée.  Aussi dans le même ordre
+d'idées, il est utile pour la question suivante de remarquer que $q_i
+= q_{i+(j_2-j_1)}$ dès que $i\geq j_1$, et donc plus généralement $q_i
+= q_{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$.)
 \end{corrige}
 
 (7) Une fois un automate déterministe complet sur $\Sigma$ présenté
@@ -448,8 +469,7 @@ 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$).
+acceptant, le langage est fini et égal à $\{a^i : i\in F\}$.
 
 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\} =
@@ -462,10 +482,14 @@ calculable algorithmiquement\footnote{Autrement dit, montrer qu'il
   existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r
   \in \mathbb{N}$, termine toujours en temps fini et répond au
   problème posé.} : donné des entiers naturels $\ell_1,\ldots,\ell_r
-\in \mathbb{N}$, décider s'il y a un 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.
+\in \mathbb{N}$, décider si l'ensemble\footnote{Autrement dit, il
+  s'agit de l'ensemble $\mathbb{N} \setminus \{\ell_1 m_1 + \cdots +
+  \ell_r m_r : (m_1,\ldots,m_r)\in \mathbb{N}^r\}$ complémentaire de
+  l'image de $\mathbb{N}^r \to \mathbb{N},\penalty0\; (m_1,\ldots,m_r)
+  \mapsto \ell_1 m_1 + \cdots + \ell_r m_r$.} des 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}$ est fini, 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
@@ -565,10 +589,10 @@ coupées au niveau des $b$.)
 \end{corrige}
 
 (2) Le langage $L := L(G)$ engendré par $G$ est, en fait, rationnel :
-expliquer brièvement pourquoi et donner une expression rationnelle qui
-le dénote.  (On pourra commencer par décrire le langage $L' := L(G,T)
-:= \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui
-dérivent de $T$ selon $G$.)
+expliquer brièvement pourquoi, et donner une expression rationnelle
+qui le dénote.  (On pourra commencer par décrire le langage $L' :=
+L(G,T) := \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots
+qui dérivent de $T$ selon $G$.)
 
 \begin{corrige}
 Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T
@@ -598,10 +622,10 @@ en insérant un arbre d'analyse d'un mot de $L'$ comme descendance de
 chaque $T$.  Bref, un mot de $L$ est une succession de mots de $L'$
 séparés par des $a$, ce que dénote justement $((cb){*}ca){*}(cb){*}c$.
 
-Tout ceci étant dit, en fait, le langage $L$ est dénoté par une
-expression rationnelle plus simple, à savoir $(c(a|b)){*}c$ (ou encore
-$c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes d'autres
-variantes), puisqu'il s'agit d'une succession de $c$ séparés
+Tout ceci étant dit, en fait, le langage $L$ peut aussi être dénoté
+par une expression rationnelle plus simple, à savoir $(c(a|b)){*}c$
+(ou encore $c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes
+d'autres variantes), puisqu'il s'agit d'une succession de $c$ séparés
 indifféremment par des $a$ ou des $b$.  Cette expression rationnelle
 perd le découpage en deux niveaux (d'abord par $a$ puis par $b$)
 effectué par la grammaire $G$, mais est correcte comme description du
-- 
cgit v1.2.3