Section on rational languages: add informal introduction, some clarifications.

1 files changed, 154 insertions, 69 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 24e9fc3..82e8241 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -508,12 +508,13 @@ 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
 une chaîne de caractères et renvoyant un booléen.
 
-\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
-alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
-peut former les langages \defin[union (de langages)]{union} $L_1\cup
-L_2$ et \defin[intersection (de langages)]{intersection} $L_1\cap L_2$
-qui sont simplement les opérations ensemblistes usuelles (entre
-parties de $\Sigma^*$).
+\thingy\label{union-and-intersection-of-languages} Si $L_1$ et $L_2$
+sont deux langages sur un même alphabet $\Sigma$ (autrement dit,
+$L_1,L_2 \subseteq \Sigma^*$), on peut former les langages
+\defin[union (de langages)]{union} $L_1\cup L_2$ et
+\defin[intersection (de langages)]{intersection} $L_1\cap L_2$ qui
+sont simplement les opérations ensemblistes usuelles (entre parties
+de $\Sigma^*$).
 
 Les opérations correspondantes sur les propriétés de mots sont
 respectivement le « ou logique » (=disjonction) et le « et logique »
@@ -539,12 +540,12 @@ $\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur
 $\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien
 commence par $b$).
 
-\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
-alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
-peut former le langage \defin[concaténation (de
-  langages)]{concaténation} $L_1 L_2$ : il est 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
+\thingy\label{concatenation-of-languages} Si $L_1$ et $L_2$ sont deux
+langages sur un même alphabet $\Sigma$ (autrement dit, $L_1,L_2
+\subseteq \Sigma^*$), on peut former le langage \defin[concaténation
+  (de langages)]{concaténation} $L_1 L_2$ : il est 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\}\\
@@ -631,17 +632,18 @@ c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
 
 \medbreak
 
-\thingy De même que l'ensemble des mots sur un alphabet $\Sigma$ admet
-une notation, à savoir $\Sigma^*$, on peut introduire une notation
-pour l'ensemble de tous les \emph{langages} (= ensembles de mots)
-sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$.  Il s'agit d'un cas
-particulier de la construction « ensemble des parties » (si $E$ est un
-ensemble, $\mathscr{P}(E) = \{A : A\subseteq E\}$ est l'ensemble de
-tous les sous-ensembles de $A$ ; c'est un axiome de la théorie des
-ensembles qu'un tel ensemble existe bien).  On pourrait donc écrire
-« $L \in \mathscr{P}(\Sigma^*)$ » comme synonyme de « $L\subseteq
-\Sigma^*$ » ou de « $L$ est un langage sur $\Sigma$ » ; on évitera
-cependant de le faire, car cette notation est plus lourde qu'utile.
+\thingy\label{set-of-languages} De même que l'ensemble des mots sur un
+alphabet $\Sigma$ admet une notation, à savoir $\Sigma^*$, on peut
+introduire une notation pour l'ensemble de tous les \emph{langages}
+(= ensembles de mots) sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$.
+Il s'agit d'un cas particulier de la construction « ensemble des
+parties » (si $E$ est un ensemble, $\mathscr{P}(E) = \{A : A\subseteq
+E\}$ est l'ensemble de tous les sous-ensembles de $A$ ; c'est un
+axiome de la théorie des ensembles qu'un tel ensemble existe bien).
+On pourrait donc écrire « $L \in \mathscr{P}(\Sigma^*)$ » comme
+synonyme de « $L\subseteq \Sigma^*$ » ou de « $L$ est un langage
+sur $\Sigma$ » ; on évitera cependant de le faire, car cette notation
+est plus lourde qu'utile.
 
 {\footnotesize Il sera marginalement question dans ces notes de
   « classes de langages » : une classe de langages est un ensemble de
@@ -659,10 +661,70 @@ cependant de le faire, car cette notation est plus lourde qu'utile.
 
 \subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
 
-\textcolor{red}{TODO: Commencer par une explication informelle.}
+\thingy \textbf{Introduction :} Les langages qui vont jouer le rôle le
+plus important dans ces notes sont les langages dits « rationnels »
+(qui seront définis de \ref{rational-languages} à
+\ref{regular-expressions} ci-dessous, et qui s'avéreront être les
+mêmes que les langages « reconnaissables » par automates finis définis
+en \ref{definition-recognizable-language}).
+
+Pour donner un premier aperçu informel de ce dont il s'agit avant de
+passer à une définition précise, commençons par donner quelques
+exemples, disons, sur l'alphabet $\Sigma = \{a,b,c,d\}$, de langages
+rationnels :
+\begin{itemize}
+\item le langage constitué des mots contenant au moins un $d$ ;
+\item le langage constitué des mots ne contenant aucun $d$ ;
+\item le langage constitué des mots commençant par un $d$ ;
+\item le langage constitué des mots commençant par un $d$ et
+  finissant par un $c$ ;
+\item le langage constitué des mots commençant par un $d$ et finissant
+  par un $c$, et dont toutes les lettres intermédiaires sont des $a$
+  ou des $b$, c'est-à-dire, le langage constitué des mots de la forme
+  suivante : un $d$, puis un nombre quelconque de $a$ et de $b$, et
+  enfin un $c$ ;
+\item le langage constitué des mots de la forme suivante : un $d$,
+  puis un nombre quelconque de mots qui peuvent être soit $a$ soit
+  $bb$, et enfin un $c$.
+\end{itemize}
 
-\thingy Soit $\Sigma$ un alphabet.  On va considérer les langages
-de base triviaux suivants :
+Ce dernier exemple est assez typique : on dira plus loin qu'il s'agit
+du langage « dénoté » par l'expression rationnelle $d(a|bb){*}c$, à
+lire comme « un $d$, puis autant qu'on veut (“$*$”) de mots qui
+peuvent être soit (“$|$”) un $a$ soit $bb$, et enfin un $c$ ».  Les
+constructions essentielles qui permettront de fabriquer les langages
+rationnels sont : la réunion (j'autorise ceci \emph{ou} cela, par
+exemple « un $a$ \emph{ou bien} $bb$ »,
+cf. \ref{union-and-intersection-of-languages}), la concaténation (je
+demande ceci \emph{puis} cela, par exemple « un $d$, \emph{puis} une
+suite quelconque de $a$ ou de $b$ »,
+cf. \ref{concatenation-of-languages}), et l'étoile de Kleene
+(représentant une répétition quelconque d'un certain motif,
+cf. \ref{kleene-star}).
+
+L'importance des langages rationnels, et des expressions rationnelles
+(=régulières) qui les décrivent, vient :
+\begin{itemize}
+\item du point de vue théorique : de ce qu'ils forment une classe à la
+  fois suffisamment simple pour pouvoir être étudiée, suffisamment
+  riche pour contenir toutes sortes de langages intéressants,
+  suffisamment naturelle pour être définie de plusieurs manières
+  différentes, et suffisamment flexible pour être stable un certain
+  nombre d'opérations ;
+\item du point de vue pratique et informatique : de ce qu'ils sont
+  algorithmiquement commodes à manier (grâce à la théorie) et
+  suffisent à représenter beaucoup de « recherches » qu'on a
+  naturellement envie de faire dans un texte, de « motifs » qu'on peut
+  vouloir trouver, ou de « contraintes » qu'on peut vouloir imposer à
+  une chaîne de caractères.
+\end{itemize}
+
+Passons maintenant à une définition plus précise.
+
+\bigbreak
+
+\thingy\label{rational-languages} Soit $\Sigma$ un alphabet.  On va
+considérer les langages de base triviaux suivants :
 \begin{itemize}
 \item le langage vide $\varnothing$,
 \item le langage constitué du seul mot vide, $\{\varepsilon\}$, et
@@ -672,21 +734,25 @@ de base triviaux suivants :
 et on va les combiner par les opérations dites « rationnelles »
 suivantes :
 \begin{itemize}
-\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$,
-\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$, et
-\item l'étoile de Kleene $L \mapsto L^*$.
+\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$
+  (discutée en \ref{union-and-intersection-of-languages}),
+\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$
+  (définie en \ref{concatenation-of-languages}), et
+\item l'étoile de Kleene $L \mapsto L^*$
+  (définie en \ref{kleene-star}).
 \end{itemize}
 
 On obtient ainsi une certaine famille de langages (cf. ci-dessous pour
 une définition plus précise), qu'on appelle \defin[rationnel
-  (langage)]{langages rationnels} : les langages rationnels sont
-exactement ceux qui peuvent s'obtenir à partir des langages de base
-énumérés ci-dessus par application (un nombre fini de fois) des
-opérations qu'on vient de dire.  Autrement dit, la réunion de deux
-langages rationnels, la concaténation de deux langages rationnels, et
-l'étoile de Kleene d'un langage rationnel, sont rationnels, et les
-langages rationnels sont exactement ceux qu'on obtient ainsi à partir
-des langages de base.
+  (langage)]{langages rationnels} : les langages rationnels sont par
+définition exactement ceux qui peuvent s'obtenir à partir des langages
+de base énumérés ci-dessus par application (un nombre \emph{fini} de
+fois) des opérations qu'on vient de dire.
+
+Autrement dit, la réunion de deux langages rationnels, la
+concaténation de deux langages rationnels, et l'étoile de Kleene d'un
+langage rationnel, sont rationnels ; et les langages rationnels sont
+exactement ceux qu'on obtient ainsi à partir des langages de base.
 
 À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage
 $\{c\}$ (constitué du seul mot $c$) est rationnel, son étoile de
@@ -698,18 +764,27 @@ encore un langage rationnel.
 \thingy Formellement, la définition des langages rationnelles est la
 suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$
 de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de
-$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$) est
-dit \emph{stable par opérations rationnelles} lorsqu'il est stable par
-les opérations de réunion, concaténation et étoile de Kleene, i.e., si
-$L_1,L_2 \in \mathscr{C}$ alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1
-L_2 \in \mathscr{C}$, et si $L \in \mathscr{C}$ alors $L^* \in
-\mathscr{C}$ ; le \emph{plus petit} (pour l'inclusion) ensemble de
-langages stable par opérations rationnelles et contenant les langages
-$\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in \Sigma$
-(i.e. $\varnothing\in\mathscr{C}$, $\{\varepsilon\} \in \mathscr{C}$
-et si $x\in\Sigma$ alors $\{x\}\in\mathscr{C}$), ou plus exactement,
-l'intersection de tous les ensembles $\mathscr{C}$ vérifiant tous ces
-propriétés, est la classe $\mathscr{R}$ des langages rationnels.
+$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$,
+cf. \ref{set-of-languages}) est dit \emph{stable par opérations
+  rationnelles} lorsqu'il est stable par les opérations de réunion,
+concaténation et étoile de Kleene, i.e., si $L_1,L_2 \in \mathscr{C}$
+alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1 L_2 \in \mathscr{C}$, et
+si $L \in \mathscr{C}$ alors $L^* \in \mathscr{C}$ ; le \emph{plus
+  petit}\footnote{La classe des langages rationnelles (qu'on cherche à
+  définir) n'est pas le seul ensemble de langages stable par
+  opérations rationnelles : l'ensemble $\mathscr{P}(\Sigma^*)$ de tous
+  les langages est aussi évidemment stable par opérations
+  rationnelles ; on s'intéresse au plus petit $\mathscr{C}$ possible
+  pour n'avoir que ce qui est nécessairement construit à partir des
+  langages de base triviaux par les opérations rationnelles.}  (pour
+l'inclusion) ensemble de langages stable par opérations rationnelles
+et contenant les langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$
+pour $x \in \Sigma$ (i.e. $\varnothing\in\mathscr{C}$,
+$\{\varepsilon\} \in \mathscr{C}$ et si $x\in\Sigma$ alors
+$\{x\}\in\mathscr{C}$), ou plus exactement, l'intersection de tous les
+ensembles $\mathscr{C}$ vérifiant tous ces propriétés, est la classe
+$\mathscr{R}$ des langages rationnels (et un langage rationnel est
+simplement un élément de $\mathscr{R}$).
 
 \emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages
 rationnels soit stable par concaténation signifie que si $L_1$ et
@@ -719,16 +794,19 @@ rationnel ; \emph{cela ne signifie pas} qu'un langage rationnel donné
 soit stable par concaténation (un langage stable $L$ par concaténation
 est un langage tel que si $w_1,w_2\in L$ alors $w_1 w_2 \in L$).
 
-\thingy Pour décrire la manière dont un langage rationnel est fabriqué
-(à partir des langages de base par les opérations rationnelles), comme
-il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on
-introduit un nouvel objet, les \index{expression
-  rationnelle|see{rationnelle (expression)}}\defin[rationnelle
-  (expression)]{expressions rationnelles} (certains préfèrent le terme
-d'\index{régulière (expression)|see{rationnelle}}\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{*}$ ».
+\thingy\label{regular-expressions} Pour décrire la manière dont un
+langage rationnel est fabriqué (à partir des langages de base par les
+opérations rationnelles), comme il est malcommode d'écrire quelque
+chose comme $\{d\}(\{c\}^*)$, on introduit un nouvel objet, les
+\index{expression rationnelle|see{rationnelle
+    (expression)}}\defin[rationnelle (expression)]{expressions
+  rationnelles} (certains préfèrent le terme d'\index{régulière
+  (expression)|see{rationnelle}}\textbf{expressions régulières}), qui
+sont des expressions servant à dénoter un langage rationnel.  Par
+exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
+langage « dénoté par l'expression rationnelle $dc{*}$ ».  Ceci fournit
+du même coup une nouvelle définition des langages rationnels : ce sont
+les langages dénotés par une expression rationnelle.
 
 Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
 est un mot sur l'alphabet $\Sigma \cup \{\bot,
@@ -762,6 +840,9 @@ par l'expression $r$, de la manière suivante :
   et son langage dénoté est $L_{(r){*}} := L^*$.
 \end{itemize}
 
+Un langage rationnel est par construction la même chose qu'un langage
+pour lequel il existe une expression rationnelle qui le dénote.
+
 \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,
@@ -792,9 +873,6 @@ $\Sigma = \{a,b,c,d\}$ :
   langage $\{\varepsilon, c\}$.
 \end{itemize}
 
-Un langage rationnel est par construction la même chose qu'un langage
-pour lequel il existe une expression rationnelle qui le dénote.
-
 \thingy On dira qu'un mot $w$ \defin[vérifier (une expression
   rationnelle)]{vérifie} une expression rationnelle $r$ lorsque ce mot
 appartient au langage qu'elle dénote (i.e., $w \in L_r$).  Par
@@ -809,16 +887,23 @@ $\{a, aba, ababa, \ldots\}$ constitué des mots commençant et finissant
 par un $a$ et dans lesquels chaque paire de $a$ est séparée par un
 unique $b$).
 
+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.
+
 \thingy La convention de parenthésage introduite ci-dessus est
 inambiguë mais parfois inutilement lourde : on se permettra parfois de
 l'alléger, par exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$
 (ou pour $(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles
 dénotent le même langage), ou encore $x{*}$ pour $(x){*}$ lorsque $x$
-est formé d'un seul caractère.  La convention essentielle est que
-l'opération d'étoile ${*}$ est la plus prioritaire ($ab{*}$ se lit
-comme $a(b){*}$ et non pas comme $(ab){*}$), la concaténation vient
-après, et la barre de disjonction $|$ est la moins prioritaire
-($ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$).
+est formé d'un seul caractère.
+
+Pour retirer des parenthèses, la convention sur la priorité des
+opérations est la suivante : l'opération d'étoile ${*}$ est la plus
+prioritaire (c'est-à-dire que $ab{*}$ se lit comme $a(b){*}$ et non
+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$).
 
 {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
   sont introduits ici par souci de complétude mais font rarement
@@ -845,7 +930,7 @@ 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}
+\subsection{Remarques sur les moteurs d'expressions régulières en informatique}\label{subsection-remarks-on-regexp-syntax}
 
 \thingy Dans le monde informatique, il existe de nombreux
 \emph{moteurs d'expressions régulières}, c'est-à-dire outils (qu'il
@@ -2951,7 +3036,7 @@ En revanche, si on change l'automate pour rendre l'état $4$ non-final
 aboutit sur la partition triviale en six états, c'est-à-dire que
 l'automate est, en fait, déjà minimal.
 
-\begin{cor}
+\begin{cor}\label{equivalence-of-regexps-is-decidable}
 On peut décider algorithmiquement si deux automates finis (de
 n'importe quelle sorte), ou deux expressions rationnelles, ou un
 automate et une expression rationnelle, sont équivalents (au sens de