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