Various additional remarks on regular expressions.

1 files changed, 52 insertions, 33 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 0b9e751..05844ca 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -567,10 +567,10 @@ une définition plus précise), qu'on appelle \textbf{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 (i.e., la réunion de deux langages rationnels, ou la
-concaténation de deux langages rationnels, ou l'étoile de Kleene d'un
+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).
+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\}$ (formé du seul mot $c$) est rationnel, son étoile de Kleene,
@@ -579,23 +579,29 @@ rationnel, et comme $\{d\}$ l'est aussi, la concaténation
 $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage
 rationnel.
 
-{\footnotesize\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. \par}
+\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.
+
+\emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages
+rationnels soit stable par concaténation signifie que si $L_1$ et
+$L_2$ sont rationnels alors le langage $L_1 L_2$ (formé de tous les
+mots concaténés d'un mot de $L_1$ et d'un mot de $L_2$) est
+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
@@ -654,7 +660,16 @@ $\Sigma = \{a,b,c,d\}$ :
 \item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\}
   \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
 \item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d,
-  bcd, bcbcd, bcbcbcd, \ldots\}$.
+  bcd, bcbcd, bcbcbcd, \ldots\}$ ;
+\item l'expression rationnelle $\bot d$ dénote le langage
+  vide $\varnothing$ (car il n'y a pas de mot dans le langage vide,
+  donc pas non plus de mot dans sa concaténation avec le
+  langage $\{d\}$) ;
+\item l'expression rationnelle $\underline{\varepsilon} d$ dénote le
+  langage $\{d\}$ ;
+\item l'expression rationnelle $(\bot|c)$ dénote le langage $\{c\}$ ;
+\item l'expression rationnelle $(\underline{\varepsilon}|c)$ dénote le
+  langage $\{\varepsilon, c\}$.
 \end{itemize}
 
 Un langage rationnel est par construction la même chose qu'un langage
@@ -664,16 +679,16 @@ 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){*}$.
 
-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$).
+\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$).
 
 {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
   sont introduits ici par souci de complétude mais font rarement
@@ -686,8 +701,12 @@ La barre de disjonction que nous avons notée ${|}$ est souvent plutôt
 notée $+$ par les mathématiciens.  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}
-(de sorte que $r+$ a le même sens que $rr{*}$).
+\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)$.
 
 \thingy Deux expressions rationnelles $r_1,r_2$ sont dites
 \textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre