From d7a83cc55359ae3d3c5cb39c3ff0c7bea1b87885 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 8 Nov 2017 15:17:45 +0100 Subject: Add remark about Kleene's star as smallest solution to an equation. --- notes-inf105.tex | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'notes-inf105.tex') diff --git a/notes-inf105.tex b/notes-inf105.tex index dccd60d..e759d97 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -721,10 +721,20 @@ langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les mots : la notation $\Sigma^*$ est donc justifiée \textit{a posteriori}. +\smallskip + 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$). +\smallskip + +{\footnotesize On peut par ailleurs montrer que $L^*$ est le plus + petit (pour l'inclusion) langage $M$ tel que $M = \{\varepsilon\} + \cup LM$. Cette observation sera implicite par exemple + dans \ref{cfg-union-concatenation-and-star} ci-dessous, et motive + aussi la construction $L^+$ qui suit.\par} + \thingy\label{kleene-plus} 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 -- cgit v1.2.3