summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-25 10:57:01 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-25 15:47:00 +0100
commitac1c637c177684b9e408e800d10872897eadd59d (patch)
treeb2e78a7d790b37811fc50fc19bf74218dd4bbdda /notes-inf105.tex
parentd4f6cce65eaa6e13bfbbb8de4d4e7df8e46a9d44 (diff)
downloadinf105-ac1c637c177684b9e408e800d10872897eadd59d.tar.gz
inf105-ac1c637c177684b9e408e800d10872897eadd59d.tar.bz2
inf105-ac1c637c177684b9e408e800d10872897eadd59d.zip
Use "denote" for the relation between a regular expression and a language.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex64
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