summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-08 13:00:03 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-08 13:00:03 +0100
commitba59c6dc4f1c31ac65b1f893b2218b2e9528d8a3 (patch)
treeb15f81ba1f3e8014eeac99e923b79f27b888f16f
parent85eb25e585c01eba5af5360e93c3c8f13218efe9 (diff)
downloadinf105-ba59c6dc4f1c31ac65b1f893b2218b2e9528d8a3.tar.gz
inf105-ba59c6dc4f1c31ac65b1f893b2218b2e9528d8a3.tar.bz2
inf105-ba59c6dc4f1c31ac65b1f893b2218b2e9528d8a3.zip
Clarifications on Kleene's star, and the empty word.
-rw-r--r--notes-inf105.tex45
1 files changed, 37 insertions, 8 deletions
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^*$.
+
+
%
%
%