From a5092b397fc70f2977be9d15b06800eff4674956 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 25 Nov 2016 11:08:20 +0100 Subject: Various additional remarks on regular expressions. --- notes-inf105.tex | 85 ++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 52 insertions(+), 33 deletions(-) diff --git a/notes-inf105.tex b/notes-inf105.tex index 0b9e751..05844ca 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -567,10 +567,10 @@ une définition plus précise), qu'on appelle \textbf{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 (i.e., la réunion de deux langages rationnels, ou la -concaténation de deux langages rationnels, ou l'étoile de Kleene d'un +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). +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\}$ (formé du seul mot $c$) est rationnel, son étoile de Kleene, @@ -579,23 +579,29 @@ rationnel, et comme $\{d\}$ l'est aussi, la concaténation $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage rationnel. -{\footnotesize\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. \par} +\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. + +\emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages +rationnels soit stable par concaténation signifie que si $L_1$ et +$L_2$ sont rationnels alors le langage $L_1 L_2$ (formé de tous les +mots concaténés d'un mot de $L_1$ et d'un mot de $L_2$) est +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 @@ -654,7 +660,16 @@ $\Sigma = \{a,b,c,d\}$ : \item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\} \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; \item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d, - bcd, bcbcd, bcbcbcd, \ldots\}$. + bcd, bcbcd, bcbcbcd, \ldots\}$ ; +\item l'expression rationnelle $\bot d$ dénote le langage + vide $\varnothing$ (car il n'y a pas de mot dans le langage vide, + donc pas non plus de mot dans sa concaténation avec le + langage $\{d\}$) ; +\item l'expression rationnelle $\underline{\varepsilon} d$ dénote le + langage $\{d\}$ ; +\item l'expression rationnelle $(\bot|c)$ dénote le langage $\{c\}$ ; +\item l'expression rationnelle $(\underline{\varepsilon}|c)$ dénote le + langage $\{\varepsilon, c\}$. \end{itemize} Un langage rationnel est par construction la même chose qu'un langage @@ -664,16 +679,16 @@ On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$ lorsque ce mot appartient au langage qu'elle dénote (i.e., $w \in L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$. -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$). +\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$). {\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$ sont introduits ici par souci de complétude mais font rarement @@ -686,8 +701,12 @@ La barre de disjonction que nous avons notée ${|}$ est souvent plutôt notée $+$ par les mathématiciens. 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} -(de sorte que $r+$ a le même sens que $rr{*}$). +\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{+}$ 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)$. \thingy Deux expressions rationnelles $r_1,r_2$ sont dites \textbf{équivalentes} lorsqu'elles dénotent le même langage. À titre -- cgit v1.2.3