Languages (start).

1 files changed, 66 insertions, 5 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index d62cbbe..5fce7d4 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -185,11 +185,12 @@ programmation, mais pas par tous : \textit{caveat programmator}.)
 Ceci permet d'écrire par exemple $\Sigma \subseteq \Sigma^*$ ou bien
 $|x|=1 \liff x\in\Sigma$.
 
-\thingy Si le cardinal de l'alphabet $\Sigma$ vaut $\#\Sigma = N$,
-alors, pour chaque $n$, le nombre de mots de longueur exactement $n$
-est égal à $N^n$ (combinatoire classique).  Le nombre de mots de
-longueur $\leq n$ vaut donc $1 + N + \cdots + N^n =
-\frac{N^{n+1}-1}{N-1}$ (somme d'une série géométrique).
+\thingy\label{number-of-words-of-length-n} Si le cardinal de
+l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
+nombre de mots de longueur exactement $n$ est égal à $N^n$
+(combinatoire classique).  Le nombre de mots de longueur $\leq n$ vaut
+donc $1 + N + \cdots + N^n = \frac{N^{n+1}-1}{N-1}$ (somme d'une série
+géométrique).
 
 
 \subsection{Concaténation de mots, préfixes, suffixes, facteurs, sous-mots}
@@ -246,6 +247,24 @@ 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 :
+\begin{itemize}
+\item $w^0 = \varepsilon$ (le mot vide),
+\item $w^{r+1} = w^r w$.
+\end{itemize}
+(Ces définitions valent, d'ailleurs, dans n'importe quel monoïde.  On
+peut constater que $w^r w^s = w^{r+s}$ quels que soient
+$r,s\in\mathbb{N}$.)  On a bien sûr $|w^r| = r|w|$.
+
+Cette définition sert notamment à désigner de façon concise les mots
+comportant des répétitions d'une même lettre : par exemple, le mot
+$aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut
+s'écrire $a^3 b^2$.  (De même que pour le mot vide, il faut souligner
+que ces exposants ne font pas partie de l'alphabet.)
+
 \thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
 lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
 dira également :
@@ -318,6 +337,48 @@ a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
 \varepsilon$).
 
 
+\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).
+
+\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
+nombre quelconque (éventuellement nul) de $c$ est un langage sur
+l'alphabet $\Sigma = \{a,b,c,d\}$.  On verra plus loin que ce langage
+est « rationnel » (et pourra être désigné par l'expression rationnelle
+$dc*$).
+
+Voici quelques autres exemples de langages :
+\begin{itemize}
+\item Le langage (fini) $\{foo,bar,baz\}$ formé des seuls trois mots
+  $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$.
+\item Le langage (fini) formé des mots de longueur exactement $42$ sur
+  l'alphabet $\Sigma = \{p,q,r\}$.  Comme on l'a vu
+  en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal
+  exactement $3^{42}$.
+\item Le langage (fini) formé du seul mot vide (=mot de longueur
+  exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$.  Ce
+  langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut).
+  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\}$ 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.
+\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ formé de tous les
+  mots commençant par un $1$ et qui, interprétés comme un nombre écrit
+  en binaire, désignent un nombre premier ($L = \{10, 11, 101, 111,
+  1011, \ldots\}$).
+\item Le langage sur l'alphabet Unicode formé de tous les mots qui
+  constituent un document XML bien-formé d'après la spécification
+  XML 1.0.
+\end{itemize}
+
+
 %
 %
 %