diff options
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r-- | notes-inf105.tex | 126 |
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$). + + % % % |