Use "denote" for the relation between a regular expression and a language.

1 files changed, 36 insertions, 28 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 67b31ec..0b9e751 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -613,61 +613,61 @@ est un mot sur l'alphabet $\Sigma \cup \{\bot,
 caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés
 \textbf{métacaractères}, et qui servent à marquer la manière dont est
 formée l'expression rationnelle.  On définit simultanément la notion
-d'expression rationnelle $r$ et de \textbf{langage désigné} $L_r$ par
-l'expression $r$, de la manière suivante :
+d'expression rationnelle $r$ et de \textbf{langage dénoté} (ou
+\textbf{désigné}) $L_r$ par l'expression $r$, de la manière suivante :
 \begin{itemize}
-\item $\bot$ est une expression rationnelle et son langage désigné
+\item $\bot$ est une expression rationnelle et son langage dénoté
   est $L_\bot := \varnothing$,
 \item $\underline{\varepsilon}$ est une expression rationnelle et son
-  langage désigné est $L_{\underline{\varepsilon}} :=
+  langage dénoté est $L_{\underline{\varepsilon}} :=
   \{\varepsilon\}$,
 \item si $x\in\Sigma$ est une lettre de l'alphabet $\Sigma$, alors le
-  mot $x$ est une expression rationnelle et son langage désigné
+  mot $x$ est une expression rationnelle et son langage dénoté
   est $L_x := \{x\}$,
 \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ésignés correspondants,
+  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ésigné est $L_{r_1 r_2} := L_1 L_2$,
+  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ésignés correspondants,
+  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ésigné est $L_{(r_1|r_2)} := L_1\cup L_2$,
+  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ésigné correspondant, alors $(r){*}$ est une expression rationnelle
-  et son langage désigné est $L_{(r){*}} := L^*$.
+  dénoté correspondant, alors $(r){*}$ est une expression rationnelle
+  et son langage dénoté est $L_{(r){*}} := L^*$.
 \end{itemize}
 
 À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
-expression rationnelle qui désigne le langage $\{c\}$, donc $(c){*}$ en
-est une qui désigne le langage $\{c\}^* = \{\varepsilon, c, cc,
-ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui désigne le langage $\{d,
+expression rationnelle qui dénote le langage $\{c\}$, donc $(c){*}$ en
+est une qui dénote le langage $\{c\}^* = \{\varepsilon, c, cc,
+ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui dénote le langage $\{d,
 dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession
 quelconques de $c$.  Voici quelques autres exemples, toujours sur
 $\Sigma = \{a,b,c,d\}$ :
 \begin{itemize}
-\item l'expression rationnelle $(a|b)$ désigne le langage $\{a\} \cup
+\item l'expression rationnelle $(a|b)$ dénote le langage $\{a\} \cup
   \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ;
-\item l'expression rationnelle $(a|b)c$ désigne le langage
+\item l'expression rationnelle $(a|b)c$ dénote le langage
   $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ;
-\item l'expression rationnelle $(bc){*}$ désigne le langage $\{bc\}^* =
+\item l'expression rationnelle $(bc){*}$ dénote le langage $\{bc\}^* =
   \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
-\item l'expression rationnelle $(a|(bc){*})$ désigne le langage $\{a\}
+\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ésigne le langage $\{a, d,
+\item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d,
   bcd, bcbcd, bcbcbcd, \ldots\}$.
 \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ésigne.
+pour lequel il existe une expression rationnelle qui le dénote.
 
 On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
-lorsque ce mot appartient au langage qu'elle désigne (i.e., $w \in
+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ésignent
+$(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
@@ -686,9 +686,17 @@ 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ésigner l'opération évoquée en \ref{kleene-plus}
+\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{*}$).
 
+\thingy Deux expressions rationnelles $r_1,r_2$ sont dites
+\textbf{équivalentes} lorsqu'elles dénotent le même langage.  À titre
+d'exemple, sur l'alphabet $\{a,b\}$, les deux expressions rationnelles
+$(ab)*a$ et $a(ba)*$ sont équivalentes (toutes les deux dénotent le
+langage $\{a, aba, ababa, \ldots\}$ formé des mots commençant et
+finissant par un $a$ et dans lesquels chaque paire de $a$ est séparée
+par un unique $b$).
+
 
 \section{Automates finis}
 
@@ -851,7 +859,7 @@ Cette description rend claire le fait que l'automate en question
 accepte exactement les mots contenant un $a$ suivi, pas forcément
 immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
 sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
-reconnaissable.  (Il est aussi rationnel puisque désigné par
+reconnaissable.  (Il est aussi rationnel puisque dénoté par
 l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.)
 
 \thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA
@@ -991,7 +999,7 @@ quelconque de $c$.
 %%% end example2b %%%
 \end{center}
 
-(Ce langage est aussi désigné par l'expression rationnelle
+(Ce langage est aussi dénoté par l'expression rationnelle
 $c{*}ac{*}bc{*}$.)
 
 \begin{prop}\label{completion-of-dfai}
@@ -1191,7 +1199,7 @@ Cet automate n'est pas déterministe car il existe deux transitions
 étiquetées $a$ partant de l'état $0$.  En considérant les différents
 chemins possibles entre $0$ et $2$ dans ce graphe, on comprend que le
 langage qu'il reconnaît est le langage des mots sur $\{a,b\}$ dont
-l'avant-dernière lettre est un $a$ (c'est aussi le langage désigné par
+l'avant-dernière lettre est un $a$ (c'est aussi le langage dénoté par
 l'expression rationnelle $(a|b){*}a(a|b)$).  Une façon de présenter le
 non-déterminisme est que l'automate « devine », quand il est dans
 l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera
@@ -1447,7 +1455,7 @@ En considérant les différents chemins possibles entre $0$ et $2$ sur
 ce graphe, on comprend que le langage qu'il reconnaît est celui des
 mots sur $\{a,b,c\}$ formés d'un nombre quelconque de $a$ suivi d'un
 nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si
-on préfère, le langage désigné par l'expression rationnelle
+on préfère, le langage dénoté par l'expression rationnelle
 $a{*}b{*}c{*}$.
 
 \thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture}
@@ -1774,7 +1782,7 @@ de $A$ en question vers $q_0$.  On a donc bien $L_{A'} = L^*$.
 \begin{prop}\label{rational-languages-are-recognizable}
 Tout langage rationnel est reconnaissable ; de plus, un εNFA le
 reconnaissant se déduit algorithmiquement d'une expression rationnelle
-le désignant.
+le dénotant.
 \end{prop}
 \begin{proof}
 Cela résulte de façon évidente de la définition des langages