diff options
| -rw-r--r-- | notes-inf105.tex | 223 |
1 files changed, 154 insertions, 69 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 24e9fc3..82e8241 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -508,12 +508,13 @@ 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 une chaîne de caractères et renvoyant un booléen. -\thingy Si $L_1$ et $L_2$ sont deux langages sur un même -alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on -peut former les langages \defin[union (de langages)]{union} $L_1\cup -L_2$ et \defin[intersection (de langages)]{intersection} $L_1\cap L_2$ -qui sont simplement les opérations ensemblistes usuelles (entre -parties de $\Sigma^*$). +\thingy\label{union-and-intersection-of-languages} Si $L_1$ et $L_2$ +sont deux langages sur un même alphabet $\Sigma$ (autrement dit, +$L_1,L_2 \subseteq \Sigma^*$), on peut former les langages +\defin[union (de langages)]{union} $L_1\cup L_2$ et +\defin[intersection (de langages)]{intersection} $L_1\cap L_2$ qui +sont simplement les opérations ensemblistes usuelles (entre parties +de $\Sigma^*$). Les opérations correspondantes sur les propriétés de mots sont respectivement le « ou logique » (=disjonction) et le « et logique » @@ -539,12 +540,12 @@ $\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur $\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien commence par $b$). -\thingy Si $L_1$ et $L_2$ sont deux langages sur un même -alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on -peut former le langage \defin[concaténation (de - langages)]{concaténation} $L_1 L_2$ : il est défini comme l'ensemble -des mots $w$ qui peuvent s'écrire comme concaténation d'un mot $w_1$ -de $L_1$ et d'un mot $w_2$ de $L_2$, soit +\thingy\label{concatenation-of-languages} Si $L_1$ et $L_2$ sont deux +langages sur un même alphabet $\Sigma$ (autrement dit, $L_1,L_2 +\subseteq \Sigma^*$), on peut former le langage \defin[concaténation + (de langages)]{concaténation} $L_1 L_2$ : il est défini comme +l'ensemble des mots $w$ qui peuvent s'écrire comme concaténation d'un +mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit \[ \begin{aligned} L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\ @@ -631,17 +632,18 @@ c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$. \medbreak -\thingy De même que l'ensemble des mots sur un alphabet $\Sigma$ admet -une notation, à savoir $\Sigma^*$, on peut introduire une notation -pour l'ensemble de tous les \emph{langages} (= ensembles de mots) -sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$. Il s'agit d'un cas -particulier de la construction « ensemble des parties » (si $E$ est un -ensemble, $\mathscr{P}(E) = \{A : A\subseteq E\}$ est l'ensemble de -tous les sous-ensembles de $A$ ; c'est un axiome de la théorie des -ensembles qu'un tel ensemble existe bien). On pourrait donc écrire -« $L \in \mathscr{P}(\Sigma^*)$ » comme synonyme de « $L\subseteq -\Sigma^*$ » ou de « $L$ est un langage sur $\Sigma$ » ; on évitera -cependant de le faire, car cette notation est plus lourde qu'utile. +\thingy\label{set-of-languages} De même que l'ensemble des mots sur un +alphabet $\Sigma$ admet une notation, à savoir $\Sigma^*$, on peut +introduire une notation pour l'ensemble de tous les \emph{langages} +(= ensembles de mots) sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$. +Il s'agit d'un cas particulier de la construction « ensemble des +parties » (si $E$ est un ensemble, $\mathscr{P}(E) = \{A : A\subseteq +E\}$ est l'ensemble de tous les sous-ensembles de $A$ ; c'est un +axiome de la théorie des ensembles qu'un tel ensemble existe bien). +On pourrait donc écrire « $L \in \mathscr{P}(\Sigma^*)$ » comme +synonyme de « $L\subseteq \Sigma^*$ » ou de « $L$ est un langage +sur $\Sigma$ » ; on évitera cependant de le faire, car cette notation +est plus lourde qu'utile. {\footnotesize Il sera marginalement question dans ces notes de « classes de langages » : une classe de langages est un ensemble de @@ -659,10 +661,70 @@ cependant de le faire, car cette notation est plus lourde qu'utile. \subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages} -\textcolor{red}{TODO: Commencer par une explication informelle.} +\thingy \textbf{Introduction :} Les langages qui vont jouer le rôle le +plus important dans ces notes sont les langages dits « rationnels » +(qui seront définis de \ref{rational-languages} à +\ref{regular-expressions} ci-dessous, et qui s'avéreront être les +mêmes que les langages « reconnaissables » par automates finis définis +en \ref{definition-recognizable-language}). + +Pour donner un premier aperçu informel de ce dont il s'agit avant de +passer à une définition précise, commençons par donner quelques +exemples, disons, sur l'alphabet $\Sigma = \{a,b,c,d\}$, de langages +rationnels : +\begin{itemize} +\item le langage constitué des mots contenant au moins un $d$ ; +\item le langage constitué des mots ne contenant aucun $d$ ; +\item le langage constitué des mots commençant par un $d$ ; +\item le langage constitué des mots commençant par un $d$ et + finissant par un $c$ ; +\item le langage constitué des mots commençant par un $d$ et finissant + par un $c$, et dont toutes les lettres intermédiaires sont des $a$ + ou des $b$, c'est-à-dire, le langage constitué des mots de la forme + suivante : un $d$, puis un nombre quelconque de $a$ et de $b$, et + enfin un $c$ ; +\item le langage constitué des mots de la forme suivante : un $d$, + puis un nombre quelconque de mots qui peuvent être soit $a$ soit + $bb$, et enfin un $c$. +\end{itemize} -\thingy Soit $\Sigma$ un alphabet. On va considérer les langages -de base triviaux suivants : +Ce dernier exemple est assez typique : on dira plus loin qu'il s'agit +du langage « dénoté » par l'expression rationnelle $d(a|bb){*}c$, à +lire comme « un $d$, puis autant qu'on veut (“$*$”) de mots qui +peuvent être soit (“$|$”) un $a$ soit $bb$, et enfin un $c$ ». Les +constructions essentielles qui permettront de fabriquer les langages +rationnels sont : la réunion (j'autorise ceci \emph{ou} cela, par +exemple « un $a$ \emph{ou bien} $bb$ », +cf. \ref{union-and-intersection-of-languages}), la concaténation (je +demande ceci \emph{puis} cela, par exemple « un $d$, \emph{puis} une +suite quelconque de $a$ ou de $b$ », +cf. \ref{concatenation-of-languages}), et l'étoile de Kleene +(représentant une répétition quelconque d'un certain motif, +cf. \ref{kleene-star}). + +L'importance des langages rationnels, et des expressions rationnelles +(=régulières) qui les décrivent, vient : +\begin{itemize} +\item du point de vue théorique : de ce qu'ils forment une classe à la + fois suffisamment simple pour pouvoir être étudiée, suffisamment + riche pour contenir toutes sortes de langages intéressants, + suffisamment naturelle pour être définie de plusieurs manières + différentes, et suffisamment flexible pour être stable un certain + nombre d'opérations ; +\item du point de vue pratique et informatique : de ce qu'ils sont + algorithmiquement commodes à manier (grâce à la théorie) et + suffisent à représenter beaucoup de « recherches » qu'on a + naturellement envie de faire dans un texte, de « motifs » qu'on peut + vouloir trouver, ou de « contraintes » qu'on peut vouloir imposer à + une chaîne de caractères. +\end{itemize} + +Passons maintenant à une définition plus précise. + +\bigbreak + +\thingy\label{rational-languages} Soit $\Sigma$ un alphabet. On va +considérer les langages de base triviaux suivants : \begin{itemize} \item le langage vide $\varnothing$, \item le langage constitué du seul mot vide, $\{\varepsilon\}$, et @@ -672,21 +734,25 @@ de base triviaux suivants : et on va les combiner par les opérations dites « rationnelles » suivantes : \begin{itemize} -\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$, -\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$, et -\item l'étoile de Kleene $L \mapsto L^*$. +\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$ + (discutée en \ref{union-and-intersection-of-languages}), +\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$ + (définie en \ref{concatenation-of-languages}), et +\item l'étoile de Kleene $L \mapsto L^*$ + (définie en \ref{kleene-star}). \end{itemize} On obtient ainsi une certaine famille de langages (cf. ci-dessous pour une définition plus précise), qu'on appelle \defin[rationnel - (langage)]{langages rationnels} : les langages rationnels sont -exactement ceux qui peuvent s'obtenir à partir des langages de base -énumérés ci-dessus par application (un nombre fini de fois) des -opérations qu'on vient de dire. Autrement dit, la réunion de deux -langages rationnels, la concaténation de deux langages rationnels, et -l'étoile de Kleene d'un langage rationnel, sont rationnels, et les -langages rationnels sont exactement ceux qu'on obtient ainsi à partir -des langages de base. + (langage)]{langages rationnels} : les langages rationnels sont par +définition exactement ceux qui peuvent s'obtenir à partir des langages +de base énumérés ci-dessus par application (un nombre \emph{fini} de +fois) des opérations qu'on vient de dire. + +Autrement dit, la réunion de deux langages rationnels, la +concaténation de deux langages rationnels, et l'étoile de Kleene d'un +langage rationnel, sont rationnels ; et les langages rationnels sont +exactement ceux qu'on obtient ainsi à partir des langages de base. À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage $\{c\}$ (constitué du seul mot $c$) est rationnel, son étoile de @@ -698,18 +764,27 @@ encore un langage rationnel. \thingy Formellement, la définition des langages rationnelles est la suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$ de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de -$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$) est -dit \emph{stable par opérations rationnelles} lorsqu'il est stable par -les opérations de réunion, concaténation et étoile de Kleene, i.e., si -$L_1,L_2 \in \mathscr{C}$ alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1 -L_2 \in \mathscr{C}$, et si $L \in \mathscr{C}$ alors $L^* \in -\mathscr{C}$ ; le \emph{plus petit} (pour l'inclusion) ensemble de -langages stable par opérations rationnelles et contenant les langages -$\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in \Sigma$ -(i.e. $\varnothing\in\mathscr{C}$, $\{\varepsilon\} \in \mathscr{C}$ -et si $x\in\Sigma$ alors $\{x\}\in\mathscr{C}$), ou plus exactement, -l'intersection de tous les ensembles $\mathscr{C}$ vérifiant tous ces -propriétés, est la classe $\mathscr{R}$ des langages rationnels. +$\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$, +cf. \ref{set-of-languages}) est dit \emph{stable par opérations + rationnelles} lorsqu'il est stable par les opérations de réunion, +concaténation et étoile de Kleene, i.e., si $L_1,L_2 \in \mathscr{C}$ +alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1 L_2 \in \mathscr{C}$, et +si $L \in \mathscr{C}$ alors $L^* \in \mathscr{C}$ ; le \emph{plus + petit}\footnote{La classe des langages rationnelles (qu'on cherche à + définir) n'est pas le seul ensemble de langages stable par + opérations rationnelles : l'ensemble $\mathscr{P}(\Sigma^*)$ de tous + les langages est aussi évidemment stable par opérations + rationnelles ; on s'intéresse au plus petit $\mathscr{C}$ possible + pour n'avoir que ce qui est nécessairement construit à partir des + langages de base triviaux par les opérations rationnelles.} (pour +l'inclusion) ensemble de langages stable par opérations rationnelles +et contenant les langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ +pour $x \in \Sigma$ (i.e. $\varnothing\in\mathscr{C}$, +$\{\varepsilon\} \in \mathscr{C}$ et si $x\in\Sigma$ alors +$\{x\}\in\mathscr{C}$), ou plus exactement, l'intersection de tous les +ensembles $\mathscr{C}$ vérifiant tous ces propriétés, est la classe +$\mathscr{R}$ des langages rationnels (et un langage rationnel est +simplement un élément de $\mathscr{R}$). \emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages rationnels soit stable par concaténation signifie que si $L_1$ et @@ -719,16 +794,19 @@ rationnel ; \emph{cela ne signifie pas} qu'un langage rationnel donné soit stable par concaténation (un langage stable $L$ par concaténation est un langage tel que si $w_1,w_2\in L$ alors $w_1 w_2 \in L$). -\thingy Pour décrire la manière dont un langage rationnel est fabriqué -(à partir des langages de base par les opérations rationnelles), comme -il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on -introduit un nouvel objet, les \index{expression - rationnelle|see{rationnelle (expression)}}\defin[rationnelle - (expression)]{expressions rationnelles} (certains préfèrent le terme -d'\index{régulière (expression)|see{rationnelle}}\textbf{expressions - régulières}), qui sont des expressions servant à désigner un langage -rationnel. Par exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on -parlera du langage « désigné par l'expression rationnelle $dc{*}$ ». +\thingy\label{regular-expressions} Pour décrire la manière dont un +langage rationnel est fabriqué (à partir des langages de base par les +opérations rationnelles), comme il est malcommode d'écrire quelque +chose comme $\{d\}(\{c\}^*)$, on introduit un nouvel objet, les +\index{expression rationnelle|see{rationnelle + (expression)}}\defin[rationnelle (expression)]{expressions + rationnelles} (certains préfèrent le terme d'\index{régulière + (expression)|see{rationnelle}}\textbf{expressions régulières}), qui +sont des expressions servant à dénoter un langage rationnel. Par +exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du +langage « dénoté par l'expression rationnelle $dc{*}$ ». Ceci fournit +du même coup une nouvelle définition des langages rationnels : ce sont +les langages dénotés par une expression rationnelle. Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) est un mot sur l'alphabet $\Sigma \cup \{\bot, @@ -762,6 +840,9 @@ par l'expression $r$, de la manière suivante : et son langage dénoté est $L_{(r){*}} := L^*$. \end{itemize} +Un langage rationnel est par construction la même chose qu'un langage +pour lequel il existe une expression rationnelle qui le dénote. + \thingy À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc, @@ -792,9 +873,6 @@ $\Sigma = \{a,b,c,d\}$ : langage $\{\varepsilon, c\}$. \end{itemize} -Un langage rationnel est par construction la même chose qu'un langage -pour lequel il existe une expression rationnelle qui le dénote. - \thingy On dira qu'un mot $w$ \defin[vérifier (une expression rationnelle)]{vérifie} une expression rationnelle $r$ lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in L_r$). Par @@ -809,16 +887,23 @@ $\{a, aba, ababa, \ldots\}$ constitué des mots commençant et finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée par un unique $b$). +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 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 dénotent le même langage), ou encore $x{*}$ pour $(x){*}$ lorsque $x$ -est formé d'un seul caractère. La convention essentielle est que -l'opération d'étoile ${*}$ est la plus prioritaire ($ab{*}$ se lit -comme $a(b){*}$ et non pas comme $(ab){*}$), la concaténation vient -après, et la barre de disjonction $|$ est la moins prioritaire -($ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$). +est formé d'un seul caractère. + +Pour retirer des parenthèses, la convention sur la priorité des +opérations est la suivante : l'opération d'étoile ${*}$ est la plus +prioritaire (c'est-à-dire que $ab{*}$ se lit comme $a(b){*}$ et non +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$). {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$ sont introduits ici par souci de complétude mais font rarement @@ -845,7 +930,7 @@ 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} +\subsection{Remarques sur les moteurs d'expressions régulières en informatique}\label{subsection-remarks-on-regexp-syntax} \thingy Dans le monde informatique, il existe de nombreux \emph{moteurs d'expressions régulières}, c'est-à-dire outils (qu'il @@ -2951,7 +3036,7 @@ En revanche, si on change l'automate pour rendre l'état $4$ non-final aboutit sur la partition triviale en six états, c'est-à-dire que l'automate est, en fait, déjà minimal. -\begin{cor} +\begin{cor}\label{equivalence-of-regexps-is-decidable} On peut décider algorithmiquement si deux automates finis (de n'importe quelle sorte), ou deux expressions rationnelles, ou un automate et une expression rationnelle, sont équivalents (au sens de |