From 2d0fa90132f68fbc18834cc062fb2137f70add5b Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 14 Nov 2016 12:17:47 +0100
Subject: More clarifications on rational languages and expressions.
---
notes-inf105.tex | 36 ++++++++++++++++++++++++++++--------
1 file changed, 28 insertions(+), 8 deletions(-)
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5ed7719..d1e43da 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -538,7 +538,7 @@ de base triviaux suivants :
\item le langage vide $\varnothing$,
\item le langage formé du seul mot vide, $\{\varepsilon\}$, et
\item les langages formés d'un seul mot lui-même formé d'une seule
- lettre, $\{a\}$ pour chaque $a\in\Sigma$,
+ lettre, $\{x\}$ pour chaque $x\in\Sigma$,
\end{itemize}
et on va les combiner par les opérations dites « rationnelles »
suivantes :
@@ -552,11 +552,11 @@ On obtient ainsi une certaine famille de langages (cf. ci-dessous pour
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 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 langage rationnel, sont
-rationnels, et les langages rationnels sont exactement ceux qu'on
-obtient ainsi).
+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
+langage rationnel, sont rationnels, et les langages rationnels sont
+exactement ceux qu'on obtient ainsi).
À 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,
@@ -565,12 +565,32 @@ 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 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 \textbf{expressions rationnelles}
(certains préfèrent le terme d'\textbf{expressions régulières}), qui
-sont des expressions servant à désigner un langage rationnel.
+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*$.
Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
est un mot sur l'alphabet $\Sigma \cup \{\bot,
@@ -623,7 +643,7 @@ $\Sigma = \{a,b,c,d\}$ :
bcd, bcbcd, bcbcbcd, \ldots\}$.
\end{itemize}
-Un langage rationnel est par définition la même chose qu'un langage
+Un langage rationnel est par construction la même chose qu'un langage
pour lequel il existe une expression rationnelle qui le désigne.
On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
--
cgit v1.2.3