diff options
| -rw-r--r-- | notes-inf105.tex | 45 |
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^*$. + + % % % |