summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex71
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}
+
+
%
%
%