More about languages.

1 files changed, 106 insertions, 4 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5fce7d4..400e6a0 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -247,10 +247,10 @@ signifie exactement ce qui vient d'être dit).
   appliquant cette propriété à la fonction $\psi(x) = 1$ pour
   tout $x\in\Sigma$.\par}
 
-\thingy Lorsque $w \in \Sigma^*$ et $r \in \mathbb{N}$, on définit un
-mot $w^r$ comme la concaténation de $r$ facteurs tous égaux au
-mot $w$, autrement dit, comme la répétition $r$ fois du mot $w$.
-Formellement, on définit par récurrence :
+\thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in
+\mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$
+facteurs tous égaux au mot $w$, autrement dit, comme la répétition $r$
+fois du mot $w$.  Formellement, on définit par récurrence :
 \begin{itemize}
 \item $w^0 = \varepsilon$ (le mot vide),
 \item $w^{r+1} = w^r w$.
@@ -366,6 +366,15 @@ 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 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.
+\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
+  contiennent trois $a$ consécutifs ; ou, si on préfère, qui ont $aaa$
+  comme facteur.
+\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
+  contiennent au moins trois $a$, non nécessairement consécutifs ; ou,
+  si on préfère, qui ont $aaa$ comme sous-mot.
 \item Le langage sur l'alphabet $\Sigma=\{a\}$ formé de tous les mots
   dont la longueur est un nombre premier ($L = \{aa, aaa, a^5, a^7,
   a^{11},\ldots\}$).  Ce langage est infini.
@@ -378,6 +387,99 @@ Voici quelques autres exemples de langages :
   XML 1.0.
 \end{itemize}
 
+\thingy On pourrait aussi considérer un langage (sur
+l'alphabet $\Sigma$) comme une \emph{propriété} des mots (sur
+l'alphabet en question).  Précisément, si $P$ est une propriété qu'un
+mot $w \in \Sigma^*$ peut ou ne pas avoir, on considère le langage
+$L_P = \{w \in \Sigma^* : w \text{~a la propriété~} P\}$, et
+inversement, si $L \subseteq \Sigma^*$ est un langage, on considère la
+propriété « appartenir à $L$ » : en identifiant la propriété et le
+langage qu'on vient d'associer l'un à l'autre (par exemple, le langage
+des mots commençant par $a$ et la propriété « commencer par $a$ »), un
+langage pourrait être considéré comme une propriété des mots.
+
+{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie
+  d'un ensemble $E$ quelconque peut être identifiée à une propriété
+  que les éléments de $E$ peuvent ou ne pas avoir, à savoir,
+  appartenir à la partie en question.)\par}
+
+On évitera de faire cette identification pour ne pas introduire de
+confusion, mais il est utile de la garder à l'esprit : par exemple,
+dans un langage de programmation fonctionnel, un « langage » au sens
+de ces notes peut être considéré comme une fonction (pure,
+c'est-à-dire, déterministe et sans effet de bord) prenant en entrée
+une chaîne de caractères et renvoyant un booléen.
+
+\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
+alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
+peut former les langages \textbf{union} $L_1\cup L_2$ et
+\textbf{intersection} $L_1\cap L_2$ qui sont simplement les opérations
+ensemblistes usuelles (entre parties de $\Sigma^*$).
+
+Les opérations correspondantes sur les propriétés de mots sont
+respectivement le « ou logique » (=disjonction) et le « et logique »
+(=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$
+est le langage des mots commençant par $a$ et $L_2$ le langage des
+mots finissant par $b$, alors $L_1 \cup L_2$ est le langage des mots
+commençant par $a$ \emph{ou bien} finissant par $b$, tandis que $L_1
+\cap L_2$ est le langage des mots commençant par $a$ \emph{et}
+finissant par $b$.
+
+\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
+$L \subseteq \Sigma^*$, on peut former le langage $\Sigma^*\setminus
+L$, parfois noté simplement $\overline L$ si ce n'est pas ambigu, dit
+\textbf{complémentaire} de $L$, et qui est simplement l'ensemble des
+mots sur $\Sigma$ \emph{n'appartenant pas} à $L$.  L'opération
+correspondante sur les propriétés de mots est la négation logique.
+
+À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des
+mots commençant par $a$, alors $\overline{L}$ est le langage des mots
+ne commençant pas par $a$, c'est-à-dire, la réunion de
+$\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur
+$\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien
+commence par $b$).
+
+\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
+alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
+peut former le langage \textbf{concaténation} $L_1 L_2$ : il est
+défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme
+concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit
+\[
+\begin{aligned}
+L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
+ &= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\
+\end{aligned}
+\]
+
+\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
+$L \subseteq \Sigma^*$, et si $r \in \mathbb{N}$, on peut définir un
+langage $L^r$, par analogie avec \ref{powers-of-a-word}, comme le
+langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ formé des
+concaténation de $r$ mots appartenant à $L$, ou si on préfère, par
+récurrence :
+\begin{itemize}
+\item $L^0 = \{\varepsilon\}$,
+\item $L^{r+1} = L^r L$.
+\end{itemize}
+
+\emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ formé
+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
+\[
+\begin{aligned}
+L^* &= \bigcup_{r=0}^{+\infty} L^r\\
+&= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
+\end{aligned}
+\]
 
 %
 %