diff options
| -rw-r--r-- | notes-inf105.tex | 65 |
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 |