Various clarifications and updates to the sections on words and languages.

1 files changed, 97 insertions, 33 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index ea0ece6..8847dd2 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -143,29 +143,41 @@ parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie
 (=liste) de caractères.  Le mot est désigné en écrivant les lettres
 les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in
 \Sigma$ sont des lettres, le mot formé par la suite finie
-$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.  À titre
-d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = \{a,b,c,d\}$,
-et \texttt{foobar} est un mot (=chaîne de caractères) sur l'alphabet
-ASCII.  (Dans un contexte informatique, il est fréquent d'utiliser une
-sorte de guillemet pour délimiter les chaînes de caractères : on
-écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
-question.  Dans ces notes, nous utiliserons peu cette convention.)
-
-L'ensemble des mots sur un alphabet $\Sigma$ sera désigné $\Sigma^*$
-(on verra en \ref{kleene-star} ci-dessous cette notation comme un cas
-particulier d'une construction « étoile » plus générale).  Par
-exemple, si $\Sigma = \{0,1\}$, alors $\Sigma^*$ est l'ensemble
-(infini !) dont les éléments sont toutes les suites finies binaires
-(=suites finies de $0$ et de $1$).
-
-\thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
-appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
-bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
-la longueur $|x_1\cdots x_n|$ du mot $x_1\cdots x_n$, vaut $n$.
-Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
-caractères en informatique.  À titre d'exemple, sur l'alphabet
-$\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
-$|abbcab|=6$ ou bien $\ell(abbcab)=6$).
+$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.
+
+À titre d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma =
+\{a,b,c,d\}$, et \texttt{foobar} est un mot (=chaîne de caractères)
+sur l'alphabet ASCII.  (Dans un contexte informatique, il est fréquent
+d'utiliser une sorte de guillemet pour délimiter les chaînes de
+caractères : on écrira donc \texttt{\char`\"foobar\char`\"} pour
+parler du mot en question.  Dans ces notes, nous utiliserons peu cette
+convention.)
+
+L'ensemble de tous les mots sur un alphabet $\Sigma$ sera
+désigné $\Sigma^*$ (on verra en \ref{kleene-star} ci-dessous cette
+notation comme un cas particulier d'une construction « étoile » plus
+générale).  Par exemple, si $\Sigma = \{0,1\}$, alors $\Sigma^*$ est
+l'ensemble (infini !) dont les éléments sont toutes les suites finies
+binaires (=suites finies de $0$ et de $1$).  Ainsi, écrire « $w \in
+\Sigma^*$ » signifie « $w$ est un mot sur l'alphabet $\Sigma$ ».
+
+{\footnotesize\thingy Typographiquement, on essaiera autant que
+  possible de désigner des mots par des variables mathématiques telles
+  que $u,v,w$, tandis que $x,y,z$ désigneront plutôt des lettres
+  quelconques dans un alphabet (quant à $a,b,c$, ils serviront de
+  lettres dans les exemples).  Ce n'est malheureusement pas possible
+  d'être systématique (il arrivera que $x$ désigne un mot) : on
+  cherchera donc à toujours rappeler le type de toute variable en
+  écrivant, par exemple, $t \in\Sigma$ ou $t \in\Sigma^*$.\par}
+
+\thingy\label{length-of-word} Le nombre $n$ de lettres dans un mot $w
+\in \Sigma^*$ est appelé la \textbf{longueur} du mot, et généralement
+notée $|w|$ ou bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in
+\Sigma$, alors la longueur $|x_1\cdots x_n|$ du mot $x_1\cdots x_n$,
+vaut $n$.  Ceci coïncide bien avec la notion usuelle de longueur d'une
+chaîne de caractères en informatique.  À titre d'exemple, sur
+l'alphabet $\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$
+(on écrira $|abbcab|=6$ ou bien $\ell(abbcab)=6$).
 
 \thingy Quel que soit l'alphabet, il existe un unique mot de
 longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé
@@ -250,7 +262,8 @@ entre le monoïde $\Sigma^*$ des mots (pour la concaténation) et le
 monoïde $\mathbb{N}$ des entiers naturels (pour l'addition) (cela
 signifie exactement ce qui vient d'être dit).
 
-{\footnotesize\thingy \textbf{Complément :} Le monoïde $\Sigma^*$
+{\footnotesize\thingy\label{universal-property-remark}
+  \textbf{Complément :} Le monoïde $\Sigma^*$
   possède la propriété suivante par rapport à l'ensemble $\Sigma$ : si
   $M$ est un monoïde quelconque (c'est-à-dire un ensemble muni d'une
   opération binaire associative $\cdot$ et d'un élément $e$ neutre
@@ -386,14 +399,32 @@ w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques.
 
 Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.
 
+{\footnotesize\thingy\label{number-of-occurrences-of-letter} La
+  notation suivante est souvent utile : si $w$ est un mot sur un
+  alphabet $\Sigma$ et si $z$ est une lettre (= élément de $\Sigma$),
+  on note $|w|_z$ le nombre total d'occurrences de la lettre $z$
+  dans $w$.  À titre d'exemple, sur l'alphabet $\Sigma=\{a,b,c,d\}$,
+  le nombre d'occurrences des différentes lettres dans le mot $abbcab$
+  sont : $|abbcab|_a=2$, $|abbcab|_b=3$, $|abbcab|_c=1$ et
+  $|abbcab|_d=0$.
+
+Formellement, on peut définir $|w|_z$ de la façon suivante : si $w =
+x_1 \cdots x_n$ où $x_1,\ldots,x_n \in \Sigma$, alors $|w|_z$ est le
+cardinal de l'ensemble $\{i : x_i = z\}$.  On peut remarquer qu'on a :
+$|w| = \sum_{z\in\Sigma} |w|_z$ (i.e., la longueur de $w$ est la somme
+des nombres d'occurrences dedans des différentes lettres de
+l'alphabet).\par}
+
 
 \subsection{Langages et opérations sur les langages}
 
 \thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement
 un ensemble de mots sur $\Sigma$.  Autrement dit, il s'agit d'un
-sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ de tous les mots
-sur $\Sigma$ : en symboles, $L \subseteq \Sigma^*$.  On souligne
-qu'on ne demande pas que $L$ soit fini (mais il peut l'être).
+sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ (de tous les mots
+sur $\Sigma$) : en symboles, $L \subseteq \Sigma^*$.
+
+On souligne qu'on ne demande pas que $L$ soit fini (mais il peut
+l'être, auquel cas on parlera fort logiquement de « langage fini »).
 
 \thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
 = \{dc^r \colon r\in\mathbb{N}\}$ des mots formés d'un $d$ suivi d'un
@@ -536,7 +567,8 @@ a$ et $b^r = bbb\cdots b$.
 \thingy\label{kleene-star} Si $L$ est un langage sur
 l'alphabet $\Sigma$, on définit enfin l'\textbf{étoile de Kleene}
 $L^*$ de $L$ comme le langage constitué des concaténations d'un nombre
-\emph{quelconque} de mots appartenant à $L$, c'est-à-dire
+\emph{quelconque} de mots appartenant à $L$, c'est-à-dire la réunion
+de tous les langages $L^r$ mentionnés ci-dessus :
 \[
 \begin{aligned}
 L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
@@ -544,6 +576,11 @@ L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
 \end{aligned}
 \]
 
+À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L =
+\{a,bb\}$, alors on a $L^* = \{\varepsilon, a, bb, \penalty-200 aa,
+abb, bba, bbbb, \penalty-200 aaa, aabb, abba, abbbb, \penalty-100
+bbaa, bbabb, bbbba, bbbbbb, \ldots\}$.
+
 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 constitué de tous les mots sur l'alphabet $\{a,b\}$, pas le
@@ -575,6 +612,33 @@ langage sur l'alphabet $\Sigma$, on définit le langage miroir
 $L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$,
 c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
 
+\medbreak
+
+\thingy De même que l'ensemble des mots sur un alphabet $\Sigma$ admet
+une notation, à savoir $\Sigma^*$, on peut introduire une notation
+pour l'ensemble de tous les \emph{langages} (= ensembles de mots)
+sur $\Sigma$ : ce sera $\mathscr{P}(\Sigma^*)$.  Il s'agit d'un cas
+particulier de la construction « ensemble des parties » (si $E$ est un
+ensemble, $\mathscr{P}(E) = \{A : A\subseteq E\}$ est l'ensemble de
+tous les sous-ensembles de $A$ ; c'est un axiome de la théorie des
+ensembles qu'un tel ensemble existe bien).  On pourrait donc écrire
+« $L \in \mathscr{P}(\Sigma^*)$ » comme synonyme de « $L\subseteq
+\Sigma^*$ » ou de « $L$ est un langage sur $\Sigma$ » ; on évitera
+cependant de le faire, car cette notation est plus lourde qu'utile.
+
+{\footnotesize Il sera marginalement question dans ces notes de
+  « classes de langages » : une classe de langages est un ensemble de
+  langages (c'est-à-dire une partie de $\mathscr{P}(\Sigma^*)$, ou si
+  on préfère un élément de $\mathscr{P}(\mathscr{P}(\Sigma^*))$).  On
+  ne développera pas de théorie générale des classes de langages et on
+  n'en parlera pas de façon systématique, mais on parlera de certaines
+  classes de langages importantes : la classe des langages rationnels
+  ou reconnaissables (§\ref{subsection-rational-languages} à
+  §\ref{section-recognizable-languages}), la classe des langages
+  algébriques (§\ref{section-context-free-grammars}), la classe des
+  langages décidables (§\ref{section-computability}) et la classe des
+  langages semi-décidable (\textit{ibid.}).\par}
+
 
 \subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
 
@@ -866,7 +930,7 @@ régulière à utiliser est \texttt{\char"5C*} et que cette chaîne de
 caractères s'écrit \texttt{"\char"5C\char"5C*"} en Java.
 
 
-\section{Automates finis}
+\section{Automates finis}\label{section-finite-automata}
 
 \setcounter{comcnt}{0}
 
@@ -1786,7 +1850,7 @@ choix.
 \par}
 
 
-\section{Langages reconnaissables et langages rationnels}
+\section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages}
 
 \subsection{Stabilité des langages reconnaissables}
 
@@ -2878,7 +2942,7 @@ et les langages reconnus sont les mêmes.
 \end{proof}
 
 
-\section{Grammaires hors contexte}
+\section{Grammaires hors contexte}\label{section-context-free-grammars}
 
 \setcounter{comcnt}{0}
 
@@ -3357,7 +3421,7 @@ S\; \rightarrow\; aSbS \;|\; bSaS \;|\; \varepsilon
 \varepsilon$) engendre le langage $L$ formé des mots ayant un nombre
 total de $a$ égal au nombre total de $b$, i.e., $L = \{w \in\Sigma^* :
 |w|_a = |w|_b\}$ où $|w|_x$ désigne le nombre total d'occurrences de
-la lettre $x$ dans le mot $w$.
+la lettre $x$ dans le mot $w$ (cf. \ref{number-of-occurrences-of-letter}).
 
 Dans un sens il est évident que tout pseudo-mot obtenu en dérivant $S$
 a un nombre de $a$ égal au nombre de $b$, puisque cette propriété est
@@ -4037,7 +4101,7 @@ construits (et éventuellement les arbres eux-mêmes).
 %
 %
 
-\section{Introduction à la calculabilité}
+\section{Introduction à la calculabilité}\label{section-computability}
 
 \setcounter{comcnt}{0}