Rework various comments (especially on regular expressions).

1 files changed, 107 insertions, 68 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 8862e5d..4533160 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -114,14 +114,16 @@ Git: \input{vcline.tex}
 
 \setcounter{comcnt}{0}
 
-\thingy \textbf{Présentation et plan :} On se propose de développer
-ici des techniques mathématiques et algorithmiques ayant à la fois un
-intérêt théorique comme théorie des langages formels, et une
-application informatique pratique à l'analyse de textes ou de chaînes
-de caractères (qu'on appellera par la suite « mots »,
+\thingy \textbf{Présentation générale et plan :} On se propose de
+développer ici des techniques mathématiques et algorithmiques ayant à
+la fois un intérêt théorique comme théorie des langages formels, et
+une application informatique pratique à l'analyse de textes ou de
+chaînes de caractères (qu'on appellera par la suite « mots »,
 cf. §\ref{subsection-introduction-and-words}).
 
-Ces notes sont divisées en grandes parties (inégales) de la manière
+Après des définitions générales (sections
+\ref{subsection-introduction-and-words} à \ref{subjection-languages}),
+ces notes sont divisées en grandes parties (inégales) de la manière
 suivante :
 \begin{itemize}
 \item l'étude des expressions rationnelles et des automates finis, et
@@ -167,7 +169,7 @@ $A=B$ mais en insistant sur le fait que c'est la définition du membre
 du côté duquel se situent les deux points).  On note $\mathbb{N}$
 l'ensemble $\{0,1,2,3\ldots\}$ des entiers naturels.
 
-Le symbole \qedsymbol marque la fin d'une démonstration.
+Le symbole \qedsymbol{} marque la fin d'une démonstration.
 
 \section{Alphabets, mots et langages ; langages rationnels}\label{section-languages-and-rational-languages}
 
@@ -562,7 +564,7 @@ langage pourrait être considéré comme une propriété des mots.
   appartenir à la partie en question.)\par}
 
 On évitera de faire cette identification pour ne pas introduire de
-confusion, mais il est utile de la garder à l'esprit : par exemple,
+complication, mais il est utile de la garder à l'esprit : par exemple,
 dans un langage de programmation fonctionnel, un « langage » au sens
 de ces notes peut être considéré comme une fonction (pure,
 c'est-à-dire, déterministe et sans effet de bord) prenant en entrée
@@ -895,11 +897,25 @@ suivante :
   dénoté est $L_{r_1 r_2} := L_1 L_2$,
 \item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
   L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants,
-  alors $(r_1|r_2)$ est une expression rationnelle et son langage
-  dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$,
+  alors $(r_1|r_2)$ est une expression rationnelle\footnote{Certains
+    préfèrent la notation $r_1+r_2$ ici,
+    cf. \ref{regexp-notation-variations} pour une discussion.} et son
+  langage dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$,
 \item si $r$ est une expression rationnelle et $L = L_r$ les langage
-  dénoté correspondant, alors $(r){*}$ est une expression rationnelle
-  et son langage dénoté est $L_{(r){*}} := L^*$.
+  dénoté correspondant, alors $(r){*}$ est une expression
+  rationnelle\footnote{Notons que certains auteurs préfèrent mettre le
+    $*$ en exposant ici, c'est-à-dire noter $(r)^*$ (comme nous
+    l'avons fait pour l'étoile de Kleene $L^*$ d'un langage $L$) ;
+    comme nous avons choisi de définir une expression rationnelle
+    comme un mot sur l'alphabet $\Sigma \cup \{\bot,
+    \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, il semble plus
+    raisonnable de ne pas rentrer dans la considération byzantine de
+    savoir si un mot peut contenir des symboles en exposant.  En tout
+    état de cause, il n'apparaîtra jamais aucune circonstance où les
+    deux notations $X^*$ et $X{*}$ auraient tous les deux un sens et
+    que ces sens diffèrent !  On peut donc ignorer purement et
+    simplement la question de savoir si oui ou non l'étoile est en
+    exposant.} et son langage dénoté est $L_{(r){*}} := L^*$.
 \end{itemize}
 
 Un langage rationnel est par construction la même chose qu'un langage
@@ -953,10 +969,10 @@ On verra plus loin (en \ref{equivalence-of-regexps-is-decidable})
 qu'on dispose d'un algorithme permettant de décider si deux
 expressions rationnelles sont équivalentes.
 
-{\footnotesize\thingy Voici quelques exemples d'équivalences
-  d'expressions rationnelles (valables en remplaçant les différents
-  $r$ qui interviennent dedans par des expressions rationnelles
-  quelconques) :
+{\footnotesize\thingy\label{regexp-identities} Voici quelques exemples
+  d'équivalences d'expressions rationnelles (valables en remplaçant
+  les différents $r$ qui interviennent dedans par des expressions
+  rationnelles quelconques) :
 
 \begin{itemize}
 \item identités « triviales » :\quad $(r|\bot)\equiv r$,\quad
@@ -1012,6 +1028,31 @@ pas comme $(ab){*}$), la concaténation est de priorité intermédiaire,
 et la barre de disjonction $|$ est la moins prioritaire (c'est-à-dire
 que $ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$).
 
+\thingy\label{regexp-notation-variations} La disjonction que nous
+avons notée « ${|}$ » est plus souvent notée « $+$ » par les
+mathématiciens\footnote{Dans le même contexte mathématique, il est
+  alors fréquent de noter « $0$ » pour ce que nous avons
+  noté « $\bot$ » (c'est un élément neutre pour la disjonction), et on
+  en profite souvent pour noter « $1$ » pour « $\varepsilon$ » et/ou
+  « $\underline{\varepsilon}$ » (c'est un élément neutre pour la
+  concaténation).  Par exemple, beaucoup des identités énoncées
+  en \ref{regexp-identities} sembleront plus naturelles si on les
+  écrit avec ces notations.}.  Cette notation est plus élégante pour
+faire le lien avec l'algèbre, et plus logique dans des cadres plus
+généraux (expressions rationnelles et automates « avec
+multiplicités ») ; nous avons cependant préféré l'éviter parce qu'elle
+prête à confusion : en effet, on a introduit en \ref{kleene-plus} une
+opération $L \mapsto L^+$ qui n'a rien à voir avec la disjonction, et
+de nombreux moteurs d'expressions régulières en informatique (par
+exemple, \texttt{egrep},
+cf. §\ref{subsection-remarks-on-regexp-syntax}) utilisent
+effectivement le symbole \texttt{+} dans ce sens, c'est-à-dire pour
+désigner « au moins une répétition »
+(cf. \ref{remarks-egrep-plus-etc}).  Même si nous avons cherché à ne
+pas utiliser le symbole $+$ pour éviter l'ambiguïté, il faut savoir
+que ce double sens existe (soit comme disjonction, soit comme
+l'opération de \ref{kleene-plus}).
+
 {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
   sont introduits ici par souci de complétude mais font rarement
   utilisés dans les expressions rationnelles (le métacaractère
@@ -1019,23 +1060,6 @@ que $ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$).
   vraie lettre et non pas du mot vide ; on peut ignorer cette
   subtilité qui n'a que très peu d'importance).\par}
 
-La barre de disjonction que nous avons notée « ${|}$ » est souvent
-plutôt notée « $+$ » par les mathématiciens\footnote{Dans le même
-  contexte mathématique, il est alors fréquent de noter « $0$ » pour
-  ce que nous avons noté « $\bot$ » (c'est un élément neutre pour la
-  disjonction), et on en profite souvent pour noter « $1$ » pour
-  « $\varepsilon$ » et/ou « $\underline{\varepsilon}$ » (c'est un
-  élément neutre pour la concaténation).}.  Il y a ici un risque de
-confusion lié au fait 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{\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}\label{subsection-remarks-on-regexp-syntax}
 
@@ -1045,45 +1069,59 @@ s'agisse de primitives d'un langage, de bibliothèques externes, de
 programmes en ligne de commande, ou autres) permettant de savoir si un
 mot est reconnu par une expression régulière (=rationnelle), autrement
 dit, s'il appartient au langage dénoté par elle.  L'un de ces moteurs
-est le programme \texttt{egrep} standard sous Unix/POSIX.
+est le programme \texttt{egrep} standard sous Unix/POSIX ; un autre
+est le moteur \texttt{java.util.regex} de Java.
 
 \thingy Les expressions régulières au sens de ces différents moteurs
 sont généralement plus puissantes que les expressions rationnelles au
-sens mathématique défini ci-dessus : différentes extensions permettent
-de désigner des langages qui ne sont pas rationnels au sens
-mathématique.  L'extension la plus fréquente est celle des
-\emph{références arrière} (ou \emph{backreferences} en anglais) qui
-permettent de demander qu'un facteur du mot se retrouve aussi à un
-autre emplacement.  Par exemple, pour beaucoup de moteurs (notamment
-\texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} »
-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 » \ref{pumping-lemma}).
+sens mathématique défini en \ref{regular-expressions} ci-dessus :
+différentes extensions permettent de désigner des langages qui ne sont
+pas rationnels au sens mathématique.
+
+L'extension la plus fréquente est celle des \emph{références arrière}
+(ou \emph{backreferences} en anglais) qui permettent de demander qu'un
+facteur du mot se retrouve aussi à un autre emplacement.  Par exemple,
+pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression
+régulière « \texttt{(a*)b\char"5C\relax 1} » 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$} (le « \texttt{\char"5C\relax 1} » désigne
+« une copie de la chaîne de caractères qui a été capturée par le
+premier jeu de parenthèses ») ; or ce langage \emph{n'est pas
+  rationnel} au sens mathématique (ce sera une conséquence du « lemme
+de pompage » \ref{pumping-lemma}), c'est donc bien le signe qu'on sort
+du cadre théorique décrit plus haut.
 
 \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{\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 de $\Sigma$ — ce qui serait très fastidieux à écrire
-si on devait énumérer tout Unicode), ou bien « \texttt{[$xyz$]} » qui
-désigne un caractère quelconque parmi ceux listés (c'est donc la même
-chose que $(x|y|z)$ mais cela ne fonctionne qu'avec des caractères
-individuels ; en contrepartie, on peut écrire des intervalles comme
-« \texttt{[a-z]} » qui désigne un caractère quelconque entre
-\texttt{a} et \texttt{z} dans l'ordre ASCII/Unicode\footnote{...ou
-  parfois l'ordre de tri défini par la locale en cours : c'est
-  malheureusement une source supplémentaire de confusion et de bugs.},
-ou bien des négations, comme « \texttt{[\char"5Ea-z]} » qui désigne un
-caractère qui \emph{n'est pas} entre \texttt{a} et \texttt{z}) ou
+commodités d'écriture dans un contexte informatique.
+
+Parmi les caractères les plus courants de cette sorte, mentionnons le
+\texttt{+} qui signifie « au moins une répétition » (alors que
+\texttt{*} signifie « au moins zéro répétitions ») : ainsi,
+« $r\texttt{+}$ » est équivalent à $rr{*}$ ; on trouve aussi
+\texttt{?} pour « au plus une répétition » : c'est-à-dire que
+« $r\texttt{?}$ » est équivalent à $(\underline{\varepsilon}|r)$ (qui
+sera d'ailleurs simplement noté $(|r)$ car il n'y a jamais de symbole
+spécial pour $\underline{\varepsilon}$).
+
+Parmi d'autres constructions qui ne sortent pas du cadre théorique des
+langages rationnels, 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 de $\Sigma$ — ce qui serait très fastidieux à
+écrire si on devait énumérer tout Unicode).  Les crochets tels que
+« \texttt{[$xyz$]} » désignent un caractère quelconque parmi ceux
+listés (c'est donc la même chose que $(x|y|z)$ mais cela ne fonctionne
+qu'avec des caractères individuels ; en contrepartie, on peut écrire
+des intervalles comme « \texttt{[a-z]} » qui désigne un caractère
+quelconque entre \texttt{a} et \texttt{z} dans l'ordre
+ASCII/Unicode\footnote{...ou parfois l'ordre de tri défini par la
+  locale en cours : c'est malheureusement une source supplémentaire de
+  confusion et de bugs.}, ou bien des négations, comme
+« \texttt{[\char"5Ea-z]} » qui désigne un caractère qui \emph{n'est
+  pas} entre \texttt{a} et \texttt{z}) ou
 « \texttt{[\char"5Eaeio-z]} » qui désigne un caractère qui \emph{n'est
   ni} \texttt{a} ni \texttt{e} ni\texttt{i} ni entre \texttt{o}
 et \texttt{z}).
@@ -1092,7 +1130,8 @@ Toutes sortes d'autres racourcis ou commodités de notation peuvent
 exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour
 désigner un début et une fin de mot (la définition précise de « mot »
 pouvant varier), ou encore \texttt{$r$\{$n_1$,$n_2$\}} qui cherche
-entre $n_1$ et $n_2$ répétitions de $r$.
+entre $n_1$ et $n_2$ répétitions de $r$ : ainsi,
+« $r\texttt{\{2,5\}}$ » est équivalent à $(rr|rrr|rrrr|rrrrr)$.
 
 \thingy Une autre subtilité est que la plupart des moteurs
 d'expressions régulières en informatique vont, par défaut,
@@ -1137,8 +1176,8 @@ moteur d'expressions régulières pour connaître la syntaxe utilisée.
 Signalons tout de même qu'il existe deux principales familles de
 syntaxes d'expressions régulières en informatique : les expressions
 régulières « POSIX étendues », utilisée notamment par le programme
-Unix \texttt{egrep}, et les expressions régulières Perl, qui ont été
-réadaptées dans beaucoup de langages, notamment Java, JavaScript,
+Unix \texttt{egrep}, et les expressions régulières de Perl, qui ont
+été réadaptées dans beaucoup de langages, notamment Java, JavaScript,
 Python et d'autres.
 
 \thingy Signalons comme complication supplémentaire que dans de