summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-29 20:23:01 +0100
committerDavid A. Madore <david+git@madore.org>2017-10-29 20:23:01 +0100
commit19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe (patch)
treea1226c26bb9e8be308e695d6d3f90180161eb7de /notes-inf105.tex
parent16c784b986cf31911f339abed45a9465b62f3807 (diff)
downloadinf105-19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe.tar.gz
inf105-19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe.tar.bz2
inf105-19b8cdeed8635dc1ed48d9620da1dbcf1e88cabe.zip
Remark on various equivalences of rational expressions.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex65
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