Concatenation, prefixes, suffixes, factors and subwords.

1 files changed, 126 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 6d083d9..d62cbbe 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -192,6 +192,132 @@ 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}
+
+\thingy Si $u := x_1\cdots x_m$ et $v := y_1\cdots y_n$ sont deux
+mots, de longueurs respectives $m$ et $n$, sur un même
+alphabet $\Sigma$, alors on définit un mot $uv := x_1\cdots x_m
+y_1\cdots y_n$ de longueur $m+n$, dont les lettres sont obtenues en
+mettant bout à bout celles de $u$ puis celles de $v$ (dans cet ordre),
+et on l'appelle \textbf{concaténation} (ou, si cela ne prête pas à
+confusion, simplement \textbf{produit}) des mots $u$ et $v$.  (Dans un
+contexte informatique, on parle de concaténation de chaînes de
+caractères.)
+
+\thingy Parmi les propriétés de la concaténation, signalons les faits
+suivants :
+\begin{itemize}
+\item le mot vide $\varepsilon$ est « \textbf{neutre} » pour la
+  concaténation, ce qui signifie par définition : $\varepsilon w = w
+  \varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
+\item la concaténation est « \textbf{associative} », ce qui signifie
+  par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
+  \in \Sigma^*$.
+\end{itemize}
+
+On peut traduire de façon savante ces deux propriétés en une phrase :
+l'ensemble $\Sigma^*$ est un \textbf{monoïde}, d'élément
+neutre $\varepsilon$, pour la concaténation (cela signifie exactement
+ce qui vient d'être dit).
+
+\thingy On a par ailleurs $|uv| = |u| + |v|$ (la longueur de la
+concaténation de deux mots est la somme des concaténations), et on
+rappelle par ailleurs que $|\varepsilon| = 0$ ; on peut traduire cela
+de manière savante : la longueur est un \textbf{morphisme de monoïdes}
+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^*$
+  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
+  pour cette opération), et si $\psi\colon \Sigma\to M$ est une
+  application quelconque, alors il existe un unique morphisme de
+  monoïdes $\hat\psi\colon \Sigma^* \to M$ (c'est-à-dire une
+  application préservant le neutre et l'opération binaire) tel que
+  $\hat\psi(x) = \psi(x)$ si $x\in\Sigma$.  (Démonstration : on a
+  nécessairement $\hat\psi(x_1\cdots x_n) = \psi(x_1)\cdots
+  \psi(x_n)$, or ceci définit bien un morphisme comme annoncé.)  On
+  dit qu'il s'agit là d'une propriété « universelle », et plus
+  précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
+  l'ensemble $\Sigma$.  Par exemple, le morphisme « longueur »
+  $\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
+  appliquant cette propriété à la fonction $\psi(x) = 1$ pour
+  tout $x\in\Sigma$.\par}
+
+\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 :
+\begin{itemize}
+\item que $u$ est un \textbf{préfixe} de $w$, ou
+\item que $v$ est un \textbf{suffixe} de $w$.
+\end{itemize}
+
+De façon équivalente, si $w = x_1\cdots x_n$ (où $x_1,\ldots,x_n \in
+\Sigma$) est un mot de longueur $n$, et si $0\leq k\leq n$ est un
+entier quelconque compris entre $0$ et $n$, on dira que $u :=
+x_1\cdots x_k$ (c'est-à-dire, le mot formé des $k$ premières lettres
+de $w$, dans le même ordre) est le \textbf{préfixe de longueur $k$}
+de $w$, et que $v := x_{k+1}\cdots x_n$ (mot formé des $n-k$ dernières
+lettres de $w$, dans le même ordre) est le \textbf{suffixe de
+  longueur $n-k$} de $w$.  Il est clair qu'il s'agit bien là de
+l'unique façon d'écrire $w = uv$ avec $|u|=k$ et $|v|=n-k$, ce qui
+fait le lien avec la définition donnée au paragraphe précédent ;
+parfois on dira que $v$ est le suffixe \textbf{correspondant} à $u$ ou
+que $u$ est le préfixe correspondant à $v$ (dans le mot $w$).
+
+Le mot vide est préfixe et suffixe de n'importe quel mot.  Le mot $w$
+lui-même est aussi un préfixe et un suffixe de lui-même.  Entre les
+deux, pour n'importe quelle longueur $k$ donnée, il existe un unique
+préfixe et un unique suffixe de longueur $k$.  (Il peut tout à fait se
+produire que le préfixe et le suffixe de longueur $k$ soient égaux
+pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui
+suit.)
+
+À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$
+a les sept préfixes suivants, rangés par ordre croissant de longueur :
+$\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et
+$abbcab$ lui-même ; il a les sept suffixes suivants, rangés par ordre
+croissant de longueur : $\varepsilon$ (le mot vide), $b$, $ab$, $cab$,
+$bcab$, $bbcab$ et $abbcab$ lui-même.  Le suffixe correspondant au
+préfixe $abb$ est $bcab$ puisque $abbcab = (abb)(bcab)$.
+
+\thingy Comme généralisation à la fois de la notion de préfixe et de
+celle de suffixe, on a la notion de facteur : si $u_0,v,u_1 \in
+\Sigma^*$ sont trois mots quelconques sur un même alphabet $\Sigma$,
+et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un
+\textbf{facteur} de $w$.  Alors qu'un préfixe ou suffixe du mot $w$
+est déterminé simplement par sa longueur, un facteur est déterminé par
+sa longueur et l'emplacement à partir duquel il commence.
+
+À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$
+(le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$,
+$bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$
+lui-même.
+
+Dans un contexte informatique, ce que nous appelons ici « facteur »
+est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
+cependant pas confondre ce concept avec celui de sous-mot défini
+ci-dessous.
+
+\thingy Si $u_0,\ldots,u_r$ et $v_1,\ldots,v_r$ sont des mots sur un
+même alphabet $\Sigma$, on dira que $v := v_1\cdots v_r$ est un
+\textbf{sous-mot} du mot $w := u_0 v_1 u_1 v_2 \cdots u_{r-1} v_r
+u_r$.  En plus clair, cela signifie que $v$ est obtenu en ne gardant
+que certaines lettres du mot $w$ (celles des $v_i$), dans le même
+ordre, mais en en effaçant d'autres (celles des $u_i$) ; à la
+différence du concept de facteur, celui de sous-mot n'exige pas que
+les lettres gardées soient consécutives.
+
+À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
+(obtenu en gardant les lettres soulignées ici :
+$\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
+définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
+a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
+\varepsilon$).
+
+
 %
 %
 %