From ba59c6dc4f1c31ac65b1f893b2218b2e9528d8a3 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 8 Nov 2016 13:00:03 +0100
Subject: Clarifications on Kleene's star, and the empty word.

---
 notes-inf105.tex | 45 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 37 insertions(+), 8 deletions(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 400e6a0..03f7f57 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -366,6 +366,9 @@ Voici quelques autres exemples de langages :
   Il ne faut pas le confondre avec le suivant :
 \item Le langage vide, qui ne contient aucun mot (sur un alphabet
   quelconque).  Ce langage a pour cardinal $0$.
+\item Le langage formé des mots de une seule lettre sur un alphabet
+  $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant
+  un mot de une lettre à la lettre en question).
 \item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
   commencent par trois $a$ consécutifs : ou, si on préfère, qui ont le
   mot $aaa$ comme préfixe.
@@ -467,20 +470,46 @@ des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est le
 langage des concaténations de $r$ mots appartenant à $L$ \emph{mais
   ces mots peuvent être différents}.  À titre d'exemple, si $L =
 \{a,b\}$ alors $L^r$ est le langage formé des $2^r$ mots de longueur
-exactement $r$ sur $\Sigma = \{a,b\}$, ce n'est pas l'ensemble à deux
-éléments $\{a^r, b^r\}$ formé des seuls deux mots $a^r = aaa\cdots a$
-et $b^r = bbb\cdots b$.
-
-On définit enfin l'\textbf{étoile de Kleene} $L^*$ sur le langage $L$
-comme le langage formé des concaténations d'un nombre
-\emph{quelconque} de mots appartenant à $L$, c'est-à-dire
+exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux éléments
+$\{a^r, b^r\}$ formé des seuls deux mots $a^r = aaa\cdots a$ et $b^r =
+bbb\cdots b$.
+
+\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit
+enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage formé
+des concaténations d'un nombre \emph{quelconque} de mots appartenant
+à $L$, c'est-à-dire
 \[
 \begin{aligned}
-L^* &= \bigcup_{r=0}^{+\infty} L^r\\
+L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
 &= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
 \end{aligned}
 \]
 
+Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$
+concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le
+langage formé de tous les mots sur l'alphabet $\{a,b\}$, pas le
+langage $\{a\}^* \cup \{b\}^*$ formé des mots obtenus en répétant la
+lettre $a$ ou en répétant la lettre $b$.
+
+On remarquera que la définition de $L^*$ ci-dessus redonne bien,
+lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme
+langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les
+mots : la notation $\Sigma^*$ est donc justifiée \textit{a
+  posteriori}.
+
+Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
+$L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
+(autrement dit, le mot vide est la concaténation de zéro mots de $L$).
+
+On introduit parfois la notation $L^+ = \bigcup_{r=1}^{+\infty} L^r =
+\{w_1\cdots w_r : r>0,\penalty-100\, w_1,\ldots,w_r\in L\}$ pour
+l'ensemble des mots formés par concaténation d'un nombre \emph{non
+  nul} de mots de $L$.  Lorsque le mot vide $\varepsilon$ n'appartient
+pas déjà à $L$, ce langage $L^+$ diffère de $L^*$ seulement en ce
+qu'il ne contient pas $\varepsilon$ ; tandis que si $\varepsilon$
+appartient déjà à $L$, alors $L^+$ est égal à $L^*$.
+
+
 %
 %
 %
-- 
cgit v1.2.3