Various clarifications, corrections, todos...

1 files changed, 83 insertions, 52 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5c75960..ea0ece6 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -151,17 +151,17 @@ sorte de guillemet pour délimiter les chaînes de caractères : on
 écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
 question.  Dans ces notes, nous utiliserons peu cette convention.)
 
-L'ensemble des mots sur un alphabet $\Sigma$ est généralement
-désigné $\Sigma^*$ (on verra que l'étoile fait partie d'un usage plus
-général qui sera défini ci-dessous).  Par exemple, si $\Sigma =
-\{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments
-sont toutes les suites finies binaires (=suites finies de $0$ et
-de $1$).
+L'ensemble des mots sur un alphabet $\Sigma$ sera désigné $\Sigma^*$
+(on verra en \ref{kleene-star} ci-dessous cette notation comme un cas
+particulier d'une construction « étoile » plus générale).  Par
+exemple, si $\Sigma = \{0,1\}$, alors $\Sigma^*$ est l'ensemble
+(infini !) dont les éléments sont toutes les suites finies binaires
+(=suites finies de $0$ et de $1$).
 
 \thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
 appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
 bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
-la longueur $\ell(x_1\cdots x_n)$ du mot $x_1\cdots x_n$, vaut $n$.
+la longueur $|x_1\cdots x_n|$ du mot $x_1\cdots x_n$, vaut $n$.
 Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
 caractères en informatique.  À titre d'exemple, sur l'alphabet
 $\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
@@ -193,7 +193,8 @@ guillemets.)
 La notation $\Sigma^+$ est parfois utilisée pour désigner l'ensemble
 des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
 $\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
-vide).
+vide) ; on verra en \ref{kleene-plus} ci-dessous que c'est un cas
+particulier d'une construction plus générale.
 
 \thingy\label{convention-on-words-of-length-one} Les mots d'une seule
 lettre sont naturellement en correspondance avec les lettres
@@ -202,8 +203,8 @@ abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé
 de la seule lettre $x$.  (En informatique, cette identification entre
 \emph{caractères} et \emph{chaînes de caractères de longueur $1$} est
 faite par certains langages de programmation, mais pas par tous :
-\textit{caveat programmator}.)  Ceci permet d'écrire par exemple
-$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.
+\textit{caveat programmator}.)  Cette convention permet d'écrire par
+exemple $\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.
 
 \thingy\label{number-of-words-of-length-n} Si le cardinal de
 l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
@@ -233,7 +234,7 @@ suivants :
   \varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
 \item la concaténation est « \textbf{associative} », ce qui signifie
   par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
-  \in \Sigma^*$.
+  \in \Sigma^*$ (on peut donc noter $uvw$ sans parenthèse).
 \end{itemize}
 
 On peut traduire de façon savante ces deux propriétés en une phrase :
@@ -264,8 +265,8 @@ signifie exactement ce qui vient d'être dit).
   précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
   l'ensemble $\Sigma$.  Par exemple, le morphisme « longueur »
   $\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
-  appliquant cette propriété à la fonction $\psi(x) = 1$ pour
-  tout $x\in\Sigma$.\par}
+  appliquant cette propriété à la fonction (constante) $\psi(x) = 1$
+  pour tout $x\in\Sigma$.\par}
 
 \thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in
 \mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$
@@ -283,7 +284,7 @@ Cette définition sert notamment à désigner de façon concise les mots
 comportant des répétitions d'une même lettre : par exemple, le mot
 $aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut
 s'écrire $a^3 b^2$.  (De même que pour le mot vide, il faut souligner
-que ces exposants ne font pas partie de l'alphabet.)
+que ces exposants \emph{ne font pas partie} de l'alphabet.)
 
 \thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
 lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
@@ -340,21 +341,38 @@ est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
 cependant pas confondre ce concept avec celui de sous-mot défini
 ci-dessous.
 
-\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et
-$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira
-que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1
-u_1 v_2 \cdots u_{r-1} v_r u_r$.  En plus clair, cela signifie que $v$
-est obtenu en ne gardant que certaines lettres du mot $w$ (celles
-des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles
-des $u_i$) ; à la différence du concept de facteur, celui de sous-mot
+\thingy\label{definition-subword} Si $w = x_1\cdots x_n$ est un mot de
+longueur $n$, on appelle \textbf{sous-mot} de $w$ un mot de la forme
+$x_{i_1} \cdots x_{i_k}$ où $1\leq i_1 < \cdots < i_k \leq n$.  En
+plus clair, cela signifie que $v$ est obtenu en ne gardant que
+certaines lettres du mot $w$, dans le même ordre, mais en en effaçant
+d'autres ; à la différence du concept de facteur, celui de sous-mot
 n'exige pas que les lettres gardées soient consécutives.
 
 À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
 (obtenu en gardant les lettres soulignées ici :
 $\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
-définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
-a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
-\varepsilon$).
+définition ci-dessus, on pourra prendre $(i_1,i_2,i_3) = (1,4,6)$).
+
+{\footnotesize\thingy Les remarques de dénombrement suivantes peuvent
+  aider à mieux comprendre les notations de préfixe, suffixe, facteur
+  et sous-mot : si $w$ est un mot de longueur $n$, alors il a
+\begin{itemize}
+\item exactement $n+1$ préfixes (car un préfixe est déterminé par sa
+  longueur $k$ entre $0$ et $n$),
+\item exactement $n+1$ suffixes (raison analogue),
+\item au plus $\sum_{k=1}^n (n+1-k) + 1 = \frac{1}{2}(n^2+n+2)$
+  facteurs (car un facteur est déterminé par sa longueur $k$ et son
+  point de départ qui peut être choisi parmi $n+1-k$ possibilités, le
+  $+1$ final étant mis pour le facteur vide),
+\item au plus $2^n$ sous-mots (car un sous-mot est déterminé par
+  l'ensemble $\{i_1,\ldots,i_k\}$ des indices de ses lettres).
+\end{itemize}
+Le nombre exact peut être plus petit en cas de coïncidences entre
+certains choix (par exemple, $aaa$ n'a que $4$ facteurs, $\varepsilon,
+a, aa, aaa$ alors que $abc$ en a bien $\frac{1}{2}(3^2+3+2) = 7$) ;
+mais les bornes ci-dessus sont effectivement atteintes pour certains
+mots.\par}
 
 \thingy\label{definition-mirror-word} Si $w = x_1\cdots x_n$, où
 $x_1,\ldots,x_n \in \Sigma$, est un mot de longueur $n$ sur un
@@ -374,7 +392,7 @@ Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.
 \thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement
 un ensemble de mots sur $\Sigma$.  Autrement dit, il s'agit d'un
 sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ de tous les mots
-sur $\Sigma^*$ : en symboles, $L \subseteq \Sigma^*$.  On souligne
+sur $\Sigma$ : en symboles, $L \subseteq \Sigma^*$.  On souligne
 qu'on ne demande pas que $L$ soit fini (mais il peut l'être).
 
 \thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
@@ -392,15 +410,16 @@ Voici quelques autres exemples de langages :
   sur l'alphabet $\Sigma = \{p,q,r\}$.  Comme on l'a vu
   en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal
   exactement $3^{42}$.
+\item Le langage constitué des mots de longueur exactement $1$ sur un
+  alphabet $\Sigma$ (=mots de une seule lettre), qu'on peut identifier
+  à $\Sigma$ lui-même (en identifiant un mot de une lettre à la lettre
+  en question, cf. \ref{convention-on-words-of-length-one}).
 \item Le langage (fini) constitué du seul mot vide (=mot de longueur
   exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$.  Ce
   langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut).
   Il ne faut pas le confondre avec le suivant :
 \item Le langage vide, qui ne contient aucun mot (sur un alphabet
   quelconque).  Ce langage a pour cardinal $0$.
-\item Le langage constitué des mots de une seule lettre sur un alphabet
-  $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant
-  un mot de une lettre à la lettre en question).
 \item Le langage sur l'alphabet $\Sigma=\{a,b\}$ constitué des mots
   qui commencent par trois $a$ consécutifs : ou, si on préfère, qui
   ont le mot $aaa$ comme préfixe.
@@ -481,7 +500,7 @@ défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme
 concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit
 \[
 \begin{aligned}
-L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
+L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
  &= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\
 \end{aligned}
 \]
@@ -514,13 +533,13 @@ longueur exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux
 éléments $\{a^r, b^r\}$ constitué des seuls deux mots $a^r = aaa\cdots
 a$ et $b^r = bbb\cdots b$.
 
-\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit
-enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage
-constitué des concaténations d'un nombre \emph{quelconque} de mots
-appartenant à $L$, c'est-à-dire
+\thingy\label{kleene-star} Si $L$ est un langage sur
+l'alphabet $\Sigma$, on définit enfin l'\textbf{étoile de Kleene}
+$L^*$ de $L$ comme le langage constitué des concaténations d'un nombre
+\emph{quelconque} de mots appartenant à $L$, c'est-à-dire
 \[
 \begin{aligned}
-L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
+L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
 &= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
 \end{aligned}
 \]
@@ -541,7 +560,7 @@ Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
 $L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
 (autrement dit, le mot vide est la concaténation de zéro mots de $L$).
 
-\thingy\label{kleene-plus} On introduit parfois la notation $L^+ =
+\thingy\label{kleene-plus} On introduit parfois la notation $L^+ :=
 \bigcup_{r=1}^{+\infty} L^r = \{w_1\cdots w_r : r>0,\penalty-100\,
 w_1,\ldots,w_r\in L\}$ pour l'ensemble des mots formés par
 concaténation d'un nombre \emph{non nul} de mots de $L$.  Lorsque le
@@ -559,6 +578,8 @@ c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
 
 \subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
 
+\textcolor{red}{TODO: Commencer par une explication informelle.}
+
 \thingy Soit $\Sigma$ un alphabet.  On va considérer les langages
 de base triviaux suivants :
 \begin{itemize}
@@ -623,7 +644,7 @@ introduit un nouvel objet, les \textbf{expressions rationnelles}
 (certains préfèrent le terme d'\textbf{expressions régulières}), qui
 sont des expressions servant à désigner un langage rationnel.  Par
 exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
-langage désigné par l'expression rationnelle $dc{*}$.
+langage « désigné par l'expression rationnelle $dc{*}$ ».
 
 Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
 est un mot sur l'alphabet $\Sigma \cup \{\bot,
@@ -656,7 +677,7 @@ d'expression rationnelle $r$ et de \textbf{langage dénoté} (ou
   et son langage dénoté est $L_{(r){*}} := L^*$.
 \end{itemize}
 
-À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
+\thingy À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
 expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en
 est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc,
 ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui dénote le langage $\{d,
@@ -689,9 +710,10 @@ $\Sigma = \{a,b,c,d\}$ :
 Un langage rationnel est par construction la même chose qu'un langage
 pour lequel il existe une expression rationnelle qui le dénote.
 
-On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
-lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in
-L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$.
+\thingy On dira qu'un mot $w$ \textbf{vérifie} une expression
+rationnelle $r$ lorsque ce mot appartient au langage qu'elle dénote
+(i.e., $w \in L_r$).  Par exemple, $dccc$ vérifie l'expression
+rationnelle $d(c){*}$.
 
 \thingy Deux expressions rationnelles $r_1,r_2$ sont dites
 \textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre
@@ -730,10 +752,11 @@ que, en informatique, le symbole \texttt{+} est utilisé par de
 nombreux moteurs d'expressions régulières (par exemple,
 \texttt{egrep}) pour dénoter l'opération évoquée en \ref{kleene-plus},
 i.e., « au moins une répétition » alors que l'étoile signifie « un
-  nombre quelconque de répétitions » : si on veut, $r{+}$ a le même
-sens que $rr{*}$.  Dans le même contexte, le symbole \texttt{?} est
-souvent utilisé pour désigner « au plus une répétition » : si on veut,
-$r{?}$ a le même sens que $(\underline{\varepsilon}|r)$.
+nombre quelconque de répétitions » : si on veut, $r{\scriptstyle +}$ a
+le même sens que $rr{*}$.  Dans le même contexte, le symbole
+\texttt{?} est souvent utilisé pour désigner « au plus une
+répétition » : si on veut, $r{?}$ a le même sens
+que $(\underline{\varepsilon}|r)$ (cf. \ref{remarks-egrep-plus-etc}).
 
 
 \subsection{Remarques sur les moteurs d'expressions régulières en informatique}
@@ -759,15 +782,15 @@ désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba,
 aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis
 d'un $b$ puis de la \emph{même suite de $a$}, et ce langage
 \emph{n'est pas rationnel} au sens mathématique (ce sera une
-conséquence du « lemme de pompage »).
+conséquence du « lemme de pompage » \ref{pumping-lemma}).
 
-\thingy Il existe aussi un certain nombre de constructions qui, sans
+\thingy\label{remarks-egrep-plus-etc} Il existe aussi un certain nombre de constructions qui, sans
 dépasser la puissance des expressions rationnelles au sens
 mathématique, apportent des commodités d'écriture dans un contexte
 informatique.  On a déjà mentionné les symboles \texttt{+} (pour « au
-  moins une répétition » : $r{+}$ est équivalent à $rr{*}$) et
-\texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent à
-$(\underline{\varepsilon}|r)$).  Parmi d'autres constructions du
+moins une répétition » : $r{\scriptstyle +}$ est équivalent à $rr{*}$)
+et \texttt{?} (pour « au plus une répétition » : $r{?}$ est équivalent
+à $(\underline{\varepsilon}|r)$).  Parmi d'autres constructions du
 genre, mentionnons encore le point \texttt{.} qui désigne un caractère
 quelconque de l'alphabet (on peut le voir comme une abréviation pour
 $(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont tous les éléments
@@ -857,6 +880,9 @@ possibles.  L'automate prendra une décision (passer dans un nouvel
 état) en fonction de son état actuel et de la lettre qu'on lui donne à
 consommer.
 
+\textcolor{red}{TODO: Commencer par une explication informelle et
+  évoquer les différentes sortes d'automates.}
+
 \subsection{Automates finis déterministes complets (=DFA)}
 
 \thingy\label{definition-dfa} Un \textbf{automate fini déterministe}
@@ -933,6 +959,9 @@ se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que
 l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
 F$ ou que $q_n \not\in F$.
 
+\textcolor{red}{TODO: Redire en termes de suites d'états comme
+  en \ref{rnfa-multiple-transition-relation}.}
+
 Graphiquement, on peut présenter la procédure de la manière suivante :
 on part de l'état $q_0$ (sommet du graphe représentant l'automate)
 indiqué par la flèche entrante (pointant de nulle part), et pour
@@ -965,6 +994,8 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
 $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
 \textbf{rejette} le mot $w$.
 
+\textcolor{red}{TODO: Explication informelle.}
+
 \thingy\label{definition-recognizable-language} L'ensemble $L_A$ des
 mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté},
 ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$.
@@ -982,7 +1013,7 @@ faire la description informelle suivante : l'automate commence dans
 l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer
 dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le
 fait passer dans l'état $2$, où il reste définitivement et qui
-constitue un état acceptant.
+constitue le seul état acceptant.
 
 \begin{center}
 %%% begin example2 %%%
@@ -1452,7 +1483,7 @@ partant de $0$ et étiquetée par $a$, tandis que $\delta'(\{0\},b) =
 \{0\}$ ; ensuite, $\delta'(\{0,1\},a) = \{0,1,2\}$ car $0,1,2$ sont
 les trois états auxquels on peut arriver dans $A$ par une transition
 partant de $0$ ou $1$ et étiquetée par $a$ ; et ainsi de suite.  En
-procédant ainsi, on constuit l'automate à $4$ états qui suit :
+procédant ainsi, on construit l'automate à $4$ états qui suit :
 
 \begin{center}
 \footnotesize
@@ -2049,7 +2080,7 @@ qu'on doit maintenant demander explicitement que l'ensemble $\delta$
 des transitions permises soit fini car l'ensemble $Q \times
 (\mathrm{regexp}(\Sigma)) \times Q$, lui, ne l'est pas.
 
-\thingy Pour un tel automate, on définit une relation $\delta^*
+\thingy\label{rnfa-multiple-transition-relation} Pour un tel automate, on définit une relation $\delta^*
 \subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$
 lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in
 \mathrm{regexp}(\Sigma)$ tels que $q_0 = q$ et $q_n = q'$ et