summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex175
1 files changed, 107 insertions, 68 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 8862e5d..4533160 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -114,14 +114,16 @@ Git: \input{vcline.tex}
\setcounter{comcnt}{0}
-\thingy \textbf{Présentation et plan :} On se propose de développer
-ici des techniques mathématiques et algorithmiques ayant à la fois un
-intérêt théorique comme théorie des langages formels, et une
-application informatique pratique à l'analyse de textes ou de chaînes
-de caractères (qu'on appellera par la suite « mots »,
+\thingy \textbf{Présentation générale et plan :} On se propose de
+développer ici des techniques mathématiques et algorithmiques ayant à
+la fois un intérêt théorique comme théorie des langages formels, et
+une application informatique pratique à l'analyse de textes ou de
+chaînes de caractères (qu'on appellera par la suite « mots »,
cf. §\ref{subsection-introduction-and-words}).
-Ces notes sont divisées en grandes parties (inégales) de la manière
+Après des définitions générales (sections
+\ref{subsection-introduction-and-words} à \ref{subjection-languages}),
+ces notes sont divisées en grandes parties (inégales) de la manière
suivante :
\begin{itemize}
\item l'étude des expressions rationnelles et des automates finis, et
@@ -167,7 +169,7 @@ $A=B$ mais en insistant sur le fait que c'est la définition du membre
du côté duquel se situent les deux points). On note $\mathbb{N}$
l'ensemble $\{0,1,2,3\ldots\}$ des entiers naturels.
-Le symbole \qedsymbol marque la fin d'une démonstration.
+Le symbole \qedsymbol{} marque la fin d'une démonstration.
\section{Alphabets, mots et langages ; langages rationnels}\label{section-languages-and-rational-languages}
@@ -562,7 +564,7 @@ langage pourrait être considéré comme une propriété des mots.
appartenir à la partie en question.)\par}
On évitera de faire cette identification pour ne pas introduire de
-confusion, mais il est utile de la garder à l'esprit : par exemple,
+complication, mais il est utile de la garder à l'esprit : par exemple,
dans un langage de programmation fonctionnel, un « langage » au sens
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
@@ -895,11 +897,25 @@ suivante :
dénoté est $L_{r_1 r_2} := L_1 L_2$,
\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants,
- alors $(r_1|r_2)$ est une expression rationnelle et son langage
- dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$,
+ alors $(r_1|r_2)$ est une expression rationnelle\footnote{Certains
+ préfèrent la notation $r_1+r_2$ ici,
+ cf. \ref{regexp-notation-variations} pour une discussion.} et son
+ langage dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$,
\item si $r$ est une expression rationnelle et $L = L_r$ les langage
- dénoté correspondant, alors $(r){*}$ est une expression rationnelle
- et son langage dénoté est $L_{(r){*}} := L^*$.
+ dénoté correspondant, alors $(r){*}$ est une expression
+ rationnelle\footnote{Notons que certains auteurs préfèrent mettre le
+ $*$ en exposant ici, c'est-à-dire noter $(r)^*$ (comme nous
+ l'avons fait pour l'étoile de Kleene $L^*$ d'un langage $L$) ;
+ comme nous avons choisi de définir une expression rationnelle
+ comme un mot sur l'alphabet $\Sigma \cup \{\bot,
+ \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, il semble plus
+ raisonnable de ne pas rentrer dans la considération byzantine de
+ savoir si un mot peut contenir des symboles en exposant. En tout
+ état de cause, il n'apparaîtra jamais aucune circonstance où les
+ deux notations $X^*$ et $X{*}$ auraient tous les deux un sens et
+ que ces sens diffèrent ! On peut donc ignorer purement et
+ simplement la question de savoir si oui ou non l'étoile est en
+ exposant.} et son langage dénoté est $L_{(r){*}} := L^*$.
\end{itemize}
Un langage rationnel est par construction la même chose qu'un langage
@@ -953,10 +969,10 @@ 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.
-{\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) :
+{\footnotesize\thingy\label{regexp-identities} 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
@@ -1012,6 +1028,31 @@ 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$).
+\thingy\label{regexp-notation-variations} La disjonction que nous
+avons notée « ${|}$ » est plus souvent 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). Par exemple, beaucoup des identités énoncées
+ en \ref{regexp-identities} sembleront plus naturelles si on les
+ écrit avec ces notations.}. Cette notation est plus élégante pour
+faire le lien avec l'algèbre, et plus logique dans des cadres plus
+généraux (expressions rationnelles et automates « avec
+multiplicités ») ; nous avons cependant préféré l'éviter parce qu'elle
+prête à confusion : en effet, on a introduit en \ref{kleene-plus} une
+opération $L \mapsto L^+$ qui n'a rien à voir avec la disjonction, et
+de nombreux moteurs d'expressions régulières en informatique (par
+exemple, \texttt{egrep},
+cf. §\ref{subsection-remarks-on-regexp-syntax}) utilisent
+effectivement le symbole \texttt{+} dans ce sens, c'est-à-dire pour
+désigner « au moins une répétition »
+(cf. \ref{remarks-egrep-plus-etc}). Même si nous avons cherché à ne
+pas utiliser le symbole $+$ pour éviter l'ambiguïté, il faut savoir
+que ce double sens existe (soit comme disjonction, soit comme
+l'opération de \ref{kleene-plus}).
+
{\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
sont introduits ici par souci de complétude mais font rarement
utilisés dans les expressions rationnelles (le métacaractère
@@ -1019,23 +1060,6 @@ 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,
-\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
-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)$ (cf. \ref{remarks-egrep-plus-etc}).
-
\subsection{Remarques sur les moteurs d'expressions régulières en informatique}\label{subsection-remarks-on-regexp-syntax}
@@ -1045,45 +1069,59 @@ s'agisse de primitives d'un langage, de bibliothèques externes, de
programmes en ligne de commande, ou autres) permettant de savoir si un
mot est reconnu par une expression régulière (=rationnelle), autrement
dit, s'il appartient au langage dénoté par elle. L'un de ces moteurs
-est le programme \texttt{egrep} standard sous Unix/POSIX.
+est le programme \texttt{egrep} standard sous Unix/POSIX ; un autre
+est le moteur \texttt{java.util.regex} de Java.
\thingy Les expressions régulières au sens de ces différents moteurs
sont généralement plus puissantes que les expressions rationnelles au
-sens mathématique défini ci-dessus : différentes extensions permettent
-de désigner des langages qui ne sont pas rationnels au sens
-mathématique. L'extension la plus fréquente est celle des
-\emph{références arrière} (ou \emph{backreferences} en anglais) qui
-permettent de demander qu'un facteur du mot se retrouve aussi à un
-autre emplacement. Par exemple, pour beaucoup de moteurs (notamment
-\texttt{egrep}), l'expression régulière « \texttt{(a*)b\char"5C\relax 1} »
-désigne le langage $\{a^nba^n : a\in\mathbb{N}\} = \{b,aba,
-aabaa,\ldots\}$ des mots formés d'un nombre quelconque de $a$ puis
-d'un $b$ puis de la \emph{même suite de $a$}, et ce langage
-\emph{n'est pas rationnel} au sens mathématique (ce sera une
-conséquence du « lemme de pompage » \ref{pumping-lemma}).
+sens mathématique défini en \ref{regular-expressions} ci-dessus :
+différentes extensions permettent de désigner des langages qui ne sont
+pas rationnels au sens mathématique.
+
+L'extension la plus fréquente est celle des \emph{références arrière}
+(ou \emph{backreferences} en anglais) qui permettent de demander qu'un
+facteur du mot se retrouve aussi à un autre emplacement. Par exemple,
+pour beaucoup de moteurs (notamment \texttt{egrep}), l'expression
+régulière « \texttt{(a*)b\char"5C\relax 1} » désigne le langage
+$\{a^nba^n : a\in\mathbb{N}\} = \{b,aba, aabaa,\ldots\}$ des mots
+formés d'un nombre quelconque de $a$ puis d'un $b$ puis de la
+\emph{même suite de $a$} (le « \texttt{\char"5C\relax 1} » désigne
+« une copie de la chaîne de caractères qui a été capturée par le
+premier jeu de parenthèses ») ; or ce langage \emph{n'est pas
+ rationnel} au sens mathématique (ce sera une conséquence du « lemme
+de pompage » \ref{pumping-lemma}), c'est donc bien le signe qu'on sort
+du cadre théorique décrit plus haut.
\thingy\label{remarks-egrep-plus-etc} Il existe aussi un certain
nombre de constructions qui, sans dépasser la puissance des
expressions rationnelles au sens mathématique, apportent des
-commodités d'écriture dans un contexte informatique. On a déjà
-mentionné les symboles \texttt{+} (pour « au moins une répétition » :
-« $r{\scriptstyle +}$ » est équivalent à $rr{*}$) et \texttt{?} (pour
-« au plus une répétition » : « $r{?}$ » est équivalent à
-$(\underline{\varepsilon}|r)$). Parmi d'autres constructions du
-genre, mentionnons encore le point « \texttt{.} » qui désigne un
-caractère quelconque de l'alphabet (on peut le voir comme une
-abréviation pour $(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$ sont
-tous les éléments de $\Sigma$ — ce qui serait très fastidieux à écrire
-si on devait énumérer tout Unicode), ou bien « \texttt{[$xyz$]} » qui
-désigne un caractère quelconque parmi ceux listés (c'est donc la même
-chose que $(x|y|z)$ mais cela ne fonctionne qu'avec des caractères
-individuels ; en contrepartie, on peut écrire des intervalles comme
-« \texttt{[a-z]} » qui désigne un caractère quelconque entre
-\texttt{a} et \texttt{z} dans l'ordre ASCII/Unicode\footnote{...ou
- parfois l'ordre de tri défini par la locale en cours : c'est
- malheureusement une source supplémentaire de confusion et de bugs.},
-ou bien des négations, comme « \texttt{[\char"5Ea-z]} » qui désigne un
-caractère qui \emph{n'est pas} entre \texttt{a} et \texttt{z}) ou
+commodités d'écriture dans un contexte informatique.
+
+Parmi les caractères les plus courants de cette sorte, mentionnons le
+\texttt{+} qui signifie « au moins une répétition » (alors que
+\texttt{*} signifie « au moins zéro répétitions ») : ainsi,
+« $r\texttt{+}$ » est équivalent à $rr{*}$ ; on trouve aussi
+\texttt{?} pour « au plus une répétition » : c'est-à-dire que
+« $r\texttt{?}$ » est équivalent à $(\underline{\varepsilon}|r)$ (qui
+sera d'ailleurs simplement noté $(|r)$ car il n'y a jamais de symbole
+spécial pour $\underline{\varepsilon}$).
+
+Parmi d'autres constructions qui ne sortent pas du cadre théorique des
+langages rationnels, mentionnons encore le point « \texttt{.} » qui
+désigne un caractère quelconque de l'alphabet (on peut le voir comme
+une abréviation pour $(x_1|x_2|\ldots|x_N)$ où $x_1,x_2,\ldots,x_N$
+sont tous les éléments de $\Sigma$ — ce qui serait très fastidieux à
+écrire si on devait énumérer tout Unicode). Les crochets tels que
+« \texttt{[$xyz$]} » désignent un caractère quelconque parmi ceux
+listés (c'est donc la même chose que $(x|y|z)$ mais cela ne fonctionne
+qu'avec des caractères individuels ; en contrepartie, on peut écrire
+des intervalles comme « \texttt{[a-z]} » qui désigne un caractère
+quelconque entre \texttt{a} et \texttt{z} dans l'ordre
+ASCII/Unicode\footnote{...ou parfois l'ordre de tri défini par la
+ locale en cours : c'est malheureusement une source supplémentaire de
+ confusion et de bugs.}, ou bien des négations, comme
+« \texttt{[\char"5Ea-z]} » qui désigne un caractère qui \emph{n'est
+ pas} entre \texttt{a} et \texttt{z}) ou
« \texttt{[\char"5Eaeio-z]} » qui désigne un caractère qui \emph{n'est
ni} \texttt{a} ni \texttt{e} ni\texttt{i} ni entre \texttt{o}
et \texttt{z}).
@@ -1092,7 +1130,8 @@ Toutes sortes d'autres racourcis ou commodités de notation peuvent
exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour
désigner un début et une fin de mot (la définition précise de « mot »
pouvant varier), ou encore \texttt{$r$\{$n_1$,$n_2$\}} qui cherche
-entre $n_1$ et $n_2$ répétitions de $r$.
+entre $n_1$ et $n_2$ répétitions de $r$ : ainsi,
+« $r\texttt{\{2,5\}}$ » est équivalent à $(rr|rrr|rrrr|rrrrr)$.
\thingy Une autre subtilité est que la plupart des moteurs
d'expressions régulières en informatique vont, par défaut,
@@ -1137,8 +1176,8 @@ moteur d'expressions régulières pour connaître la syntaxe utilisée.
Signalons tout de même qu'il existe deux principales familles de
syntaxes d'expressions régulières en informatique : les expressions
régulières « POSIX étendues », utilisée notamment par le programme
-Unix \texttt{egrep}, et les expressions régulières Perl, qui ont été
-réadaptées dans beaucoup de langages, notamment Java, JavaScript,
+Unix \texttt{egrep}, et les expressions régulières de Perl, qui ont
+été réadaptées dans beaucoup de langages, notamment Java, JavaScript,
Python et d'autres.
\thingy Signalons comme complication supplémentaire que dans de