Remark on various equivalences of rational expressions.

1 files changed, 55 insertions, 10 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index fd86890..4831e7f 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -893,7 +893,52 @@ 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
+{\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) :
+
+\begin{itemize}
+\item identités « triviales » :\quad $(r|\bot)\equiv r$,\quad
+  $(\bot|r)\equiv r$,\quad $r\bot\equiv \bot$,\quad $\bot r\equiv
+  \bot$, \quad $r\underline{\varepsilon} \equiv r$,\quad
+  $\underline{\varepsilon}r \equiv r$,\quad $(\bot){*}\equiv
+  \underline{\varepsilon}$ ;
+\item identité d'associativité :\quad $((r_1|r_2)|r_3)\equiv
+  (r_1|(r_2|r_3))$ ;
+\item identités de distributivité :\quad $r(r_1|r_2)\equiv
+  (rr_1|rr_2)$,\quad $(r_1|r_2)r\equiv (r_1r|r_2r)$ ;
+\item identité de commutativité :\quad $(r_1|r_2)\equiv (r_2|r_1)$ ;
+\item identités « apériodiques » :\quad $((r_1|r_2)){*} \equiv
+  (r_1){*}(r_2(r_1){*}){*}$,\quad $((r_1|r_2)){*} \equiv
+  ((r_1){*}r_2){*}(r_1){*}$\quad et\quad $(r_1 r_2){*} \equiv
+  (\underline{\varepsilon}|r_1(r_2 r_1){*}r_2)$ ;
+\item identités « cycliques » :\quad $(r){*} \equiv
+  (\underline{\varepsilon}|r)(rr){*} \equiv
+  (\underline{\varepsilon}|r|rr)(rrr){*} \equiv
+  (\underline{\varepsilon}|r|rr|rrr)(rrrr){*} \equiv \cdots$ ;
+\item identités d'« idempotence » :\quad $(r|r)\equiv r$,\quad
+  $((r){*}){*} \equiv (r){*}$ ;
+\end{itemize}
+
+Ces différentes identités présentent un intérêt théorique dont
+l'explication dépasserait le cadre de ces notes ; cependant, il peut
+être intéressant de réfléchir à ce que chacune signifie.
+
+Signalons au passage que toutes ces identités \emph{ne suffisent pas}
+à produire toutes les équivalences entre expressions rationnelles.
+Par exemple, elles ne permettent pas de démontrer l'équivalence
+suivante : $(a|b){*} \equiv
+((a|b)(b|ab{*}ab{*}ab{*}a)){*}(\underline{\varepsilon}|(a|b)(|ab{*}|ab{*}ab{*}|ab{*}ab{*}ab{*}))$
+(écrite avec les conventions de \ref{convention-on-writing-regexps}) ;
+la question d'arriver à trouver un système d'axiomes qui permet de
+déduire toutes les équivalences entre expressions rationnelles est un
+problème délicat.
+
+\par}
+
+\thingy\label{convention-on-writing-regexps}
+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
@@ -914,15 +959,15 @@ 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,
+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