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(-)

(limited to 'notes-inf105.tex')

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