summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-08 15:17:45 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-08 15:17:45 +0100
commitd7a83cc55359ae3d3c5cb39c3ff0c7bea1b87885 (patch)
tree6c4ed11bf83e4d13448c81e833035410460e2016
parentf3be62b7d38da0fd991723ead8fb5fe31c2dcb85 (diff)
downloadinf105-d7a83cc55359ae3d3c5cb39c3ff0c7bea1b87885.tar.gz
inf105-d7a83cc55359ae3d3c5cb39c3ff0c7bea1b87885.tar.bz2
inf105-d7a83cc55359ae3d3c5cb39c3ff0c7bea1b87885.zip
Add remark about Kleene's star as smallest solution to an equation.
-rw-r--r--notes-inf105.tex10
1 files changed, 10 insertions, 0 deletions
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