[Link] [Link]

be

Mémoire

Auteur : Talmas, Emeline

Promoteur(s) : Leroy, Julien
Faculté : Faculté des Sciences
Diplôme : Master en sciences mathématiques, à finalité didactique
Année académique : 2020-2021
URI/URL : [Link]

Avertissement à l'attention des usagers :

Tous les documents placés en accès ouvert sur le site le site MatheO sont protégés par le droit d'auteur. Conformément
aux principes énoncés par la "Budapest Open Access Initiative"(BOAI, 2002), l'utilisateur du site peut lire, télécharger,
copier, transmettre, imprimer, chercher ou faire un lien vers le texte intégral de ces documents, les disséquer pour les
indexer, s'en servir de données pour un logiciel, ou s'en servir à toute autre fin légale (ou prévue par la réglementation
relative au droit d'auteur). Toute utilisation du document à des fins commerciales est strictement interdite.

Par ailleurs, l'utilisateur s'engage à respecter les droits moraux de l'auteur, principalement le droit à l'intégrité de l'oeuvre
et le droit de paternité et ce dans toute utilisation que l'utilisateur entreprend. Ainsi, à titre d'exemple, lorsqu'il reproduira
un document par extrait ou dans son intégralité, l'utilisateur citera de manière complète les sources telles que
mentionnées ci-dessus. Toute utilisation non explicitement autorisée ci-avant (telle que par exemple, la modification du
document ou son résumé) nécessite l'autorisation préalable et expresse des auteurs ou de leurs ayants droit.
 Université de Liège
Faculté des Sciences
Département de Mathématique

Introduction à la théorie des codes

Mémoire présenté en vue de l’obtention du grade de Master en sciences mathématiques à

finalité didactique

Promoteur : Julien Leroy

Emeline Talmas

Année académique 2020–2021

ii
Remerciements

Le succès est la somme de petits efforts, répétés jour après jour.

— Leo Robert Collier
Je tiens tout d’abord à remercier chaleureusement mon promoteur Julien Leroy pour
m’avoir proposé ce sujet de mémoire et pour son encadrement tout au long de l’élaboration
de ce travail.
J’adresse un grand merci à ma maman et à ma sœur qui ont relu courageusement ce
mémoire qui leur était totalement incompréhensible.
Je remercie également ma famille et mes amis, peut-être plus particulièrement ceux qui
ont partagé avec moi ces études, pour leur soutien durant ces dernières années.
Finalement je remercie « mon » Julien d’avoir supporté mes moments de doute, de
stress et d’avoir toujours cru en moi. Son soutien a sans doute été le plus précieux.

iii
iv
Table des matières

Introduction vii

1 Codes 1
1.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Semi-groupes, monoïdes et mots . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Séries formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Premières définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Qu’est-ce qu’un code ? . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Ensembles préfixes, suffixes, bifixes . . . . . . . . . . . . . . . . . . 9
1.2.3 Codes maximaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Un algorithme pour les codes . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Idée de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Codes et sous-monoïdes libres . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Théorème du défaut . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Description quantitative des codes 29

2.1 Mesure des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.1 Lois de probabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 Lois de Bernoulli . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.3 Codes et lois de Bernoulli . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Ensembles complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Codes préfixes 55
3.1 Premiers résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 Lien avec les séries formelles . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3 Représentation graphique des codes préfixes . . . . . . . . . . . . . . . . . 60
3.4 Ensembles préfixes et automates . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5 Codes préfixes maximaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.6 Quelques opérations sur les ensembles préfixes . . . . . . . . . . . . . . . . 73
3.7 Codes sémaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

v
vi TABLE DES MATIÈRES

Bibliographie 81
Introduction

On doit la naissance de la théorie des codes à la théorie de l’information de Claude

Shannon, développée dans les années 1950. Cette dernière, dont le sujet premier est de
quantifier le contenu en information d’un ensemble de données, s’intéresse notamment à la
quantité d’information transmissible. C’est dans ce contexte qu’apparaissent les notions de
code et de codage. Un codage est une application injective d’un alphabet A dans l’ensemble
des mots non vides sur un alphabet B. Un codage s’étend en un morphisme de A∗ dans
B ∗ ; si ce morphisme est également injectif, le codage est dit à déchiffrage unique. Dans ce
cas, nous appellerons code l’image du codage.

La théorie des codes émerge donc de la théorie de l’information, mais peut être étu-
diée indépendamment de celle-ci, pour ses propriétés mathématiques intrinsèques. C’est
d’ailleurs l’approche que nous adopterons dans ce mémoire. Nous définirons donc la notion
de code d’une manière légèrement différente, bien qu’équivalente comme nous le verrons
ultérieurement : un code est un ensemble de mots tel que tout mot admet au plus une
décomposition en facteurs de cet ensemble. De manière générale, nous pouvons voir la
théorie des codes comme une étude des factorisations de mots en facteurs issus d’un en-
semble donné. De ce point de vue, et au vu des problèmes auxquels elle s’intéresse, la
théorie des codes se place au sein de l’informatique théorique.

La définition d’un code telle qu’elle est considérée dans ce mémoire laisse penser qu’il
s’agit d’un concept purement combinatoire. Cependant, comme nous le verrons, la notion
de code est essentiellement équivalente à celle de morphisme injectif d’un monoïde libre
dans un autre. L’étude des codes pourrait donc être finalement considérée comme un pro-
blème d’algèbre. Ce n’est pas dans ce sens que nous traiterons ce problème puisque nous
faisons le choix d’utiliser principalement des outils de combinatoire des mots, de théorie
des automates et de théorie des langages formels.

Ce travail s’inspire principalement de l’ouvrage [3] Codes and Automata de Jean Bers-
tel, Dominique Perrin et Christophe Reutenauer, et s’articule de la façon suivante.

Le Chapitre 1 sera consacré à une introduction générale des codes. Nous commencerons
par définir la notion de code, sur laquelle repose tout ce travail. Nous en donnerons en-
suite quelques équivalences. Les codes pouvant être regroupés en différentes familles, nous

vii
viii INTRODUCTION

introduirons notamment les codes préfixes, suffixes, bifixes ou encore les codes maximaux.
Nous reviendrons sur la notion de code maximal au Chapitre 2 et l’étude des codes préfixes
se fera plus en détail au Chapitre 3. De plus, nous fournirons une méthode algorithmique
nous permettant de vérifier qu’un ensemble de mots donné est un code. Finalement nous
nous intéresserons aux sous-monoïdes libres et aux propriétés qui les lient aux codes.

Le Chapitre 2 sera dédié notamment à la mesure des codes. Après avoir introduit les
lois de probabilité sur un alphabet, nous nous pencherons plus précisément sur les lois de
Bernoulli. Ces dernières seront utiles non seulement pour établir des conditions nécessaires
pour qu’un ensemble de mots soit un code, mais également pour comprendre qu’un code
ne peut contenir que « peu » de « petits » mots. Nous aborderons ensuite des notions de
densité et introduirons entre autres les notions d’ensembles complets, de codes maximaux
et de codes fins. Les notions qui seront présentées dans cette section nous permettront
d’établir quelques résultats à propos des codes maximaux. Ces derniers constituent une
famille privilégiée de codes qu’il est intéressant d’étudier puisque nous verrons que tout
sous-ensemble d’un code est encore un code.

Le Chapitre 3, comme annoncé précédemment, sera axé sur les codes préfixes. Il s’agit
sans doute de la famille de codes la plus facile à reconnaitre et à construire. Nous commen-
cerons par en donner quelques propriétés de base. Ensuite, nous établirons des liens entre
ces codes particuliers et d’autres branches des mathématiques discrètes comme les séries
formelles ou la théorie des automates. Nous nous intéresserons également à la maxima-
lité des codes préfixes. Pour ce faire, nous adapterons les notions de densité présentées au
Chapitre 2 à ce cas particulier. Finalement, nous étudierons un sous-ensemble spécifique
des codes préfixes : les codes sémaphores. De manière évidente, les résultats qui seront
présentés dans ce chapitre pourront être adaptés au cas des codes suffixes.
Chapitre 1

Codes

Ce premier chapitre sera dédié à l’introduction de la notion de code et de leurs propriétés

principales.
Tout d’abord, nous définirons les codes, en donnerons des exemples et contre-exemples,
et fournirons une caractérisation des codes et ses conséquences. Nous définirons également
des familles particulières de codes : codes préfixes, suffixes, bifixes, maximaux.
Ensuite, nous présenterons un algorithme permettant de déterminer si un ensemble
donné est un code.
Finalement, nous étudierons les liens entre codes et sous-monoïdes libres et démontre-
rons le Théorème du défaut, qui fournit une condition suffisante pour être un code.

1.1 Rappels
1.1.1 Semi-groupes, monoïdes et mots
Un semi-groupe est un ensemble muni d’une opération binaire associative. Un monoïde
M est un semi-groupe qui possède un élément neutre, noté 1M . Un sous-monoïde d’un
monoïde M est une partie N de M qui est stable pour l’opération et qui contient l’élément
neutre de M . Un morphisme de monoïdes entre deux monoïdes M et N est une application
ϕ : M → N qui satisfait ϕ(mm0 ) = ϕ(m)ϕ(m0 ) pour tous m, m0 ∈ M et ϕ(1M ) = 1N .
Soit A un ensemble que nous appellons alphabet. Dans la suite, sauf mention explicite
du contraire, un alphabet sera toujours supposé fini. Les éléments de A sont appelés lettres.
Un mot w sur l’alphabet A est une suite finie d’éléments de A : w = a1 a2 · · · an avec ai ∈ A.
Le mot vide est noté ε. L’ensemble de tous les mots sur l’alphabet A est noté A∗ . Muni de
la concaténation, cet ensemble possède une structure de monoïde ayant ε pour neutre. Ce
monoïde est appelé monoïde libre sur A. L’ensemble des mots non vides sur A est noté A+ .
La longueur d’un mot w = a1 a2 · · · an avec ai ∈ A est le nombre n de lettres dans w. Nous
la notons |w|. Par définition, |ε| = 0. Un facteur d’un mot w ∈ A∗ est un mot x ∈ A∗ tel
qu’il existe u, v ∈ A∗ tels que w = uxv. Il est dit propre si w 6= x. Un mot x est un préfixe
(resp. suffixe) d’un mot w ∈ A∗ s’il existe un mot u ∈ A∗ tel que w = xu (resp. w = ux).

1
2 CHAPITRE 1. CODES

Un ensemble X est dit fermé par préfixe (resp. fermé par suffixe ) s’il contient tous les
préfixes (resp. suffixes) de ses éléments. Pour un sous-ensemble X de A∗ , nous notons X ∗
le sous-monoïde engendré par X, i.e.
X ∗ = {x1 x2 · · · xn | n ≥ 0, xi ∈ X}.
De la même façon, nous notons X + le semi-groupe engendré par X, i.e.
X + = {x1 x2 · · · xn | n ≥ 1, xi ∈ X}.
Soient X, Y ⊂ A∗ . On définit le produit de X et Y par
XY = {xy | x ∈ X, y ∈ Y }.
Le produit XY est non ambigu si lorsque l’on a xy = x0 y 0 avec x, x0 ∈ X et y, y 0 ∈ Y , on
a x = x0 et y = y 0 .
Soient X ⊂ A∗ et w ∈ A∗ . L’ensemble w−1 X (resp. Xw−1 ) est l’ensemble des mots qui
concaténés à droite (resp. gauche) de w sont dans X, i.e.
w−1 X = {u ∈ A∗ | wu ∈ X} (resp. Xw−1 = {u ∈ A∗ | uw ∈ X}).
Si Y est une partie de A∗ , nous notons
[ [
Y −1 X = w−1 X et XY −1 = Xw−1 .
w∈Y w∈Y

Soit M un monoïde. Un idéal à droite (resp. à gauche, bilatère) est un sous-ensemble non
vide I de M tel que IM ⊂ I (resp. M I ⊂ I, M IM ⊂ I). Dans la suite, nous désignerons
par idéal un idéal bilatère. Si X est inclus dans M , nous appellerons XM (resp. M X,
M XM ) l’idéal à droite (resp. à gauche, bilatère) engendré par X.

1.1.2 Séries formelles

Soient A un alphabet et K un semi-anneau. Une série formelle sur A à coefficients dans
K est une application
S : A∗ → K.
On note (S, w) l’image d’un mot w ∈ A∗ par l’application S. On note KhhAii l’ensemble des
séries formelles sur A. Soient S, T ∈ KhhAii et k ∈ K, on définit les opérations suivantes :
1. La somme :
S + T : A∗ → K, w 7→ (S, w) + (T, w).
Ainsi, (S + T, w) = (S, w) + (T, w) pour tout w ∈ A∗ .
2. Le produit de Cauchy :
X
ST : A∗ → K, w 7→ (S, u)(T, v).
uv=w
X
Ainsi, (ST, w) = (S, u)(T, v) pour tout w ∈ A∗ .
uv=w
1.1. RAPPELS 3

Pour X ⊂ A∗ , on écrit X pour désigner la série caractéristique de X définie par

(
1 si w ∈ X
(X, w) =
0 sinon.

Dans le cas où X = {w}, on note w la série caractéristique de X.

Muni de ces opérations, KhhAii est un anneau. Le neutre pour le produit est la série ε.

La série S ∈ KhhAii est dite propre si (S, ε) = 0. Lorsque S est propre on note
X X
S∗ = S n et S + = S n.
n≥0 n≥1

Dans ce cas, ces sommes sont bien définies puisque, pour w fixé, on a (S n , w) = 0 pour n
suffisamment grand. On a alors S ∗ = ε + S + et S ∗ S = SS ∗ = S + .

Proposition 1.1.1. Soient K un anneau et S ∈ KhhAii. La série S est inversible dans

KhhAii si et seulement si son terme indépendant est inversible dans K.

Proposition 1.1.2. Soit K un anneau et S ∈ KhhAii une série propre. La série ε − S est
inversible et S ∗ = (ε − S)−1 .
X
Pour toute série formelle S ∈ KhhAii nous notons S = (S, w)w.
w∈A∗

Proposition 1.1.3. Soient X, Y ∈ A∗ . On a


2 si w ∈ X ∩ Y

(X + Y , w) = 1 si w ∈ (X\Y ) ∪ (Y \X)

0 si w ∈
/ X ∪ Y.


En particulier, si X et Y sont disjoints, alors X + Y = X ∪ Y .

Proposition 1.1.4. Soient X, Y ∈ A∗ . On a

(X Y , w) = Card{(x, y) ∈ X × Y | w = xy}.

En particulier, on a XY = X Y si et seulement si le produit XY est non ambigu.

Proposition 1.1.5. Soient X ∈ A∗ . On a

((X)∗ , w) = Card{(x1 , x2 , . . . , xn ) | n ≥ 0, xi ∈ X, w = x1 · · · xn }.
4 CHAPITRE 1. CODES

1.1.3 Automates
Un automate déterministe est la donnée d’un quintuple
A = {Q, q0 , F, A, δ}
où Q est un ensemble dont les éléments sont les états de A ; q0 ∈ Q est un état privilégié
appelé état initial ; F ⊂ Q est l’ensemble des états finals ; A est l’alphabet de l’automate ;
δ : Q × A → Q est la fonction de transition de A. Nous supposerons que δ est une fonction
totale. On étend la fonction δ à Q × A∗ par récurrence en posant δ(q, ε) = q et pour tous
w ∈ A∗ et a ∈ A :
δ(q, wa) = δ(δ(q, w), a).
On définit l’automate minimal
AX = (QX , q0,X , FX , A, δX )
d’un sous-ensemble X de A∗ de la manière suivante :
• QX = {w−1 X | w ∈ A∗ },
• q0,X = ε−1 X = X,
• FX = {w−1 X | w ∈ X},
• δX (q, a) = a−1 q pour tout q ∈ QX , a ∈ A.
L’automate minimal d’un sous-ensemble X de A∗ accepte X.
Un automate déterministe A = {Q, q0 , F, A, δ} est accessible si pour tout état q ∈ Q,
il existe un mot w ∈ A∗ tel que δ(q0 , w) = q. Il est coaccessible si pour tout état q ∈ Q, il
existe un mot w ∈ A∗ tel que δ(q, w) ∈ F . Il est réduit si pour tous p, q ∈ Q
{w ∈ A∗ | δ(p, w) ∈ F } = {w ∈ A∗ | δ(q, w) ∈ F } ⇒ p = q.
Autrement dit, l’automate est réduit si pour tout couple (p, q) d’états avec p 6= q il existe
un mot w ∈ A∗ tel que
δ(p, w) ∈ F et δ(q, w) ∈
/F
ou
δ(p, w) ∈
/ F et δ(q, w) ∈ F.
Dans ce cas, on dit que le mot w distingue les états p et q et que ces états sont distingués.
L’automate minimal AX d’un ensemble X ⊂ A∗ est déterministe, accessible et réduit.

1.2 Premières définitions et propriétés

1.2.1 Qu’est-ce qu’un code ?
Définition 1.2.1. Soit A un alphabet. Un sous-ensemble X du monoïde libre A∗ est un
code sur A si pour tous m, n ≥ 1 et x1 , . . . , xm , y1 , . . . , yn ∈ X, la condition
x1 x2 · · · xm = y 1 y 2 · · · y n
1.2. PREMIÈRES DÉFINITIONS ET PROPRIÉTÉS 5

implique m = n et xi = yi pour i = 1, . . . , m.
Un élément du code sera simplement appelé mot du code.

Autrement dit, un ensemble X est un code si tout mot de X ∗ possède une unique
factorisation en mots de X.
Étant donné cette définition, il est évident qu’un code ne contient pas le mot vide ε.

Remarque 1.2.2. Tout alphabet A est trivialement un code.

Exemple 1.2.3. Soit l’alphabet A = {a, b}. L’ensemble X = {aa, baa, ba} est un code sur
A.
Procédons par l’absurde pour le montrer.
Supposons qu’il existe un mot w de X + , de longueur minimale, qui possède deux factori-
sations distinctes :

w = x1 x2 · · · xm
= y1 y2 · · · yn

avec m, n ≥ 1 et xi , yj ∈ X.
Puisque l’on a supposé que w était de longueur minimale, on a forcément x1 6= y1 , ce qui
implique que soit x1 est préfixe de y1 , soit y1 est préfixe de x1 . Supposons que x1 est préfixe
de y1 . Vu la définition de notre ensemble X, on a x1 = ba et y1 = baa. Ainsi a doit être un
préfixe de x2 , impliquant alors que x2 = aa. Ensuite, on voit que a doit être un préfixe de
y2 également, ce qui entraine que y2 = aa :

w = ba aa · · · xm
= baa aa · · · yn

Ainsi, on a que y1 = x1 a et y1 y2 = x1 x2 a.
Si l’on suppose avoir y1 y2 · · · yp = x1 x2 · · · xp a (avec p ≤ min{m, n}) , on aura forcément
yp+1 = aa puis xp+1 = aa. On obtient alors

y1 y2 · · · yp+1 = x1 x2 · · · xp+1 a.

Finalement, il vient
w = y1 y2 · · · yn = x1 x2 · · · xn a,
or a ∈
/ X, ce qui contredit le fait que w possède deux factorisations distinctes en mots de
X.

Exemple 1.2.4. Soit l’alphabet A = {a, b}. L’ensemble X = {a, ab, ba} n’est, quant à lui,
pas un code puisque le mot w = aba possède deux factorisations distinctes en mots de X :

w = ab · a = a · ba.

Proposition 1.2.5. Tout sous-ensemble d’un code est encore un code.

6 CHAPITRE 1. CODES

Définition 1.2.6. Si p est un naturel non nul, l’ensemble X = Ap est appelé le code
uniforme des mots de longueur p.
Il s’agit en effet d’un code : soit w ∈ X ∗ tel que
w = x1 x2 · · · xm = y1 y2 · · · yn ,
avec m, n ≥ 1 et xi , yj ∈ X. Puisque les mots de X sont de longueur constante p, la seule
manière de factoriser w en mots de X est de considérer des blocs de longueur p, ce qui
implique donc que m = n et xi = yi pour i = 1, . . . , m.

Le résultat suivant nous permet de reformuler la problématique de l’étude des codes

en un problème purement algébrique : les codes correspondent en effet exactement aux
morphismes injectifs d’un monoïde libre dans un autre.
Théorème 1.2.7. Si un sous-ensemble X de A∗ est un code alors toute bijection d’un
alphabet B (éventuellement infini) dans X s’étend en un morphisme injectif de B ∗ dans
A∗ .
Inversement, s’il existe un morphisme injectif β : B ∗ → A∗ tel que X = β(B) alors X
est un code.
Démonstration. Soit f : B → X une bijection. On définit l’application β : B ∗ → A∗ de la
façon suivante :
β(ε) = ε et β(b) = f (b1 )f (b2 ) · · · f (bn )
pour tout b ∈ B ∗ tel que b = b1 b2 · · · bn , avec bi ∈ B pour i = 1, . . . , n.
Montrons que β est un morphisme injectif étendant f :
• β est un morphisme :
En effet, vu la définition de β on a β(ε) = ε.
De plus, soient b, b0 ∈ B ∗ tels que b = b1 b2 · · · bn et b0 = b01 b02 · · · b0m . On a alors :
β(b · b0 ) = β(b1 b2 · · · bn b01 b02 · · · b0m )
= f (b1 )f (b2 ) · · · f (bn )f (b01 )f (b02 ) · · · f (b0m )
= β(b)β(b0 ).

• β étend f :
Si b ∈ B, alors on a simplement β(b) = f (b).

• β est injectif :
Soient u, v ∈ B ∗ des mots tels que β(u) = β(v). Notons
u = b1 b2 · · · bm et v = b01 b02 · · · b0n ,
avec m, n ≥ 1 et bi , b0j ∈ B.
Par définition de β, on obtient que
β(u) = f (b1 )f (b2 ) · · · f (bm ) = f (b01 )f (b02 ) · · · f (b0n ) = β(v).
1.2. PREMIÈRES DÉFINITIONS ET PROPRIÉTÉS 7

avec f (bi ), f (b0j ) ∈ X.

L’ensemble X étant un code, il vient m = n et f (bi ) = f (b0i ) pour i = 1, . . . m.
On a alors que bi = b0i pour i = 1, . . . , m, puisque f : B → X est en particulier
injectif. Finalement on obtient bien que u = v.
Inversement, soit β : B ∗ → A∗ un morphisme injectif. Si on a

x1 x2 · · · xm = y1 y2 · · · yn

pour m, n ≥ 1 et xi , yj ∈ X = β(B), alors il existe des bi , b0j ∈ B tels que xi = β(bi ) et

yj = β(b0j ). Il vient alors
x1 x2 · · · xm = β(b1 b2 · · · bm )
et
y1 y2 · · · yn = β(b01 b02 · · · b0n ).
Ainsi, par injectivité de β, on a b1 b2 · · · bm = b01 b02 · · · b0n . Puisque les bi , b0j sont des lettres,
il vient que m = n et bi = b0i pour i = 1, . . . , m.
Finalement on obtient xi = yi pour i = 1, . . . , m, ce qui conclut que X est bien un code.

Définition 1.2.8. Soient A, B deux alphabets, B éventuellement infini, et X ⊂ A∗ . Un

morphisme β : B ∗ → A∗ qui est injectif et tel que X = β(B) est appelé un codage pour X.

Le théorème et la définition qui précèdent nous permettent de faire le lien entre nos
codes et ceux utilisés dans le cadre de la théorie de l’information. Ceci montre en effet que
les codes tels que nous les étudions sont précisément les images des codages à déchiffrage
unique.

Exemple 1.2.9. Grâce au résultat précédent, on obtient une autre façon de montrer que
l’ensemble X de l’Exemple 1.2.4. n’est pas un code.
En effet, considérons le morphisme ϕ : B ∗ = {1, 2, 3}∗ → A∗ = {a, b}∗ tel que

ϕ(1) = a, ϕ(2) = ab, ϕ(3) = ba.

Il n’est pas injectif puisque ϕ(13) = aba = ϕ(21). Ainsi, ϕ(B) = X = {a, ab, ba} n’est pas
un code.

Le corollaire suivant nous montre que l’image (resp. l’image inverse) d’un code par un
morphisme injectif est encore un code.

Corollaire 1.2.10. Soit α : A∗ → C ∗ un morphisme injectif. Si X est un code sur A alors

α(X) est un code sur C et si Y est un code sur C alors α−1 (Y ) est un code sur A.

Démonstration. Soit β : B ∗ → A∗ un codage pour X.

On a que
α ◦ β : B∗ → C ∗
8 CHAPITRE 1. CODES

est un morphisme injectif.

En appliquant le Théorème 1.2.7, on obtient que α(β(B)) = α(X) est un code.
Soit X = α−1 (Y ). Soient m, n ≥ 1, x1 , . . . , xm , x01 , . . . x0n ∈ X tels que

x1 x2 · · · xm = x01 x02 · · · x0n .

Il vient alors que

α(x1 x2 · · · xm ) = α(x01 x02 · · · x0n )

⇔ α(x1 )α(x2 ) · · · α(xm ) = α(x01 )α(x02 ) · · · α(x0n )

avec α(xi ), α(x0j ) ∈ Y .

Puisque Y est un code, on a m = n et α(xi ) = α(x0i ). Par injectivité, on en tire que xi = x0i
pour i = 1, . . . , m. Ainsi X = α−1 (Y ) est bien un code.

Exemple 1.2.11. L’ensemble X = {00, 01, 02, 1, 2} est un code 1 sur l’alphabet B =
{0, 1, 2}.
Soit α : B ∗ → A∗ , avec A = {a, b} un morphisme tel que

α(0) = a, α(1) = ab, α(2) = bb.

Puisque l’ensemble X 0 = {a, ab, bb} est un code 2 , nous savons, grâce au Théorème 1.2.7,
que α est injectif.
Ainsi l’ensemble α(X) = {aa, aab, abb, ab, bb} est un code.

Corollaire 1.2.12. Si X ⊂ A∗ est un code, alors X n est un code pour tout naturel non
nul n.

Démonstration. Soit β : B ∗ → A∗ un codage pour X. On a 3 X n = (β(B))n = (β(B n )).

Or on sait que B n est un code uniforme. Ainsi, par le Corollaire 1.2.10, on sait que X n
est un code puisqu’il s’agit de l’image d’un code par un morphisme injectif.

Remarque 1.2.13. Le corollaire précédent nous montre que toute puissance d’un code
est encore un code. Cependant le produit de deux codes distincts n’est pas nécessairement
un code.
En effet, considérons les codes suivants :

X = {a, ba} et Y = {a, ab}

1. Nous vérifierons aisément que l’ensemble X est bel et bien un code lorsque nous aurons défini les
ensembles préfixes.
2. De la même façon, nous le vérifierons plus facilement après avoir défini les ensembles suffixes.
3. L’égalité (β(B))n = β(B n ) est assez directe en procédant par double inclusion.
1.2. PREMIÈRES DÉFINITIONS ET PROPRIÉTÉS 9

sur l’alphabet A = {a, b}. Posons Z = XY , il vient

Z = {aa, aab, baa, baab}.
Considérons le mot w = aabaab ∈ Z ∗ . Il possède deux factorisations distinctes en mots de
Z:
w = aab · aab
= aa · baab

1.2.2 Ensembles préfixes, suffixes, bifixes

Soient x, y ∈ A∗ . Nous notons x  y (resp. x ≺ y) le fait que x est un préfixe (resp.
préfixe propre) de y. La relation  est un ordre appelé ordre préfixe.
Définition 1.2.14. Un sous-ensemble X de A∗ est dit préfixe si aucun élément de X n’est
préfixe propre d’un autre élément de X.
Autrement dit, X est préfixe si pour tous x, y ∈ X, la relation x  y entraine x = y.
Remarque 1.2.15. Si un ensemble préfixe X contient le mot vide ε, alors on a X = {ε}.
Définition 1.2.16. Un sous-ensemble X de A∗ est dit suffixe si aucun élément de X n’est
suffixe propre d’un autre élément de X.
Définition 1.2.17. Un ensemble est dit bifixe s’il est à la fois préfixe et suffixe.
Proposition 1.2.18. Tout ensemble préfixe (suffixe, bifixe) X 6= {ε} est un code.
Démonstration. Étant donné que X 6= {ε}, on sait déjà que ε ∈/ X.
Procédons alors par l’absurde. Supposons que l’ensemble X n’est pas un code.
Il existe donc un mot w ∈ X ∗ , que l’on suppose être de longueur minimale, qui possède
deux factorisations distinctes en mots de X :
w = x1 x2 · · · xm
= y1 y2 · · · yn ,
avec m, n ≥ 1 et xi , yj ∈ X.
On a donc x1 6= y1 et par conséquent, on a soit x1 ≺ y1 , soit y1 ≺ x1 , ce qui contredit le
fait que X est un ensemble préfixe.

Définition 1.2.19. Un code préfixe (suffixe, bifixe) est un ensemble préfixe (suffixe, bifixe)
qui est un code, c’est-à-dire distinct de {ε}.
Nous vérifions maintenant que les ensembles de l’Exemple 1.2.11 sont effectivement des
codes puisque
— l’ensemble X = {00, 01, 02, 1, 2} est préfixe,
— l’ensemble X 0 = {a, ab, bb} est suffixe.
Exemple 1.2.20. Les codes uniformes sont des codes bifixes.
10 CHAPITRE 1. CODES

1.2.3 Codes maximaux

Définition 1.2.21. Un code X est maximal sur un alphabet A si X n’est pas strictement
inclus dans un autre code sur A, i.e. si X ⊂ X 0 avec X 0 un code sur A implique X = X 0 .
Remarque 1.2.22. Le caractère maximal d’un code dépend évidemment de l’alphabet
sur lequel il est défini. En effet, si X ⊂ A∗ et A ⊂ B, on a X ⊂ B ∗ . Ce n’est pas parce que
X est maximal sur A qu’il l’est sur B.
Proposition 1.2.23. Les codes uniformes sont maximaux.
Démonstration. Soit un alphabet A. Considérons le code uniforme An pour un n > 0.
Procédons par l’absurde et supposons que An n’est pas maximal.
Il existe donc un mot u ∈ A+ \An tel que Y = An ∪ {u} est un code. Considérons le mot
w = un . On a w ∈ Y ∗ mais également w ∈ (An )∗ puisque sa longueur est un multiple de n.
On a alors
w = un = x1 x2 · · · x|u|
avec x1 , x2 , . . . , x|u| ∈ An ⊂ Y .
Or u ∈/ An donc w possède deux factorisations distinctes en mots de Y , ce qui contredit le
fait que Y est un code.

Proposition 1.2.24. Tout code X sur A est contenu dans un code maximal sur A.
Démonstration. Soit F l’ensemble des codes sur A contenant X, ordonné par l’inclusion.
Pour montrer que F contient un élément maximal, nous allons utiliser le Lemme de Zorn,
i.e. nous allons montrer que toute chaine C de F admet un majorant. Notons que F est
non vide puisqu’il contient X.
Considérons une chaine C de codes contenant X.
Posons Y = ∪Y ∈C Y . Montrons alors que Y ∈ F et que Y majore C.
• Il est évident, vu sa définition, que Y majore C.
• On a Y ∈ F :
En effet, par définition nous savons que X ⊂ Y puisque chaque Y ∈ C contient X. Il
nous reste donc à montrer que Y est bien un code.
Soient m, n ≥ 1 et x1 , . . . , xm , y1 , . . . yn ∈ Y tels que :
x1 · · · xm = y 1 · · · y n .
Il existe donc Y1,1 , . . . , Y1,m , Y2,1 , . . . , Y2,n ∈ C tels que x1 ∈ Y1,1 , . . . , xm ∈ Y1,m , y1 ∈
Y2,1 , . . . yn ∈ Y2,n . Nous avons alors n + m éléments de C, il y a donc un de ces
éléments qui contient tous les autres puisque C est une chaine. Notons le Y 0 . Ainsi
on a xi , yj ∈ Y 0 qui est un code par définition. Il vient alors que n = m et xi = yi
pour i = 1, . . . , m.

Remarque 1.2.25. Cette proposition, comme nous le verrons dans la Section 2.2, n’est
plus vraie si nous nous limitons à des codes finis, i.e. tout code fini n’est pas nécessairement
inclus dans un code maximal fini.
1.3. UN ALGORITHME POUR LES CODES 11

1.3 Un algorithme pour les codes

Il n’est pas toujours facile de vérifier qu’un ensemble donné est un code. Dans cette
section, nous allons décrire un algorithme qui nous permettra de déterminer si un ensemble
de mots satisfait à la définition d’un code.

1.3.1 Idée de l’algorithme

Pour se familiariser avec l’algorithme, partons d’un exemple.
Soit X = {b, abb, abbba, bbba, baabb}.
Si nous souhaitions « naïvement » trouver un mot w ∈ X ∗ possédant deux décompositions
en mots de X de manière systématique, nous pourrions procéder de la manière suivante :
• Première étape :
Nous commençons par chercher tous les mots de X qui sont préfixes d’autres mots
de X. Vu notre exemple, nous obtenons les égalités suivantes :

(bbba) = (b)bba (1.1)

(baabb) = (b)aabb (1.2)
(abbba) = (abb)ba (1.3)

Nous appellons les suffixes soulignés les restes.

• Deuxième étape :
Nous essayons ensuite de compléter les égalités ci-dessus à partir de ces restes. Pour
ce faire, nous avons deux possibilités :
1. Soit nous cherchons un mot du code qui a le reste comme préfixe.
2. Soit nous cherchons un mot du code qui est préfixe du reste.
Le reste bba de l’égalité 1.1 a b comme préfixe mais n’est préfixe d’aucun mot de X,
ainsi l’égalité devient

(bbba) = (b)(b)ba. (1.4)

Le reste aabb de l’égalité 1.2 n’est préfixe d’aucun mot de X et n’a aucun préfixe dans
X. Cette égalité ne pouvant être complétée, elle ne peut déboucher sur une double
factorisation.
Le reste ba de l’égalité 1.3 a b comme préfixe et est préfixe de baabb. Nous obtenons
donc ces deux nouvelles égalités :

(abbba) = (abb)(b)a (1.5)

(abbba)abb = (abb)(baabb) (1.6)

À l’issue de cette étape nous obtenons donc de nouveaux restes.

12 CHAPITRE 1. CODES

• Troisième étape :
La démarche est la même que celle appliquée précédemment, seuls les restes ont
changé. Nous obtenons alors les égalités suivantes :

(bbba)abb = (b)(b)(baabb) (1.7)

(bbba) = (b)(b)(b)a (1.8)

(abbba)bbba = (abb)(b)(abbba) (1.9)

(abbba)bb = (abb)(b)(abb) (1.10)

(abbba)(abb) = (abb)(baabb) (1.11)

(abbba)(abbba) = (abb)(baabb)ba (1.12)

Remarquons que le reste de l’égalité 1.6 est lui-même un mot de X. C’est pourquoi
l’égalité 1.11 nous donne une double factorisation du mot w = abbbaabb en mots de
X. Puisque nous avons obtenu une double factorisation, nous pouvons en conclure
que l’ensemble X n’est pas un code et ainsi arrêter notre recherche.

Observons que dans la méthode présentée ci-dessus, seuls les restes nous importent. Par
ailleurs, nous obtenons une double factorisation à l’égalité 1.11 car le reste est le mot vide.

Formalisons cette construction. Étant donné un ensemble X ⊂ A+ , posons :

U1 = X −1 X\{ε}
Un+1 = X −1 Un ∪ Un−1 X (n ≥ 1).

Ainsi défini, l’ensemble Un contient tous les restes calculés à l’étape n. Remarquons que
l’ensemble X −1 Un correspond aux restes de Un ayant un préfixe dans X et Un−1 X corres-
pond aux restes de Un étant préfixes d’un mot de X.

De manière évidente, l’algorithme se termine lorsqu’un des ensembles Un contient le

mot vide puisque cela signifie que l’on a trouvé un mot qui possède deux factorisations
distinctes et par conséquent que X n’est pas un code. Par ailleurs, il est également clair
que dès qu’il existe i 6= j tels que Ui = Uj , les ensembles Un seront périodiques : nous
pouvons alors arrêter l’algorithme dès que nous sommes dans un tel cas. Si le mot vide
n’apparait dans aucun des Un alors l’ensemble X sera un code.
Nous montrerons dans la suite qu’avec cette deuxième condition l’algorithme s’arrête tou-
jours dans le cas où X est un ensemble régulier.

Remarquons que dans le cas où X ⊂ A+ est un ensemble préfixe, nous avons directement

U1 = ∅.
1.3. UN ALGORITHME POUR LES CODES 13

Par conséquent, U2 = U1 , l’algorithme s’arrête et on en conclut que X est un code.

Notons que cette méthode ne nous était pas totalement inconnue : c’est en effet essen-
tiellement la méthode qui nous a permis de conclure que l’ensemble X de l’Exemple 1.2.3
est bien un code (les restes seront toujours égaux à a).

1.3.2 Exemples
Illustrons l’algorithme décrit ci-dessus sur deux exemples.
Exemple 1.3.1. Considérons l’ensemble X = {ab, baa, bbab, abbb} sur l’alphabet A =
{a, b}. Calculons la suite (Un )n≥1 :

U1 = {bb}
U2 = {ab}
U3 = {ε, bb}

Ainsi ε ∈ U3 , donc X n’est pas un code.

Deux décompositions d’un même mot peuvent être obtenues en « remontant » l’algo-
rithme : ε apparait dans U3 car ab est un mot de X, ab apparait dans U2 parce que bb est
préfixe de bbab, et bb apparait dans U1 parce que ab est préfixe de abbb. Ceci nous fournit
la double décomposition
(abbb)(ab) = (ab)(bbab).
Exemple 1.3.2. Considérons l’ensemble X = {ab, bab, bba, bbba, abaa} sur l’alphabet A =
{a, b}. Calculons la suite (Un )n≥1 :

U1 = {aa}
U2 = ∅
U3 = ∅

Nous sommes donc dans le cas où U2 = U3 , l’algorithme s’achève et puisque ε n’est contenu
dans aucun des ensembles Un . On en déduit que X est un code.

1.3.3 Résultats
Présentons maintenant les résultats justifiant formellement l’algorithme décrit précé-
demment.
Lemme 1.3.3. Soit X ⊂ A+ et soit la suite (Un )(n≥1) définie comme ci-dessus.
Pour tout n ≥ 1, on a w ∈ Un si et seulement s’il existe des entiers p, q ≥ 1 avec p+q = n+1
et des mots x1 , . . . , xp , y1 , . . . , yq ∈ X avec x1 6= y1 et w suffixe de yq tels que

x1 x2 · · · xp w = y1 y2 · · · yq
14 CHAPITRE 1. CODES

Démonstration. Montrons tout d’abord que la condition est nécessaire. Procédons par ré-
currence sur n.
• Cas de base : n = 1
Si w ∈ U1 , alors par définition on a

xw = y,

avec x, y ∈ X et x 6= y. On a bien que w est suffixe de y.

• Induction : Supposons que la propriété est vraie pour tout j < n et montrons-la pour
n.
Soit w ∈ Un . On a soit xw = v, soit vw = x pour un certain x ∈ X et un certain
v ∈ Un−1 . Par hypothèse de récurrence, il existe des entiers p, q ≥ 1 avec p + q = n
et des mots x1 , . . . , xp , y1 , . . . , yq ∈ X avec x1 6= y1 et v suffixe de yq tels que

x1 x2 · · · xp v = y1 y2 · · · yq ,

— Cas 1 : Si xw = v, alors

x1 x2 · · · xw = y1 y2 · · · yq ,

et la condition est satisfaite par x1 , . . . , xp , xp+1 , y1 , . . . , yq où xp+1 = x, puisque

w est bien suffixe de yq .
— Cas 2 : Si vw = x, alors

x1 x2 · · · xp vw = y1 y2 · · · yq w
x1 x2 · · · xp x = y1 y2 · · · yq w,

et la condition est vérifiée par y1 , . . . , yq , x1 , . . . , xp , xp+1 où xp+1 = x, puisque

w est suffixe de x.
Inversement, supposons qu’il existe des entiers p, q ≥ 1 tels que p + q = n + 1 et des
mots x1 , . . . , xp , y1 , . . . , yq ∈ X avec x1 6= y1 et w suffixe de yq tels que

x1 x2 · · · xp w = y1 y2 · · · yq . (1.13)

Procédons par récurrence sur n pour montrer que w ∈ Un .

• Cas de base : n = 1
On a forcément que p = q = 1 et donc

x1 w = y1

avec x1 , y1 ∈ X et x1 6= y1 . Ainsi, w ∈ U1 = X −1 X\{ε}.

1.3. UN ALGORITHME POUR LES CODES 15

• Induction : Supposons que la propriété est vraie pour tout j < n et montrons-la pour
n.
Puisque w est suffixe de yq , on a yq = vw pour un certain v ∈ A∗ . L’égalité 1.13
devient donc
x1 x2 · · · xp = y1 y2 · · · yq−1 v.
Posons v = v 0 xr+1 · · · xp , où v 0 est suffixe de xr pour un r tel que 1 ≤ r ≤ p. Alors

x1 · · · xr = y1 · · · yq−1 v 0 .

— Cas 1 : q = 1. Alors p > 1. Dans ce cas, on peut supposer r = 1. Il vient alors

x1 = v 0 ∈ X et y1 = v 0 x2 · · · xp w. Ainsi, on a x2 · · · xp w ∈ X −1 X\{ε} = U1 =
Ur+q−1 .
— Cas 2 : q > 1. Par hypothèse de récurrence, v 0 ∈ Ur+q−2 .
−1
Ensuite, puisque yq = v 0 xr+1 · · · xp w, on a xr+1 · · · xp w ∈ Ur+q−2 X ⊂ Ur+q−1 .
Montrons maintenant par récurrence sur i, 1 ≤ i ≤ p − r, que l’on a

xr+i · · · xp w ∈ Ur+q+i−2 .

— Cas de base : i = 1
On a bien, vu ce qui précède :

xr+1 · · · xp w ∈ Ur+q−1 .

— Induction : Supposons que xr+j · · · xp w ∈ Ur+q+j−2 pour j ≤ i. Montrons-le pour

i + 1.
On a, par hypothèse de récurrence

xr+i · · · xp w ∈ Ur+q+i−2 .

Puisque xr+i ∈ X, il vient alors que xr+1+i · · · xp w ∈ Ur+q+i−1 .

On obtient alors finalement que xp w ∈ Up+q−2 et par conséquent

w ∈ X −1 Up+q−2 ⊂ Up+q−1 ,

où p + q − 1 = n.

Théorème 1.3.4. L’ensemble X ⊂ A+ est un code si et seulement si aucun des ensembles

Un définis ci-dessus ne contient le mot vide ε.
Démonstration. Si X n’est pas un code, alors il existe un mot w ∈ X ∗ , que l’on suppose
de longueur minimale, qui possède deux factorisations distinctes en mots de X :

w = x1 x2 · · · xp
= y1 y2 · · · yq
16 CHAPITRE 1. CODES

avec x1 , . . . , xp , y1 , . . . , yq ∈ X et x1 6= y1 .
Par le lemme précédent, il vient que ε ∈ Up+q+1 .
Inversement, si ε ∈ Un , par le lemme, il existe des entiers p, q ≥ 1 tels que p + q = n + 1
et des mots x1 , . . . , xp , y1 , . . . , yq ∈ X, avec x1 6= y1 tels que

x1 x2 · · · xp = y 1 y 2 · · · y q .

Ceci montre que X n’est pas un code.

Lorsque que nous considérons le cas où X est fini ou plus généralement où X est régu-
lier, nous allons voir que le nombre d’ensembles Un est fini, ce qui entraine que l’algorithme
s’achève au vu de la deuxième condition d’arrêt. Il en découle alors que le nombre de calculs
nécessaires pour prouver que X est un code est fini. Ainsi, on en conclut qu’il est décidable
qu’un ensemble fini ou régulier est un code.

Procédons tout d’abord à quelques rappels :

Définition 1.3.5. Soit X ⊂ A∗ . On définit la congruence syntaxique ≡X de X de la façon

suivante. Soient x, y ∈ X, on pose

x ≡X y ⇔ (∀u, v ∈ A∗ : uxv ∈ X ⇔ uyv ∈ X).

Proposition 1.3.6. Muni de l’opération ◦ : A∗ /≡X × A∗ /≡X → A∗ /≡X : ([x], [y]) 7→

[x] ◦ [y], l’ensemble quotient A∗ /≡X possède une structure de monoïde.

Définition 1.3.7. Le monoïde (A∗ /≡X , ◦) est le monoïde syntaxique de X.

Proposition 1.3.8. Un ensemble X est régulier si et seulement si son monoïde syntaxique

est fini.

Avant de démontrer le second résultat qui nous intéresse dans cette sous-section, pré-
sentons tout d’abord quelques résultats intermédiaires qui rendront plus abordable la dé-
monstration de celui-ci.

Proposition 1.3.9. Un ensemble X ⊂ A∗ est une union de classes d’équivalence d’une

congruence R si et seulement si pour tous x ∈ X et y ∈ A∗ tels que xRy , on a y ∈ X.
[
Démonstration. Supposons d’abord que X = [zi ]R .
i
Soient x ∈ X, y ∈ A∗ tels que xRy. Il existe donc un i tel que x ∈ [zi ]R . On a alors xRzi .
Puisque R est une congruence, il vient que yRzi , i.e. y ∈ [zi ]R . Par conséquent, y ∈ X.

∗
[que pour tous x ∈ X, y ∈ A tels que xRy , on a y ∈ X.
Supposons ensuite
Montrons que X = [w]R par double inclusion.
w∈X
1.3. UN ALGORITHME POUR LES CODES 17
[
⊂ : Soit x ∈ X. On a forcément x ∈ [x]R et donc x ∈ [w]R .
w∈X
[
⊃ : Soit x ∈ [w]R . Il existe donc w ∈ X tel que x ∈ [w]R . Ainsi xRw et donc par
w∈X
hypothèse, x ∈ X.

Proposition 1.3.10. Tout ensemble X ⊂ A∗ est une union de classes d’équivalence de sa

congruence syntaxique ≡X .
Démonstration. Soient x ∈ X, y ∈ A∗ tels que x ≡X y. Alors, pour tous u, v ∈ A∗ on a
uxv ∈ X ⇔ uyv ∈ X.
En particulier, εxε = x ∈ X ⇔ εyε = y ∈ X. On a donc bien y ∈ X.

Lemme 1.3.11. Si X ⊂ A∗ est une union de classes d’équivalence d’une congruence R

alors pour tout sous-ensemble Y de A∗ , Y −1 X est une union de classes d’équivalence de
R.
Démonstration. Soient x ∈ Y −1 X, x0 ∈ A∗ tels que xRx0 . Alors yx ∈ X pour un certain
y ∈ Y . Puisque R est une congruence il vient que yxRyx0 . Comme X est une union de
classes d’équivalence, par la Proposition 1.3.9 il vient que yx0 ∈ X. Ainsi, x0 ∈ Y −1 X.

Nous avons désormais tous les outils nécessaires à la démonstration du résultat suivant.
Théorème 1.3.12. Si X ⊂ A+ est régulier alors l’ensemble de tous les Un (n ≥ 1) est
fini.
Démonstration. Soient ≡X la congruence syntaxique de X et µ la congruence 4 sur A∗ qui
a pour classes {ε} et A+ , i.e. xµy ⇔ x, y 6= ε ou x = y = ε. Posons ι = ≡X ∩ µ.
Nous allons montrer que Un est une union de classes d’équivalence de ι par récurrence sur
n ≥ 1.
• Cas de base : n = 1
Vu la Proposition 1.3.10, X est une union de classes d’équivalence de ≡X . Grâce au
Lemme 1.3.11, on sait que X −1 X est également une union de classes de ≡X . Vu la
définition de ι, X −1 X est une union de classes de ι. De plus, comme {ε} est une
classe de ι, X −1 X\{ε} = U1 est encore une union de classes de ι.
• Induction : Supposons que les ensembles Uk sont des unions de classes d’équivalence
pour k ≤ n et montrons que Un+1 est encore une union de classes d’équivalence.
Par hypothèse de récurrence nous savons que Un est une union de classes d’équivalence
de ι. De plus, nous savons aussi que X est une union de classes d’équivalence de ι.
Ainsi Un−1 X et X −1 Un le sont aussi vu le Lemme 1.3.11. Puisque Un+1 = Un−1 X ∪
X −1 Un , Un+1 est encore une union de classes d’équivalence de ι.
4. On vérifie facilement qu’il s’agit bien d’une congruence.
18 CHAPITRE 1. CODES

Il vient donc que Un est une union de classes d’équivalence de ι.

Puisque ι possède un nombre fini de classes d’équivalence 5 , il n’y a qu’un nombre fini de
Un .

Remarque 1.3.13. La réciproque de ce Théorème n’est pas vraie.

En effet, considérons l’ensemble X = {an bn |n ≥ 1} qui n’est pas régulier 6 . Puisque X est
bifixe nous avons U1 = ∅. Ainsi, l’ensemble des Un est fini.

1.4 Codes et sous-monoïdes libres

Dans cette section, nous considérons le sous-monoïde X ∗ généré par un code X. Nous
verrons notamment qu’il est possible de montrer qu’un ensemble de mots est un code en
connaissant uniquement le sous-monoïde qu’il génère.
Proposition 1.4.1. Tout sous-monoïde M de A∗ possède un unique ensemble minimal de
générateurs
X = (M \{ε})\(M \{ε})2
Démonstration. Dans un premier temps, nous allons montrer que X engendre M , i.e.
X∗ = M .
Nous savons déjà, par définition de X, que X ⊂ M . Puisque M est un sous-monoïde, il
est stable pour le produit et donc X ∗ ⊂ M . Nous allons montrer la seconde inclusion en
procédant par récurrence sur la longueur des mots de M :
• Cas de base :
On a ε ∈ X ∗ .
• Induction : Supposons que la propriété est vérifiée pour les mots de longueur j < k
et montrons-la pour les mots de longueur k.
Soit m ∈ M \{ε} tel que |m| = k.
— Cas 1 : si m ∈/ (M \{ε})2 , alors on a directement que m ∈ X ⊂ X ∗ .
— Cas 2 : si m ∈ (M \{ε})2 , alors m = m1 m2 où m1 , m2 ∈ (M \{ε}) et |m1 |, |m2 | <
|m| = k. Ainsi par hypothèse de récurrence, m1 , m2 ∈ X ∗ . Et par stabilité pour
le produit, on obtient m ∈ X ∗ .
Nous avons donc bien l’égalité M = X ∗ .
Montrons maintenant le caractère minimal de X.
Considérons un ensemble Y de générateurs de M . On peut supposer que ε ∈ / Y . On a donc
∗
que chaque x ∈ X ⊂ M est dans Y et peut donc s’écrire de la manière suivante :

x = y1 y2 · · · yn
5. En effet, nous savons que ≡X possède un nombre fini de classes d’équivalence vu la Proposition 1.3.8,
et que µ possède deux classes d’équivalence. Ainsi puisque les classes de ι sont les intersections des classes
de ≡X et µ, il y en a un nombre fini.
6. Nous le vérifions aisément grâce au Lemme de la Pompe.
1.4. CODES ET SOUS-MONOÏDES LIBRES 19

avec yi ∈ Y et n > 0.
/ (M \{ε})2 , on a forcément n = 1. Autrement dit, x = y1 ∈ Y . Il vient
Puisque x 6= ε et x ∈
donc X ⊂ Y .
Ainsi, X est bien un ensemble minimal de générateurs, un tel ensemble est unique.

Remarque 1.4.2. L’ensemble X = (M \{ε})\(M \{ε})2 est un ensemble minimum de

générateurs de M .
Exemple 1.4.3. Soit A = {a, b} et posons M = {w ∈ A∗ | |w|a ≡ 0 mod 2}
On voit 7 que M = (b+ab∗ a)∗ . Ainsi, l’ensemble minimal de générateurs de M est l’ensemble
X = b ∪ ab∗ a. En effet, montrons que X = (M \{ε})\(M \{ε})2 par double inclusion.
On sait déjà que X ∗ = M . Ainsi X est un ensemble de générateurs de M et par conséquent
il contient (M \{ε})\(M \{ε})2 . Réciproquement, soit x ∈ X. Il est clair que x ∈ M \{ε}.
Par ailleurs, x ne peut se décomposer en deux mots non vides de M . En effet cela est clair
si x = b, et sinon, chaque mot de la décomposition contiendrait exactement un a.
Nous allons maintenant nous intéresser aux sous-monoïdes engendrés par des codes.
Définition 1.4.4. Un sous-monoïde M de A∗ est dit libre s’il existe un isomorphisme

α : B∗ → M

d’un monoïde libre B ∗ (B éventuellement infini) dans M .

La proposition suivante nous donne un critère d’équivalence au fait d’être libre.
Théorème 1.4.5. Si M est un sous-monoïde libre de A∗ , alors son ensemble minimal de
générateurs est un code.
Inversement, si X ⊂ A∗ est un code, alors le sous-monoïde X ∗ de A∗ est libre et X est
son ensemble minimal de générateurs.
Démonstration. Soit α : B ∗ → M un isomorphisme. Alors α0 : B ∗ → A∗ : b 7→ α(b) est
un morphisme injectif. Par le Théorème 1.2.7, l’ensemble X = α(B) est un code. On a
M = α(B ∗ ) = (α(B))∗ = X ∗ . Donc X engendre M .
De plus, B = B + \B + B + et α(B + ) = M \{ε}. Il vient donc

X = α(B)
= α(B + \B + B + )
= α(B + )\α(B + B + )
= α(B + )\α(B + )2 ,

ce qui montre que X est l’ensemble minimal de générateurs de M .

7. Il est assez aisé de construire un automate acceptant le language M .
20 CHAPITRE 1. CODES

Inversement, supposons que X ⊂ A∗ est un code et considérons un codage pour X

α : B ∗ → A∗ .

Par définition, α est injectif et α est une bijection de B dans X. On a alors que α est une
bijection entre B ∗ et α(B ∗ ) = X ∗ et ainsi X ∗ est libre.
Il vient :

X = α(B)
= α(B + )\α(B + )α(B + )
= α(B)+ \α(B)+ α(B)+
= X + \X + X +
= (X ∗ \{ε})\(X ∗ \{ε})2

Ainsi, X est bien l’ensemble minimal des générateurs de X ∗ .

Remarque 1.4.6. Le théorème précédent nous permet de construire des sous-monoïdes

libres : il suffit simplement de prendre le sous-monoïde engendré par un code.
Si l’on s’intéresse à l’étude des codes non plus dans des monoïdes libres mais dans des
groupes libres, cela revient à étudier les sous-groupes d’un groupe libre. Or, nous savons
que tout sous-groupe d’un groupe libre est libre, ce qui n’est pas le cas dans les monoïdes
libres, i.e. un sous-monoïde d’un monoïde libre n’est pas nécessairement libre. En effet,
considérons, par exemple, l’alphabet A = {a, b} et le sous-monoïde M = {ε} ∪ A∗ bA∗ de
A∗ . Montrons par l’absurde que M n’est pas un sous-monoïde libre. Supposons qu’il existe
un alphabet C et un isomorphisme ϕ tel que

ϕ : C ∗ → M.

Puisque ϕ est en particulier injectif, nous avons |ϕ(w)| ≥ |w| pour tout w ∈ C ∗ . Comme
b ∈ M , il existe c ∈ C ∗ tel que ϕ(c) = b. Ainsi 1 = |b| ≥ |c|, ce qui implique que c ∈ C
(c 6= ε, par injectivité). Les mots ab et ba sont également dans M , il existe donc d, e ∈ C ∗
tels que ϕ(d) = ab et ϕ(e) = ba. On a donc |d|, |e| ≤ 2. Cependant puisque a ∈ / M , il vient
|d|, |e| =
6 2. On a donc forcément d, e ∈ C. On observe alors que

ϕ(cd) = bab = ϕ(ec),

ce qui contredit l’injectivité de ϕ puisque c 6= d, e.

Le Théorème 1.4.5 implique les deux résultats suivants :
Corollaire 1.4.7. Un sous-monoïde M de A∗ est libre si et seulement s’il existe un code
X ⊂ M tel que M = X ∗ .
Corollaire 1.4.8. Soient X et Y des codes sur un même alphabet A. Si X ∗ = Y ∗ alors
X =Y.
1.4. CODES ET SOUS-MONOÏDES LIBRES 21

Définition 1.4.9. Le code X qui engendre un sous-monoïde libre M de A∗ est appelé la

base de M.
Remarque 1.4.10. Soit M = X ∗ le sous-monoïde de A∗ engendré par X ⊂ A+ . Si X est
un code alors X est la base de M .
Dès lors, si un ensemble X n’est pas un code, nous avons deux possibilités (non exclu-
sives) :
1. X n’est pas l’ensemble minimal de générateurs de X ∗ .
2. X ∗ n’est pas libre.
Définition 1.4.11. Un sous-monoïde N d’un monoïde M est stable dans M si pour tous
u, v, w ∈ M
u, v, uw, wv ∈ N ⇒ w ∈ N,
ce qui peut se réécrire
N −1 N ∩ N N −1 ⊂ N.
Dans la définition précédente, N étant un sous-monoïde, l’inclusion est en fait une éga-
lité. En effet, si w ∈ N alors ww ∈ N , ce qui montre que w ∈ N −1 N ∩ N N −1 .

La proposition suivante nous montre que la notion de stabilité coïncide avec celle de
liberté dans le cas des monoïdes libres.
Proposition 1.4.12. Un sous-monoïde N de A∗ est stable si et seulement s’il est libre.
Démonstration. Supposons que N est stable. Posons X = (N \{ε})\(N \{ε})2 et montrons
que X est un code car dans ce cas, X ∗ = N sera libre.
Procédons par l’absurde et supposons que X n’est pas un code.
Il existe donc un mot z ∈ X ∗ , supposé de longueur minimale, qui possède deux factorisa-
tions distinctes en mots de X :

z = x1 x2 · · · xm = y 1 y 2 · · · y n

avec m, n ≥ 1 et xi , yj ∈ X ⊂ N . Puisque l’on a x1 6= y1 , on peut supposer que x1 est

préfixe propre de y1 . Ainsi, on a
y1 = x1 w
pour un certain mot non vide w. On a alors que

x1 , y2 · · · yn , x1 w = y1 , wy2 · · · yn = x2 · · · xm

sont tous dans N. Puisque N est stable, il vient que w ∈ N . Ainsi on a

y 1 = x1 w ∈
/X

puisqu’un mot de X ne peut pas s’écrire comme le produit de deux mots non vides de N .
Or, on a supposé y1 ∈ X. L’ensemble X est donc un code.
22 CHAPITRE 1. CODES

Supposons maintenant que N est libre et soit X sa base.

Soient u, v, w ∈ A∗ et supposons que u, v, uw et wv appartiennent à N = X ∗ . Posons

u = x1 · · · xk , uw = y1 · · · yl , wv = xk+1 · · · xr , v = yl+1 · · · ys

avec xi , yj ∈ X. L’égalité u · wv = uw · v implique

x1 · · · xk · xk+1 · · · xr = y1 · · · yl · yl+1 · · · ys .

Puisque X est un code, il vient que r = s et yi = xi pour i = 1, . . . , s. De plus, on a l ≥ k

puisque |u| ≤ |uw|, donc

uw = y1 · · · yl
= x1 · · · xl
= uxk+1 · · · xl .

Ainsi, w = xk+1 · · · xl ∈ X ∗ = N . On en conclut donc que N est stable.

Définition 1.4.13. Soit M un monoïde.

Le sous-monoïde N de M est unitaire à droite dans M si pour tous u, v ∈ M

u, uv ∈ N ⇒ v ∈ N,

ce qui peut se réécrire

N −1 N ⊂ N. (1.14)
Le sous-monoïde N de M est unitaire à gauche dans M si pour tous u, v ∈ M

u, vu ∈ N ⇒ v ∈ N,

ce qui peut se réécrire

N N −1 ⊂ N. (1.15)
Le sous-monoïde N de M est biunitaire s’il est à la fois unitaire à gauche et à droite.

Dans la définition précédente, N étant un sous-monoïde, les inclusions 1.14 et 1.15 sont
en fait des égalités. Ainsi N est biunitaire si et seulement si N −1 N = N = N N −1 .
Remarque 1.4.14. Observons qu’un sous-monoïde unitaire à gauche (resp. à droite) est
en particulier stable.
Vu la remarque précédente, un sous-monoïde biunitaire de A∗ est en particulier stable.
Cependant, la réciproque n’est pas vraie. Le sous-monoïde engendré par un code préfixe
(resp. suffixe) qui n’est pas suffixe (resp. préfixe) est libre vu la Proposition 1.4.5 et donc
stable par la Proposition 1.4.12. La proposition suivante prouve que ce sous-monoïde est
unitaire à droite (resp. à gauche) mais pas à gauche (resp. à droite).
1.4. CODES ET SOUS-MONOÏDES LIBRES 23

Proposition 1.4.15. Un sous-monoïde M de A∗ est unitaire à droite (unitaire à gauche,

biunitaire) si et seulement si son ensemble minimal de générateurs est un code préfixe
(suffixe, bifixe).

Démonstration. Soit M ⊂ A∗ un sous-monoïde. Soit X = (M \{ε})\(M \{ε})2 son en-

semble minimal de générateurs.
Supposons que M est unitaire à droite et montrons que X est préfixe.
Soient x, xu ∈ X ⊂ M pour un certain u ∈ A∗ . Puisque M est unitaire à droite, il vient
que u ∈ M . Si u 6= ε, alors u ∈ M \{ε} et xu ∈ (M \{ε})2 , ce qui contredit le fait que
xu ∈ X. Donc u = ε et X est bien préfixe.
Inversement, supposons que X est préfixe. Soient u, v ∈ A∗ tels que u, uv ∈ M = X ∗ ,
montrons que v ∈ M . Posons

u = x1 · · · xn et uv = y1 · · · ym ,

avec xi , yj ∈ X. Il vient donc que x1 · · · xn v = y1 · · · ym . L’ensemble X étant préfixe, x1 ne

peut pas être préfixe propre de y1 et inversement. Nous avons donc x1 = y1 . En continuant
de proche en proche, on obtient finalement xi = yi pour i = 1, . . . , n. Il vient alors que

v = yn+1 · · · ym ∈ M,

ce qui montre que M est unitaire à droite.

Définition 1.4.16. Un sous-monoïde libre M de A∗ est maximal si M 6= A∗ et si M n’est

pas contenu strictement dans un autre sous-monoïde libre, excepté A∗ .

Proposition 1.4.17. Si M est un sous-monoïde libre maximal de A∗ , alors sa base X est

un code maximal.

Démonstration. Procédons par l’absurde en supposant qu’il existe un code Y sur A tel que
X (Y.
On a alors X ∗ ⊂ Y ∗ et X ∗ 6= Y ∗ . En effet, si X ∗ = Y ∗ , on aurait X = Y vu le Corollaire
1.4.8. Puisque M = X ∗ est un sous-monoïde libre maximal, on a forcément Y ∗ = A∗ et
par conséquent Y = A, toujours au vu du Corollaire 1.4.8. Il vient alors que X ( A.
Soit b ∈ A\X et posons Z = X ∪ {b2 }. L’ensemble Z est un code puisque X ne contient
que des lettres de A\{b} et qu’en lui ajoutant le mot b2 , l’ensemble Z forme un ensemble
bifixe différent de {ε}, qui est donc un code. On a

M ( Z ∗ ( A∗ .

/ X ∗ = M . La seconde est également

La première inclusion est stricte puisque b2 ∈ Z et b2 ∈
stricte puisque b ∈ A∗ mais b ∈/ Z ∗.
Ainsi, M n’est pas un sous-monoïde libre maximal, d’où la contradiction.
24 CHAPITRE 1. CODES

Remarque 1.4.18. La réciproque de cette proposition est fausse.

En effet, considérons les codes uniformes Ap avec p ≥ 1. On sait par la Proposition 1.2.23
que ces codes sont maximaux.
Or, si k, n ≥ 2, on a
(Akn )∗ ( (An )∗ ⊂ A∗
ce qui montre que (Akn )∗ n’est pas un sous-monoïde maximal.

Proposition 1.4.19. Soient G un groupe et H un sous-groupe de G. Soit ϕ : A∗ → G un

morphisme de monoïdes. L’ensemble M = ϕ−1 (H) est un sous-monoïde biunitaire.
Démonstration. Le fait que ϕ−1 (H) soit un sous-monoïde est évident puisque ϕ(ε) = 1 ∈
H, le morphisme envoie le neutre du monoïde libre sur le neutre du groupe et H en tant que
sous-groupe possède le neutre du groupe G. De plus, si m1 , m2 ∈ M , alors ϕ(m1 ), ϕ(m2 ) ∈
H. Par définition, on a
ϕ(m1 m2 ) = ϕ(m1 )ϕ(m2 ) ∈ H.
Ainsi, m1 m2 ∈ M .
Montrons à présent que M est biunitaire.
Soient p, pq ∈ M . Puisque M = ϕ−1 (H), il vient que ϕ(p), ϕ(pq) ∈ H. On a alors

(ϕ(p))−1 ϕ(pq) = (ϕ(p))−1 ϕ(p)ϕ(q) = ϕ(q).

Puisque H est un sous-groupe, on sait que (ϕ(p))−1 ∈ H, il vient alors que ϕ(q) ∈ H et
donc q ∈ M , ce qui montre que M est unitaire à droite.
On procède de manière analogue pour montrer que M est unitaire à gauche.

Remarque 1.4.20. La base de M = ϕ−1 (H) est donc un code bifixe.

Définition 1.4.21. Soient G un groupe et H un sous-groupe de G. On appelle code de
groupe la base X d’un sous-monoïde M = ϕ−1 (H), où ϕ : A∗ → G est un morphisme de
monoïdes surjectif.
Proposition 1.4.22. Un code de groupe est un code maximal.
Démonstration. Soient G un groupe, H un sous-groupe de G et X le code de groupe de
M = ϕ−1 (H). Si M = A∗ alors on a directement que X = A est maximal.
Sinon, prenons un mot w ∈ A∗ \M . Posons Y = X ∪ {w} et montrons que ce n’est pas un
code.
Posons m = ϕ(w) ∈ G. On sait que m admet un inverse dans G et ϕ étant surjectif on sait
qu’il existe un mot w0 ∈ A∗ tel que ϕ(w0 ) = m−1 . Les mots u = ww0 et v = w0 w sont dans
M puisque
ϕ(ww0 ) = ϕ(w)ϕ(w0 ) = mm−1 = 1 ∈ H
et
ϕ(w0 w) = ϕ(w0 )ϕ(w) = m−1 m = 1 ∈ H;
1.4. CODES ET SOUS-MONOÏDES LIBRES 25

Ainsi, le mot ww0 w = uw = wv ∈ Y ∗ possède deux factorisations distinctes 8 en mots de

Y.

1.4.1 Théorème du défaut

Le but de cette sous-section est de démontrer le Théorème du défaut, qui montre que
si X n’est pas un code, alors il existe un code Y , contenant moins d’éléments que X, qui
est tel que Y ∗ est un sous-monoïde libre contenant X.

Proposition 1.4.23. L’intersection d’une famille arbitraire de sous-monoïdes libres de A∗

est un sous-monoïde libre.

Démonstration. Soit (Mi )i∈I une famille de sous-monoïdes libres de A∗ et posons M =

∩i∈I Mi .
• M est un sous-monoïde :
Chaque Mi est un sous-monoïde, donc par définition, ε ∈ Mi ∀i ∈ I. Ainsi, ε ∈ M .
Soient m1 , m2 ∈ M . On a en particulier m1 , m2 ∈ Mi ∀i ∈ I. Par définition on a
m1 m2 ∈ Mi ∀i ∈ I. Par conséquent, m1 m2 ∈ M .
• M est libre :
Montrons que M est stable. Soient u, v, uw, wv ∈ M . Par définition, ces quatre mots
sont dans chacun des Mi . Puisque les Mi sont libres, ils sont stables donc on a bien
w ∈ Mi ∀i ∈ I. Ainsi, w ∈ M .

Soit X ⊂ A∗ . Comme nous venons de le voir, l’intersection de tous les sous-monoïdes

libres de A∗ contenant X est encore un sous-monoïde. Il s’agit du plus petit 9 sous-monoïde
libre de A∗ contenant X. Nous l’appellons l’enveloppe libre de X.

Remarque 1.4.24. Si X ∗ est un sous-monoïde libre, alors il coïncide avec son enveloppe
libre. Cependant, si X ∗ n’est pas libre, alors il est inclus strictement dans son enveloppe
libre.

Lemme 1.4.25. Soient X ⊂ A∗ et Y la base de l’enveloppe libre de X. Alors tout élément

de Y apparait comme premier (resp. dernier) facteur dans la factorisation d’un mot x ∈ X
en mots de Y , i.e.
Y ⊂ X(Y ∗ )−1 ∩ (Y ∗ )−1 X
où X(Y ∗ )−1 = {w ∈ A∗ |wY ∗ ∩ X 6= ∅} et (Y ∗ )−1 X = {w ∈ A∗ |Y ∗ w ∩ X 6= ∅}.
/ X ∗.
8. u = u1 · · · un avec ui ∈ X et on a u1 6= w puisque w ∈
9. Pour l’inclusion.
26 CHAPITRE 1. CODES

Démonstration. Procédons par l’absurde et supposons qu’il existe y ∈ Y tel que

yY ∗ ∩ X = ∅,

i.e. y ∈ Y \X(Y ∗ )−1 . Montrons que Y ∗ n’est pas le plus petit sous-monoïde libre contenant
X.
Posons Z = {zy i |z ∈ Y \y, i ≥ 0} = (Y \y)y ∗ . Puisque X ⊂ Y ∗ , tout x ∈ X s’écrit :
x = y1 y2 · · · yn avec yi ∈ Y . Comme yY ∗ ∩ X = ∅, on a forcément que y1 6= y. Il vient donc
que X ⊂ {ε} ∪ (Y \y)Y ∗ . De plus, on a 10

{ε} ∪ (Y \y)Y ∗ ⊂ Z ∗

/ Z ∗ . Il vient alors X ⊂ Z ∗ ( Y ∗ .
et y ∈
De plus, Z ∗ est libre : en effet tout mot x ∈ Z ∗ possède une factorisation unique de la
forme
x = x1 x2 · · · xn
avec x1 , . . . , xn ∈ Y et x1 6= y, puisque Y est un code. Par conséquent le mot x peut se
réécrire de manière unique de la façon suivante :

x = z1 y p1 z2 y p2 · · · zr y pr

avec zi ∈ Y \y et pi ≥ 0. Ainsi, Z est bien un code.

Théorème 1.4.26 (Théorème du défaut). Soit X ⊂ A∗ et soit Y la base de l’enveloppe

libre de X. Si X n’est pas un code, alors

Card(Y ) < Card(X).

Démonstration. Considérons deux cas :

— Cas 1 : Supposons que ε ∈
/ X.
Soit α : X → Y une application définie par

α(x) = y si x ∈ yY ∗ ,

i.e. α associe à x ∈ X le premier facteur de son unique factorisation en mots de Y .

Ainsi, l’application est bien et partout définie puisque Y est un code et X ⊂ Y ∗ . Vu
le lemme précédent, l’application α est surjective. Par contre, elle n’est pas injective.
En effet, puisque X n’est pas un code, il existe w ∈ X ∗ possédant deux factorisations
distinctes
w = x1 · · · xn = x01 · · · x0m
10. Effectivement, soit w ∈ (Y \y)Y ∗ , on a w = y1 · · · yn , avec y1 6= y et yi ∈ Y ∀i. En coupant avant
chaque yi 6= y, on obtient des blocs de (Y \y)y ∗ .
1.4. CODES ET SOUS-MONOÏDES LIBRES 27

avec xi , x0j ∈ X ⊂ Y ∗ et x1 6= x01 . Chacun des xi , x0j se décompose en mots de Y de

manière unique. Ainsi,
0 0 0 0
x1 · · · xn = y1,1 · · · y1,n1 · · · yn,1 · · · yn,nn = y1,1 · · · y1,m 1
· · · ym,1 · · · ym,m m
= x01 · · · x0m ,
0 0
avec yi,j , yk,l ∈ Y . Vu que Y est un code, on a y1,1 = y1,1 . Il vient alors α(x1 ) = α(x01 ).
Nous avons donc bien Card(Y ) < Card(X).
— Cas 2 : Si ε ∈ X.
Dans ce cas, X et X 0 = X\{ε} ont la même enveloppe libre Y ∗ .
• Si X 0 est un code, alors le sous-monoïde engendré par X 0 coïncide avec son
enveloppe libre , i.e. (X 0 )∗ = Y ∗ . Vu le Corollaire 1.4.8, on a X 0 = Y et il vient

Card(Y ) < Card(X).

• Si X 0 n’est pas un code, il suffit d’appliquer le Cas 1 à X 0 . Il vient donc que

Card(Y ) < Card(X 0 ) < Card(X).

Corollaire 1.4.27. L’ensemble X = {x1 , x2 }, x1 6= x2 , est un code si et seulement si x1

et x2 ne sont pas des puissances d’un même mot.

Démonstration. Supposons que X est un code et procédons par l’absurde en supposant

que x1 , x2 sont des puissances d’un même mot. Soit w ∈ A∗ tel que

x1 = wr , x2 = ws ,

avec r, s ∈ N. Le mot x = x1 x2 ∈ X ∗ possède deux factorisations distinctes puisque

x = x1 x2 = w r w s = w s w r = x2 x1 ,

ce qui contredit le fait que X est un code.

Supposons maintenant que X n’est pas un code. Soit Y la base de l’enveloppe libre de
X. Par le théorème précédent, on sait que Card(Y ) < Card(X). Or, x1 , x2 ∈ Y ∗ , i.e. x1 , x2
sont des concaténations de mots de Y . Étant donné qu’il n’y a qu’un élément dans Y , cela
entraine que x1 et x2 sont des puissances d’un même mot.
28 CHAPITRE 1. CODES
Chapitre 2

Description quantitative des codes

Dans ce chapitre, nous allons essentiellement introduire des outils permettant de « me-
surer » la taille d’ensembles de mots.
Les lois de Bernoulli constituent le premier de ces outils. Dans le Théorème 2.1.15 nous
verrons, par exemple, que les codes ne peuvent pas contenir « trop » de « petits » mots.
Avant d’y parvenir, nous introduirons des lois de probabilité appliquées aux ensembles de
mots et présenterons certaines de leurs propriétés. D’autres résultats importants seront
également démontrés, comme le Théorème de Kraft-McMillan. Par ailleurs, de nombreux
résultats de cette section seront utilisés dans des preuves ultérieures.
Le second outil développé dans ce chapitre est la notion de densité d’un ensemble de
mots. Tout comme la densité topologique, à laquelle elle est liée, cette notion nous permet
d’identifier les ensembles contenant « beaucoup » d’éléments. Ceci nous permettra d’étudier
la maximalité des codes.

2.1 Mesure des codes

Les lois de Bernoulli nous permettront d’établir des conditions nécessaires pour qu’un
ensemble de mots soit un code. De plus, elles nous permettront de mesurer la taille des
codes grâce notamment au Théorème 2.1.15. Les résultats de cette section sont, par ailleurs,
également très utiles pour les sections suivantes.

2.1.1 Lois de probabilité

Définition 2.1.1. Soit A un alphabet. Une application π : A∗ → [0; 1] telle que

π(ε) = 1 (2.1)

et X
π(wa) = π(w) ∀ w ∈ A∗ (2.2)
a∈A

29
30 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

est appelée une loi de probabilité sur A∗ . La condition 2.2 est appelée la condition de
cohérence.
Une loi de probabilité est dite positive si elle est non nulle, i.e. si π(w) > 0 pour tout
w ∈ A∗ .
X
Proposition 2.1.2. La condition de cohérence implique que π(x) = 1.
x∈An

Démonstration. Procédons par récurrence sur n ≥ 0.

• Cas de base : n = 0 X
On a A0 = {ε}, ainsi π(x) = π(ε) = 1.
x∈A0
• Induction : Supposons que la propriété est vraie pour j < n et montrons-la pour n.
On a
X X X
π(x) = π(ya) (2.3)
x∈An y∈An−1 a∈A
X
= π(y) (2.4)
y∈An−1

= 1, (2.5)
où 2.4 est obtenu grâce à la condition de cohérence et 2.5 grâce à l’hypothèse de
récurrence.

Étant donné une loi de probabilité π sur A∗ , on pose pour chaque X ⊂ A∗

X
π(X) = π(x)
x∈X

La valeur π(X) peut être positive ou infinie.

Remarque 2.1.3. Pour une famille (Xi )i≥0 de sous-ensembles de A∗ , on a
!
[ X
π Xi ≤ π(Xi ).
i≥0 i≥0

En effet, si les ensembles Xi sont disjoints deux à deux, on a

!
[ X
π Xi = π(w) (2.6)
S
i≥0 w∈ i≥0 Xi
XX
= π(w) (2.7)
i≥0 w∈Xi
X
= π(Xi ). (2.8)
i≥0
2.1. MESURE DES CODES 31

Dans le cas où les ensembles ne sont pas disjoints, il est clair que nous avons l’inégalité
souhaitée puisque certains éléments sont repris plusieurs fois à l’égalité 2.7.

Définition 2.1.4. La série génératrice de X ⊂ A∗ est la série

X
fX (t) = un tn
n≥0

où un = Card(X ∩ An ).

Définition 2.1.5. La série génératrice des probabilités d’un ensemble X ⊂ A∗ est la série
X
FX (t) = π(X ∩ An )tn .
n≥0

En particulier, on a
X
FX (1) = π(X ∩ An ) (2.9)
n≥0
X X
= π(w) (2.10)
n≥0 w∈X∩An
X
= π(w) (2.11)
w∈X
= π(X). (2.12)

Remarque 2.1.6. Grâce à la Proposition 2.1.2, on sait que π(An ) = 1. Ainsi on a π(X ∩
+∞
X
n n n n
A ) ≤ 1 et par conséquent |π(X ∩ A )t | ≤ |t |. Or on sait que tn converge sur ] − 1; 1[.
X n=0
n n
On en déduit alors que FX (t) = π(X ∩ A )t converge au moins sur ] − 1; 1[, i.e. le
n≥0
rayon de convergence de la série FX (t) est au moins 1.

2.1.2 Lois de Bernoulli

Intéressons-nous maintenant à une classe de lois de probabilité en particulier.

Définition 2.1.7. Une loi de Bernoulli est un morphisme π de A∗ dans [0, 1] muni de la
multiplication tel que X
π(a) = 1.
a∈A

Proposition 2.1.8. Une loi de Bernoulli est une loi de probabilité.

32 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Démonstration. Soit π une loi de Bernoulli sur A∗ . Étant donné que π est un morphisme,
nous avons, d’une part, π(ε) = 1 et, d’autre part, soit w ∈ A∗ , on a
X X
π(wa) = π(w)π(a)
a∈A a∈A
X
= π(w) π(a)
a∈A
| {z }
=1
= π(w)

1
Définition 2.1.9. La loi uniforme de Bernoulli sur A est définie par π(a) = pour
Card A
tout a ∈ A.
Dans le cas d’une loi uniforme de Bernoulli, la série génératrice des probabilités est liée
à la série génératrice par la relation suivante :

fX (t) = FX (kt), (2.13)

où k = Card A.
En effet, dans ce cas on a
X
k n π(X ∩ An ) = k n π(w) (2.14)
w∈X∩An
X 1
= kn (2.15)
w∈X∩An
kn
X
= 1 (2.16)
w∈X∩An
= Card(X ∩ An ). (2.17)

L’égalité 2.15 provient du fait que si w ∈ X ∩ An , alors w = w1 · · · wn avec wi ∈ A. Ainsi

1
π(w) = π(w1 ) · · · π(wn ). Puisque π est uniforme chaque π(wi ) = .
k
Par ailleurs, puisque π(X) = FX (1), il vient
  X
1
π(X) = fX = un k −n . (2.18)
k n≥1

où un = Card(X ∩ An ).
Proposition 2.1.10. Soient X, Y ⊂ A∗ et π une loi de Bernoulli sur A∗ . On a

π(XY ) ≤ π(X)π(Y ).

En particulier, on a l’égalité si le produit XY est non ambigu.

2.1. MESURE DES CODES 33

Démonstration. On a
!
[ [
π(XY ) = π {xy}
x∈X y∈Y
XX
≤ π(xy)
x∈X y∈Y

= π(X)π(Y ).
[
En particulier, si le produit XY est non ambigu, alors l’union {xy} est disjointe, d’où
x∈X
y∈Y
l’égalité.

2.1.3 Codes et lois de Bernoulli

De manière intuitive, si nous cherchons à construire un code sur un alphabet donné,
nous nous rendons vite compte qu’il ne faut pas lui ajouter « trop » de « trop petits » mots.
Grâce aux lois de Bernoulli, nous allons pouvoir « quantifier » ces notions de « trop » et
« trop petits ». Cette quantification sera réalisée au moyen des Théorèmes 2.1.15 et 2.1.23.

Lemme 2.1.11. Soit π une loi de Bernoulli sur A∗ . Pour des ensembles X, Y ⊂ A+ , on a
1. FX∪Y (t) = FX (t) + FY (t) si X ∩ Y 6= ∅.
2. FXY (t) = FX (t)FY (t) si le produit XY est non ambigu.

Démonstration. 1. On a
X
FX∪Y (t) = π((X ∪ Y ) ∩ An )tn (2.19)
n≥0
X
= π((X ∩ An ) ∪ (Y ∩ An ))tn (2.20)
n≥0
X
= (π(X ∩ An ) + π(Y ∩ An ))tn (2.21)
n≥0
X X
= π(X ∩ An )tn + π(Y ∩ An )tn (2.22)
n≥0 n≥0

= FX (t) + FY (t), (2.23)

l’égalité 2.21 découlant de la Remarque 2.1.3.

2. Pour tout n, on a [
XY ∩ An = (X ∩ Ai )(Y ∩ Aj )
i+j=n
34 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Puisque le produit XY est non ambigu, cette union est disjointe.

En effet supposons le contraire : soit w ∈ (X ∩ Ai )(Y ∩ Aj ) ∩ (X ∩ Ak )(Y ∩ Al ) avec
i 6= k, j 6= l. Il vient alors

w = x1 · · · xi y1 · · · yj = x01 · · · x0k y10 · · · yl0 ,

avec x1 · · · xi , x01 · · · x0k ∈ X et y1 · · · yj , y10 · · · yl0 ∈ Y tels que x1 · · · xi 6= x01 · · · x0k et

y1 · · · yj 6= y10 · · · yl0 , ce qui contredit le fait que le produit XY est non ambigu.
On obtient alors
!
[
π(XY ∩ An ) = π (X ∩ Ai )(Y ∩ Aj )
i+j=n
X
π (X ∩ Ai )(Y ∩ Aj ) .


=
i+j=n

Ensuite, π étant un morphisme, il vient :

X
π (X ∩ Ai )(Y ∩ Aj ) =


π(w)
w∈(X∩Ai )(Y ∩Aj )
X
= π(x)π(y)
x∈X∩Ai
y∈X∩Aj
X X
= π(x) π(y)
x∈X∩Ai y∈X∩Aj

= π(X ∩ Ai )π(Y ∩ Aj ).

Ainsi, d’une part nous avons

X
FXY (t) = π(XY ∩ An )tn
n≥0
X X
= (π(X ∩ Ai )π(Y ∩ Aj ))tn .
n≥0 i+j=n

D’autre part, nous avons

X X
FX (t)FY (t) = π(X ∩ An )tn π(Y ∩ An )tn
n≥0 n≥0
!
X X
= π(X ∩ Ai )π(X ∩ Aj ) tn .
n≥0 i+j=n

L’égalité de l’énoncé est ainsi démontrée.

2.1. MESURE DES CODES 35

Remarque 2.1.12. Si chaque mot de X1 · · · Xm possède une factorisation unique en mots

de X1 , . . . , Xm , alors on a 1
FX1 ···Xm (t) = FX1 (t) · · · FXm (t).
Proposition 2.1.13. Soit X ⊂ A+ un code et soit π une loi de Bernoulli sur A∗ . Alors
on a
1
FX ∗ (t) = .
1 − FX (t)
Démonstration. Puisque FX (0) = 0, nous savons que le terme indépendant de la série
1−FX (t) est 1, qui est inversible. Ainsi, vu la Proposition 1.1.1, nous savons que la série 1−
X 1
FX (t) est inversible. Grâce à la Proposition 1.1.2, il vient (FX (t))∗ = FX (t)n = .
n≥0
1 − F X (t)
L’ensemble X étant un code, les produits X n sont non ambigus. En effet, tout mot de X n
possède une factorisation unique en mots de X et par la Remarque 2.1.12 il vient que
(FX (t))n = FX n (t).
De plus les ensembles X n sont deux-à-deux disjoints. En effet, s’il existait un mot w ∈
X m ∩ X n , alors w = x1 · · · xn = y1 · · · ym avec xi , yj ∈ X, ce qui contredit le fait que X est
un code. Ainsi il vient
! !
X [
FSn≥0 X n (t) = π X n ∩ A m tm
m≥0 n≥0
!
X [
= π (X n ∩ Am ) tm
m≥0 n≥0
XX
= π(X n ∩ Am )tm
m≥0 n≥0
X
= FX n (t).
n≥0

Finalement, on a donc
FX ∗ (t) = FSn≥0 X n (t)
X
= FX n (t)
n≥0
X
= (FX (t))n
n≥0
1
= .
1 − FX (t)

1. On peut le démontrer grâce à un raisonnement analogue à celui du point 2 du lemme précédent.

36 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Dans le cas des lois uniformes de Bernoulli, nous avons le corollaire suivant :
Corollaire 2.1.14. Soit X un code sur un alphabet fini A. On a alors
1
fX ∗ (t) = .
1 − fX (t)
Vu la définition des lois de Bernoulli, les mots « plus longs » auront une probabilité
plus petite que les mots « plus courts ». La condition π(X) ≤ 1 exprime alors le fait que
X ne contienne « pas trop » de petits mots. Cela peut se voir encore plus facilement dans
le cas de la loi uniforme de Bernoulli vu la relation 2.18.
Théorème 2.1.15. Si X est un code sur A, alors π(X) ≤ 1 pour toute loi de Bernoulli π
sur A∗ .

XSupposons d’abord que X est fini.

Démonstration.
Alors π(X) = π(x) est également fini. Procédons par l’absurde et supposons que π(X) >
x∈X
1.
On sait alors que FX (1) > 1. Puisque FX (0) = 0 et que FX (t) est continu sur [0; 1], il existe
un nombre r < 1 tel que
FX (r) = 1.
1
Puisque X est un code, on a FX ∗ (t) = . Ainsi, FX ∗ (t) diverge si t = r. On en tire
1 − FX (t)
alors que le rayon de convergence R de la série FX ∗ (t) est tel que R ≤ r < 1. En effet, si le
rayon de convergence R était tel que R > r, la série convergerait en r. Or, vu la Remarque
2.1.6, le rayon de convergence doit valoir au moins 1, d’où la contradiction.
Considérons maintenant le cas où X est infini.
Nous savons que A∗ est dénombrable, ce qui implique que X l’est également. Nous pouvons
alors réécrire l’ensemble X comme étant {x0 , x1 , x2 , x3 . . .}. Il vient alors que
X
π(X) = π(x) (2.24)
x∈X
X
= π(xn ) (2.25)
n≥0
N
X
= sup π(xn ). (2.26)
N ∈N n=0

N
X
Vu ce qui précède, nous savons que π(xn ) = π({x0 , . . . , xn }) ≤ 1. Il en va donc de même
n=0
pour sa borne supérieure. Ceci conclut la preuve.

En appliquant le théorème précédent au cas des lois uniformes de Bernoulli, nous ob-
tenons le corollaire suivant :
2.1. MESURE DES CODES 37

Corollaire 2.1.16. Soit X un code sur un alphabet A de k lettres. On a alors

X
k −|x| ≤ 1. (2.27)
x∈X

Démonstration.
X Soit π la loi uniforme de Bernoulli sur A. Puisque X est un code, on a
π(X) = π(x) ≤ 1.
x∈X
1
Or π(x) = π(x1 ) · · · π(x|x| ), avec xi ∈ A. La loi étant uniforme chacun des π(xi ) vaut .
k
1
Ainsi π(x) = |x| , d’où la conclusion.
k

Remarque 2.1.17. L’inégalité 2.27 peut se réécrire

X
Card(X ∩ An )k −n ≤ 1. (2.28)
n≥1

Pour montrer qu’un ensemble X n’est pas un code, il suffit de trouver une loi de
Bernoulli telle que π(X) > 1.
Exemple 2.1.18. Soient A = {a, b} et X = {a, ab, ba, baa}. Soit π la loi uniforme de
Bernoulli sur A. Il vient
X
π(X) = π(x)
x∈X
= π(a) + π(ab) + π(ba) + π(bba)
1 2 1
= + +
2 4 8
9
= > 1.
8
On a donc trouvé une loi de Bernoulli qui est telle que π(X) > 1, par conséquent l’ensemble
X n’est pas un code.
La réciproque du Théorème 2.1.15 n’est pas vraie. Comme le montre l’exemple suivant
il est possible qu’un ensemble X qui n’est pas un code soit tel que π(X) ≤ 1 pour toute
loi de Bernoulli π.
Exemple 2.1.19. Considérons l’ensemble X = {ab, aba, aab} sur l’alphabet A = {a, b}.
Étant donné que le mot w = aba · ab = ab · aab possède deux factorisations distinctes
en mots de X, il est clair que X n’est pas un code. Cependant, n’importe quelle loi de
Bernoulli π sur A∗ nous donne π(X) ≤ 1.
En effet, posons p = π(a) et q = π(b). On a alors
π(X) = π(ab) + π(aba) + π(aab)
= pq + p2 q + p2 q
= pq + 2p2 q
38 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

1 4 1 8
Remarquons que l’on a 2 pq ≤ et p2 q ≤ . Il vient donc que π(X) ≤ + < 1.
4 27 4 27

Jusqu’à présent, nous avons démontré quelques conditions nécessaires pour être un
code, la proposition suivante va, quant à elle, nous fournir une condition suffisante.
Proposition 2.1.20. Soient X ⊂ A+ et π une loi de Bernoulli sur A∗ .
1. Si X est un code, alors
π(X n ) = π(X)n ∀ n ≥ 0.
2. Si π est positif, si π(X) est fini et si π(X n ) = π(X)n pour tout n ≥ 1, alors X est
un code.
Démonstration. 1. Si X est un code, les mots de X n possèdent une factorisation unique
en mots de X. Ainsi vu la Remarque 2.1.12, nous avons en particulier π(X n ) =
FX n (1) = FX (1) · · · FX (1) = (π(X))n .
2. Procédons par l’absurde et supposons que X n’est pas un code. Il existe donc un mot
w ∈ X ∗ , supposé de longueur minimale, tel que
w = x1 x2 · · · xn = y1 y2 · · · ym
avec n, m ≥ 1, xi , yj ∈ X et x1 6= y1 . Le mot u = ww possède alors deux factorisations
de k = m + n facteurs
u = x1 x2 · · · xn y1 y2 · · · ym = y1 y2 · · · ym x1 x2 · · · xn
On a donc
!k
X
(π(X))k = π(x)
x∈X
! ! !
X X X
= π(z1 ) π(z2 ) · · · π(zk )
z1 ∈X z2 ∈X zk ∈X
X X X
= ··· π(z1 z2 · · · zk )
z1 ∈X z2 ∈X zk ∈X

et X
π(X k ) = π(v).
v∈X k

Il vient alors que

(π(X))k ≥ π(X k ) + π(u).
Or, par hypothèse (π(X))k = π(X k ), ainsi π(u) = 0, ce qui contredit le fait que π
est positif.

1 4
2. Il suffit d’étudier le signe des polynômes p(1 − p) − 4 et p2 (1 − p) − 27 pour s’en convaincre.
2.1. MESURE DES CODES 39

Les lois de Bernoulli nous permettent également de trouver des codes maximaux.

Proposition 2.1.21. Soit X un code sur A. S’il existe une loi de Bernoulli positive π sur
A∗ telle que π(X) = 1, alors le code X est maximal.

Démonstration. Procédons par l’absurde et supposons que X n’est pas maximal.

Il existe un certain mot w ∈/ X de A∗ tel que Y = X ∪ {w} est un code. Par le Théorème
2.1.15, on a π(Y ) ≤ 1. Or,
X X
π(Y ) = π(y) = π(x) + π(w) = π(X) + π(w) = 1 + π(w).
y∈Y x∈X

Il s’ensuit alors que π(w) = 0, ce qui contredit le fait que π est positif.

Exemple 2.1.22. Soient A = {a, b} et X = {a, ba, bb} un ensemble préfixe. Soit π une
distribution de Bernoulli sur A∗ telle que π(a) = p et π(b) = q. On a
X
π(X) = π(x)
x∈X
= π(a) + π(ba) + π(bb)
= π(a) + π(b)π(a) + π(b)π(b)
= p + pq + q 2
= p + q. (p + q)
| {z }
=1
=1

L’ensemble est donc un code maximal.

Comme montré à l’Exemple 2.1.19, la réciproque du Théorème 2.1.15 (et donc du

Corollaire 2.1.16) n’est
P pas vraie. En particulier, si X ⊂ A∗ et si on pose un = Card(X ∩
n −n
A ), la condition n≥1 un k ≤ 1 n’implique pas que X soit un code. Par contre, le
théorème suivant montre que cette condition implique l’existence d’un code X 0 tel que
un = Card(X 0 ∩ An ).

Théorème 2.1.23 (Kraft-McMillan). Étant donné une suite (un )n≥1 de naturels, il existe
un code X sur un alphabet A de k symboles tel que un = Card(X ∩ An ) si et seulement si
X
un k −n ≤ 1.
n≥1

De plus, le code X peut être choisi préfixe.

40 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Démonstration. La condition est nécessaire vu le Corollaire 2.1.16. En effet, si π est la loi

uniforme de Bernoulli sur A, on a
X X
un k −n = Card(X ∩ An )k −n
n≥1 n≥1
X
= k n π(X ∩ An )k −n
n≥1
X X
= π(w)
n≥1 w∈X∩An
X
= k −|w| .
w∈X
X X
D’autre part, observons tout d’abord que un k −n ≤ 1 entraine ui k −i ≤ 1 et par
n≥1 1≤i≤n
X
n−i n
conséquent ui k ≤k .
1≤i≤n
Nous allons construire, par récurrence sur n ≥ 1, une suite X1 , X2 , X3 , . . . de codes préfixes
qui seront tels que
∀n Xn ⊂ Xn+1 (2.29)
i
∀n ∀1 ≤ i ≤ n, Card(Xn ∩ A ) = ui (2.30)
∀n ∀i > n, Card(Xn ∩ Ai ) = 0. (2.31)
• Cas de base : n = 1
On a u1 ≤ k. Il suffit de choisir u1 lettres de A pour former X1 . Alors X1 est bien un
code préfixe tel que Card(X1 ∩ A) = u1 .
• Induction : Supposons avoir construit des codes préfixes X1 , . . . , Xn vérifiant les
conditions 2.29, 2.30 et 2.31, et construisons Xn+1 .
L’ensemble des mots de A∗ de longueur n + 1 et qui ont un préfixe dans Xn s’écrit
n
[
(Xn ∩ Ai )An+1−i .
i=1

Cette union est disjointe car Xn est un code préfixe.

Le nombre de mots de longueur n + 1 ayant un préfixe dans Xn est donc
n
X
Card (Xn ∩ Ai )An+1−i


S=
i=1
n
X
= Card(Xn ∩ Ai ) Card(An+1−i )
i=1
Xn
= ui k n+1−i .
i=1
2.2. ENSEMBLES COMPLETS 41

Par hypothèse,
n+1
X
ui k n+1−i ≤ k n+1
i=1
⇔ S + un+1 ≤ k n+1 .

Il y a donc au moins un+1 mots de longueur n + 1 qui n’ont pas de préfixe dans Xn .
Soit Y un ensemble de un+1 mots de longueur n + 1 qui n’ont pas de préfixe dans
Xn . Posons
Xn+1 = Xn ∪ Y.
L’ensemble Xn+1 est un code préfixe tel que ∀ 1 ≤ i ≤ n + 1, Card(Xn+1 ∩ Ai ) = ui .
[
Posons X = Xn .
n≥1
— L’ensemble X est préfixe :
Si v, w ∈ X, il existe n, m tels que v ∈ Xn et w ∈ Xm . Supposons par exemple
que m ≥ n, alors v, w ∈ Xm qui est un code préfixe. Ainsi v, w ne peuvent pas être
préfixes propres l’un de l’autre.

— On a Card(X ∩ An ) = un :
En effet, nous avons Card(X ∩ An ) = Card(Xn ∩ An ) = un .
Ainsi l’ensemble X satisfait aux conditions de l’énoncé.

2.2 Ensembles complets

Nous savons, jusqu’à présent, que tout sous-ensemble d’un code est encore un code. Il
peut donc être intéressant d’étudier les codes maximaux. Par ailleurs, dans cette section,
nous définirons les ensembles complets, possédant la propriété contraire : tout ensemble
contenant un ensemble complet est complet. Nous verrons alors dans le Théorème 2.2.11 que
les codes maximaux se trouvent à l’intersection entre les codes et les ensembles complets.
Définition 2.2.1. Soient M un monoïde et P un sous-ensemble de M . Un élément m ∈ M
est dit complétable dans P s’il existe des éléments u, v ∈ M tels que umv ∈ P .
Cette définition est équivalente au fait que P rencontre l’idéal M mM :

M mM ∩ P 6= ∅.

L’ensemble des éléments complétables dans P est F (P ) = M −1 P M −1 .

Un élément qui n’est pas complétable dans P est dit incomplétable dans P .
Définition 2.2.2. Un sous-ensemble P d’un monoïde M est dense dans M si tous les
éléments de M sont complétables dans P , i.e. F (P ) = M .
42 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Remarque 2.2.3. Cette définition est équivalente au fait que P rencontre tous les idéaux
de M . En effet, P est dense dans M si et seulement si pour tout m ∈ M , on a M mM ∩P 6= ∅.
Soit I un idéal de M . Par définition, on a M IM ⊂ I. Soit i ∈ I, on a M iM ⊂ I. En
particulier ∅ =
6 M iM ∩ P ⊂ I ∩ P .
La remarque précédente nous permet de justifier l’utilisation du terme « dense ». En
effet, nous pouvons vérifier que T = {∅} ∪ {I | I idéal de M } est une topologie sur M .
Puisqu’un ensemble est dense, au sens topologique, si et seulement s’il rencontre tout ouvert
non vide, la notion de densité définie ci-dessus est équivalente à celle de densité topologique.
Intuitivement, un ensemble dense contient « beaucoup » d’éléments.

Soient P, Q deux sous-ensembles d’un monoïde M tels que P ⊂ Q. Si P est dense alors
Q l’est aussi.
Remarque 2.2.4. Dans le cas du monoïde libre A∗ , X ⊂ A∗ est dense si et seulement
tout mot de A∗ est facteur d’un mot de X.
Définition 2.2.5. Un sous-ensemble P d’un monoïde M est complet dans M si le sous-
monoïde engendré par P est dense, i.e. F (P ∗ ) = M .
De manière équivalente, P est complet si et seulement si, pour tout élément m ∈ M ,

M mM ∩ P ∗ 6= ∅.

Nous avons trivialement le résultat suivant.

Proposition 2.2.6. 1. Tout ensemble dense est complet.
2. Tout ensemble contenant un ensemble complet est encore complet.
Définition 2.2.7. Un mot w ∈ A+ est dit sans bords si aucun préfixe propre non vide de
w n’est un suffixe de w.
En d’autres termes, w est sans bords si et seulement si w ∈ uA+ ∩ A+ u implique u = ε.
Proposition 2.2.8. Si un mot w ∈ A∗ est sans bords alors wA∗ ∩ A∗ w = wA∗ w ∪ {w}.
Démonstration. Procédons par double inclusion.
⊂ : Si u ∈ wA∗ ∩ A∗ w, alors u = wv = v 0 w pour des mots v, v 0 ∈ A∗ .
• Si v = v 0 = ε alors u ∈ {w}.
• Sinon, |v|, |v 0 | ≥ |w|. En effet, si |v|, |v 0 | < |w|,
v0 w

w v

alors il existe un suffixe de w qui est également préfixe propre de w, ce qui

contredit le fait que w est sans bords. Ainsi, v = tw et v 0 = wt0 pour des mots
t, t0 ∈ A∗ . Il vient alors que u = wv = wtw ∈ wA∗ w.
2.2. ENSEMBLES COMPLETS 43

⊃ : Soit u ∈ wA∗ w ∪ {w}.

• Si u ∈ {w} alors u ∈ wA∗ ∩ A∗ w.
• Si u ∈ wA∗ w, alors il existe v ∈ A∗ tel que u = wvw = wv 0 = v 00 w avec
v 0 = vw ∈ A∗ et v 00 = wv ∈ A∗ . Ainsi, u ∈ wA∗ ∩ A∗ w.

Lemme 2.2.9. Soit A un alphabet d’au moins deux lettres. Pour tout mot u ∈ A+ , il existe
un mot v ∈ A+ tel que uv est sans bords.
Démonstration. Soit a ∈ A la première lettre de u et soit b ∈ A\{a}. Montrons que le mot
w = uab|u| est sans bords, autrement dit, le mot v = ab|u| convient.
Procédons par l’absurde et supposons qu’il existe un mot t qui est préfixe propre non vide
et suffixe de w. On a alors nécessairement |t| > |u|. Ainsi, t étant suffixe, on a t = sab|u|
pour un certain s ∈ A∗ et puisqu’il est également préfixe, on a t = uab|s| . Il vient donc
|s| = |u|. On obtient finalement t = w, ce qui contredit le fait que t est préfixe propre de
w.

Proposition 2.2.10. Soit X ⊂ A+ un code maximal. Pour tout mot w ∈ A∗ on a

X ∗ wA∗ ∩ X ∗ 6= ∅. (2.32)
Démonstration. Traitons tout d’abord le cas où Card A = 1. Supposons A = {a}, alors
Card X = 1 avec X = {an } pour un n fixé. Soit w ∈ A∗ , alors w = am pour un certain
m. Alors le mot am akn−m appartient à X ∗ wA∗ ∩ X ∗ pour un k tel que kn > m. Ensuite,
traitons le cas où w = ε. Nous avons directement w ∈ X ∗ wA∗ ∩ X ∗ . Maintenant, nous
pouvons donc supposer que Card A ≥ 2 et w ∈ A+ .
Par le lemme précédent, il existe un mot w0 ∈ A+ tel que y = ww0 est sans bords. Si
y ∈ X, alors il vient directement que y = ww0 ∈ X ∗ wA∗ ∩ X ∗ . Supposons donc que y ∈
/X
et posons Y = X ∪ {y}. Nous allons alors montrer que X ∗ yA∗ ∩ X ∗ 6= ∅. L’ensemble Y ne
peut pas être un code vu la maximalité de X. Il existe donc un mot t ∈ Y ∗ , supposé de
longueur minimale, qui possède deux factorisations en mots de Y :
t = x 1 x2 · · · xn
= y1 y2 · · · ym ,
avec m, n ≥ 1, xi , yj ∈ Y et x1 6= y1 . L’ensemble X étant un code, il y a forcément un des
xi , yj qui est égal à y. Considérons l’occurence la plus à gauche de y parmi les xi , yj , on
peut supposer xk = y. Autrement dit, le mot x1 · · · xk−1 est le plus petit préfixe de t qui ne
contient pas y. On a donc x1 , . . . , xk−1 ∈ X. Posons l le plus petit indice tel que x1 · · · xk
est préfixe de y1 · · · yl . Posons
z = x1 x2 · · · xk−1 xk u = y1 y2 · · · yl ,
| {z } |{z}
∈X ∗ =y

pour u ∈ A . On a donc z ∈ X yA . Montrons que z ∈ X ∗ en montrant que y1 , . . . , yl ∈ X.

∗ ∗ ∗

Soit p le plus petit indice tel que x1 x2 · · · xk−1 soit préfixe de y1 y2 · · · yp .

44 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

• Cas 1 : p = l
Si yl = yp , alors x1 · · · xk−1 est préfixe de y1 · · · yl , ce qui implique que y1 · · · yl ∈ X ∗ .
En effet, sinon il y a un des y1 , . . . , yl qui est égal à y ce qui contredit le fait que xk
est l’occurence la plus à gauche de y.
• Cas 2 : Posons
x1 x2 · · · xk−1 v = y1 y2 · · · yp
avec v 6= ε puisque X est un code.
v

x1 x2 ··· xk−1 xk = y u

y1 y2 ··· yp yp+1 ··· yl−1 yl

Il vient xk u = vyp+1 · · · yl . On a alors que yp+1 , . . . , yl−1 sont des facteurs propres
de xk = y, i.e. |yp+1 |, . . . , |yl−1 | < |y|. Ainsi ils sont aussi dans X. De plus, puisque
yl 6= y, y étant sans bords, on a yl ∈ X.
Finalement, z est bien dans X ∗ .

Le théorème suivant découle simplement de la proposition précédente.

Théorème 2.2.11. Tout code maximal est complet.

Grâce à ce résultat, nous allons désormais pouvoir montrer qu’il existe des codes finis
qui ne sont pas inclus dans un code maximal fini, comme stipulé dans la Remarque 1.2.25.

Exemple 2.2.12. Soit X = {a5 , ba2 , ab, b} un code 3 sur l’alphabet A = {a, b}. Chaque
code maximal contenant X est infini. Nous allons le montrer par l’absurde.
Soit Y un code maximal sur A contenant X et supposons que Y est fini. Posons m =
max{|y| | y ∈ Y } et u = bm a4+5m bm ∈ A∗ . L’ensemble Y étant maximal, il est complet,
ainsi u est facteur d’un mot de Y ∗ . Cependant, bm et a4+5m ne peuvent être des facteurs
propres d’un mot de Y vu leurs longueurs, il existe donc des mots y, y 0 ∈ Y ∪ {ε} et des
naturels p, q, r ≥ 0 tels que
u = bp yaq y 0 br
avec aq ∈ Y ∗ .
Le mot a5 est le seul mot de Y qui ne contient pas de b. En effet, nous allons montrer
que si une autre puissance de a appartient à Y , nous trouverons un mot possédant deux
factorisations différentes, ce qui contredit le fait que Y est un code.
— Si a5i ∈ Y , pour i > 1 4 , alors a5i = (a5 )i .
— Si a5i+1 ∈ Y , pour i ≥ 0, alors (a5 )i (ab) = (a5i+1 )(b).
3. Nous le vérifions grâce à l’algorithme développé dans la Section 1.3 : U1 = {aa}, U2 = {aaa}, U3 = U1
et ε ∈
/ Un pour n = 1, 2, 3.
4. Si i = 0 alors a5i = ε ∈
/ Y et on sait déjà que a5 ∈ Y .
2.2. ENSEMBLES COMPLETS 45

— Si a5i+2 ∈ Y , pour i ≥ 0, alors (ba2 )(a5 )i = (b)(a5i+2 ).

— Si a5i+3 ∈ Y , pour i ≥ 0, alors (ba2 )(a5 )i (ab) = (b)(a5i+3 )(b).
— Si a5i+4 ∈ Y , pour i ≥ 0, alors (a5 )i+1 (b) = (a5i+4 )(ab).
Ainsi, q est forcément un multiple de 5, ce qui implique que |y|a + |y 0 |a ≡ 4 mod 5. Soient

y = bh a5s+i et y 0 = aj+5t bk

avec 0 ≤ i, j ≤ 4. On a i + j ≡ 4 mod 5. Il vient donc i + j = 4. Nous allons alors montrer

que pour tout choix pour i, j, nous arrivons à la conclusion que Y n’est pas un code en
trouvant des mots qui possèdent des décompositions distinctes en mots de Y .
— i = 0, j = 4, alors k ≥ 1 et on a (ba2 )(a5t+4 bk ) = (b)(a5 )t+1 (ab)(b)k−1 .
— i = 1, j = 3, alors on a (bh a5s+1 )(b) = (b)h (a5 )s (ab).
— i = 2, j = 2, alors on a (b)(a5t+2 bk ) = (ba2 )(a5 )t (b)k .
— i = 3, j = 1, alors h ≥ 1 et on a (bh a5s+3 )(b) = (b)h−1 (ba2 )(a5 )s (ab).
— i = 4, j = 0, alors on a (bh a5s+4 )(ab) = (b)h (a5 )s+1 (b).
Ainsi, Y n’est pas fini.

Nous allons maintenant nous intéresser plus spécifiquement à la notion de densité et à

ses liens avec la maximalité des codes.

Définition 2.2.13. Un sous-ensemble P d’un monoïde M est dit fin lorsqu’il n’est pas
dense. Autrement dit, il existe au moins un élément m ∈ M qui n’est pas complétable dans
P , i.e. M mM ∩ P = ∅.

Proposition 2.2.14. Tout sous-ensemble d’un ensemble fin est fin.

Proposition 2.2.15. Soient M un monoïde et P , Q, R ⊂ M .

1. L’ensemble P ∪ Q est fin si et seulement si P et Q sont fins.
2. Si R est dense et P est fin, alors R\P est dense.

Démonstration. 1. Supposons tout d’abord que P et Q sont fins. Ainsi il existe des mots
m, n ∈ M tels que
M mM ∩ P = ∅ et M nM ∩ Q = ∅.
Le mot mn est incomplétable dans P ∪ Q :

M (mn)M ∩ (P ∪ Q) = (M (mn)M ∩ P ) ∪ (M (mn)M ∩ Q)

⊂ (M mM ∩ P ) ∪ (M nM ∩ Q) = ∅.

L’ensemble P ∪ Q est donc fin.

La réciproque découle directement de la proposition précédente.
46 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

2. Procédons par l’absurde et supposons que R\P est fin. Alors, vu le point précédent,
(R\P ) ∪ P est fin. Or, R ⊂ (R\P ) ∪ P , ce qui contredit notre hypothèse.

Remarque 2.2.16. Les ensembles fins d’un monoïde libre ont des propriétés supplémen-
taires :
1. Tout sous-ensemble fini X ⊂ A∗ est fin.
En effet, si on prend un élément w ∈ A∗ \X tel que |w| > max{|x| | x ∈ X}, alors
A∗ wA∗ ∩ X = ∅.
2. Si X, Y ⊂ A∗ sont des ensembles fins, alors XY est fin.
Comme X et Y sont fins, il existe x, y ∈ A∗ tels que x et y sont incomplétables dans
X et Y , respectivement. Montrons par l’absurde que w = xy est incomplétable dans
XY . Supposons qu’il existe u, v ∈ A∗ tels que uxyv ∈ XY . Il existe alors x0 ∈ X et
y 0 ∈ Y tels que uxyv = x0 y 0 . Posons l = |ux|.
— Si |x0 | ≤ l :
u x y v

0 0
x y

Alors y 0 ∈ A∗ yA∗ ∩ Y , ce qui contredit le fait que y est incomplétable dans Y .

— Si |x0 | ≥ l :
u x y v

x0 y0

Alors x0 ∈ A∗ xA∗ ∩ X, ce qui contredit le fait que x est incomplétable dans X.

Puisqu’un ensemble est fin s’il n’est pas dense, intuitivement nous savons qu’il ne
contient que « peu » d’éléments. La proposition suivante va confirmer cette intuition.

Proposition 2.2.17. Soit X ⊂ A∗ un ensemble fin. Pour toute loi de Bernoulli positive
π sur A∗ , on a
π(X) < ∞.

Démonstration. Soit w un mot qui n’est pas facteur d’un mot de X, i.e. w est incomplétable
dans X. Posons n = |w|. On a n ≥ 1. Pour 0 ≤ i ≤ n − 1, considérons

Xi = {x ∈ X | |x| ≡ i mod n}.

n−1
! n−1
[ X
Puisque π(X) = π Xi = π(Xi ), l’union étant disjointe, il suffit de montrer que
i=0 i=0
π(Xi ) est fini pour i = 0, . . . , n − 1.
2.2. ENSEMBLES COMPLETS 47

On a Xi ⊂ Ai (An \{w})∗ . Puisque An \{w} est un code 5 , nous avons

!
[
π ((An \{w})∗ ) = π (An \{w})k (2.33)
k≥0
X
π (An \{w})k


= (2.34)
k≥0
X
= (π (An \{w}))k (2.35)
k≥0
X
= (1 − π(w))k (2.36)
k≥0

puisque le produit (An \{w})k est non ambigu et π(An ) = 1 d’après la Proposition 2.1.2.
Étant donné que π est positif par hypothèse, nous savons que π(w) > 0, et par conséquent
(1 − π(w)) < 1. Nous obtenons donc
1
π ((An \{w})∗ ) = .
π(w)
Finalement, il vient
π(Xi ) ≤ π(Ai (An \{w})∗ )
= π(Ai ) π((An \{w})∗ )
| {z }
=1
1
=
π(w)
car le produit Ai (An \{w})∗ est non ambigu.

Proposition 2.2.18. Soit X ⊂ A∗ un ensemble fin et complet. Soit w un mot incomplétable

dans X. Alors [
A∗ = d−1 X ∗ g −1 = D−1 X ∗ G−1 , (2.37)
d∈D,g∈G

où D est l’ensemble des suffixes de w et G est l’ensemble des préfixes de w.

Démonstration. Soit z ∈ A∗ . Puisque X est complet, X ∗ est dense. Le mot wzw ∈ A∗ est
donc complétable dans X ∗ , il existe alors u, v ∈ A∗ tels que
uwzwv ∈ X ∗ .
Puisque w est incomplétable dans X, il n’est facteur d’aucun mot de X. Par conséquent,
il existe deux factorisations w = g1 d = gd1 telles que
ug1 , dzg, d1 v ∈ X ∗ .
5. C’est un sous-ensemble du code uniforme An .
48 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Ainsi, z ∈ d−1 X ∗ g −1 , ce qui permet de conclure étant donné que la seconde inclusion est
triviale.

Proposition 2.2.19. Soit X ⊂ A∗ un ensemble fin et complet. Pour toute loi de Bernoulli
positive π sur A∗ , on a
π(X) ≥ 1.
!
[ X
Démonstration. On a π(A∗ ) = π An = π(An ) = ∞. Vu la proposition précédente,
| {z }
n≥0 n≥0 =1
on a !
[ X
π(A∗ ) = π d−1 X ∗ g −1 ≤ π d−1 X ∗ g −1 .


d∈D,g∈G d∈D,g∈G

Ainsi il existe une paire (g, d) ∈ G × D telle que π(d−1 X ∗ g −1 ) = ∞, la somme étant finie.
Puisque d(d−1 X ∗ g −1 )g ⊂ X ∗ , il vient

π(d(d−1 X ∗ g −1 )g) = π(d)π(d−1 X ∗ g −1 )π(g)

≤ π(X ∗ )

étant donné que le produit d(d−1 X ∗ g −1 )g est non ambigu, d et g étant fixés. Puisque π est
supposée positif, π(X ∗ ) = ∞. De plus,
!
[
π(X ∗ ) = π Xn
n≥0
X
≤ π(X n )
n≥0
X
≤ (π(X))n .
n≥0

Procédons alors par l’absurde en supposant que π(X) < 1. Vu ce qui précède, on a π(X ∗ ) <
∞, ce qui mène à une contradiction. Ainsi π(X) ≥ 1.

Théorème 2.2.20. Tout code fin et complet est maximal.

Démonstration. Soit X un code fin et complet. Par le Théorème 2.1.15, nous savons que
π(X) ≤ 1 pour toute loi de Bernoulli π sur A∗ . Par la proposition précédente, nous savons
que π(X) ≥ 1 pour toute loi de Bernoulli positive π sur A∗ . Ainsi, il vient que π(X) = 1
pour toute loi de Bernoulli positive π sur A∗ . Finalement, par la Proposition 2.1.21, on en
tire que X est maximal.
Les Théorèmes 2.2.11 et 2.2.20 nous permettent d’obtenir une condition équivalente au
fait d’être complet.
2.2. ENSEMBLES COMPLETS 49

Théorème 2.2.21. Soit X un code sur A. L’ensemble X est complet si et seulement si X

est dense ou maximal.

Démonstration. La condition est nécessaire. En effet, supposons que X est complet mais
pas dense. Ainsi, X est fin et vu le Théorème 2.2.20, on en tire que X est maximal.
La condition est suffisante puisque nous savons que tout ensemble dense est complet
vu la Proposition 2.2.6 et que tout code maximal est complet vu le Théorème 2.2.11.

Proposition 2.2.22. Soit X ⊂ A∗ un code maximal fini. Pour tout sous-ensemble non
vide B de A, le code X ∩ B ∗ est un code maximal sur B.

Démonstration. Soit n = max{|x| | x ∈ X}. Puisque Y = X ∩ B ∗ ⊂ X et que X est fini,

par la Remarque 2.2.16, nous savons que Y est fin. Ainsi pour montrer que Y est un code
maximal sur B, vu le Théorème 2.2.20, il suffit de montrer que Y est complet dans B ∗ .
Soit w ∈ B ∗ et b ∈ B. Considérons le mot w0 = bn+1 wbn+1 ∈ B ∗ ⊂ A∗ . Nous savons que
X est un code maximal sur A, ainsi il est complet sur A. Il existe donc des mots u, v ∈ A∗
tels que
uw0 v = x1 x2 · · · xk ,
avec x1 , . . . , xk ∈ X, i.e. uw0 v ∈ X ∗ . Vu la définition de n, il existe deux naturels 1 < i ≤
j < k tels que
xi xi+1 · · · xj = br wbs
pour certains r, s ∈ {1, . . . , n}. On a alors xi , xi+1 , . . . , xj ∈ X ∩ B ∗ = Y , et donc w est
complétable dans Y ∗ .

Corollaire 2.2.23. Soit X ⊂ A∗ un code maximal fini. Pour chaque lettre a ∈ A, il existe
un naturel n tel que an ∈ X.

Démonstration. Soit B = {a}. Vu la proposition précédente, X ∩{a}∗ est un code maximal,

et donc non vide. Il existe alors w ∈ X ∩ {a}∗ , i.e. il existe n tel que w = an ∈ X.

Définition 2.2.24. Soit X ⊂ A∗ un code maximal fini et a ∈ A. Le naturel n tel que

an ∈ X est appelé l’ordre de a relatif à X.

Théorème 2.2.25. Soit X un code fin sur A. Les propositions suivantes sont équivalentes.
1. L’ensemble X est un code maximal.
2. Il existe une loi de Bernoulli positive π sur A∗ telle que π(X) = 1.
3. Pour toute loi de Bernoulli positive π sur A∗ , on a π(X) = 1.
4. L’ensemble X est complet.

Démonstration. On a les implications suivantes :

 50 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

1 ⇒ 4 : Immédiat vu le Théorème 2.2.11.

4 ⇒ 3 : On sait, vu le Théorème 2.1.15 et la Proposition 2.2.19, que pour toute loi de Bernoulli
positive π sur A∗ , on a π(X) = 1.
3 ⇒ 2 : Évident vu qu’il existe des lois de Bernoulli positives π sur A∗ .
2 ⇒ 1 : Direct vu la Proposition 2.1.21.

Ce théorème nous permet de vérifier plus aisément si un code fin est maximal. En effet,
il nous suffit maintenant de considérer n’importe quelle loi de Bernoulli positive et de voir
si on a bien π(X) = 1.
[
Remarque 2.2.26. Considérons l’ensemble préfixe X = an bAn sur l’alphabet A =
n≥0
{a, b}.
• L’ensemble X est complet puisqu’il est dense :
En effet, pour tout w ∈ A∗ , a|w| bw ∈ X.
• Toute loi de Bernoulli positive π sur A∗ est telle que π(X) = 1.
En effet, soit π une loi de Bernoulli positive sur A∗ telle que π(a) = p et π(b) = 1 − p,
avec 0 < p < 1. On a alors
!
[
π(X) = π an bAn
n≥0
X
= π(an bAn )
n≥0
!
X X
= π(w)
n≥0 w∈an bAn
!
X X
= π(an )π(b) π(u)
n≥0 u∈An
| {z }
=1
X
= pn (1 − p)
n≥0
1
= (1 − p)
1−p
= 1.

Ainsi, X satisfait les quatre conditions du Théorème 2.2.25 alors qu’il n’est pas fin.

Théorème 2.2.27. Soit X ⊂ A+ un ensemble fin et soit π une loi de Bernoulli positive
sur A∗ . Chaque combinaison de deux des trois assertions suivantes implique la troisième.
1. L’ensemble X est un code.
 2.2. ENSEMBLES COMPLETS 51

2. On a π(X) = 1.
3. L’ensemble X est complet.

Démonstration. On a les implications suivantes :

1 + 2 ⇒ 3 : Si π(X) = 1, avec X un code, nous savons que X est un code maximal par la
Proposition 2.1.21. Vu le Théorème 2.2.11, il vient que X est complet.
1 + 3 ⇒ 2 : Puisque X est un code fin et complet, vu le Théorème 2.2.25, on sait que
π(X) = 1.
2 + 3 ⇒ 1 : Soit n ≥ 1 un naturel. Commençons par montrer que l’ensemble X n est fin et
complet.
• Complet : Soit u ∈ A∗ . Puisque X est complet par hypothèse, il existe v, w ∈ A∗ tels
que vuw ∈ X ∗ . Il existe donc k ≥ 0 tel que vuw ∈ X k . Ainsi (vuw)n ∈ (X n )k ⊂
(X n )∗ , ce qui montre que u est complétable dans (X n )∗ .
• Fin : Nous savons que X est fin et par la Remarque 2.2.16 nous savons que le produit
de deux ensembles fins est fin. Ainsi il vient que X n est un ensemble fin.
Grâce à la Proposition 2.2.19, nous savons que π(X n ) ≥ 1. Or, vu la Proposition 2.1.10,
nous savons que π(X n ) ≤ π(X)n , i.e. π(X n ) ≤ 1. Il vient alors que π(X n ) = 1. Ainsi, pour
tout n ≥ 1 nous avons π(X n ) = π(X)n . On en conclut, par la Proposition 2.1.20, que X
est un code.

Nous terminons cette section en nous intéressant aux codes réguliers. Comme nous
l’avons vu précédemment, un code fini n’est pas nécessairement inclus dans un code fini
maximal. Cependant, nous pouvons nous en sortir en considérant des codes réguliers.

Proposition 2.2.28. Tout code régulier est fin.

Démonstration. Soit X ⊂ A∗ un code régulier. Soit A = {Q, q0 , F, A, δ} un automate fini

déterministe acceptant X. À tout mot w ∈ A∗ , nous allons associer le nombre suivant :

ρ(w) = Card(δ(Q, w)) = Card{δ(q, w) | q ∈ Q}.

On a alors ρ(w) ≤ Card(Q) et ρ(uwv) ≤ ρ(w) pour tous mots u, v ∈ A∗ . Soit J l’ensemble
des mots w ∈ A∗ tels que ρ(w) est minimal. L’ensemble J est un idéal de A∗ . En effet,
• J ⊂ A∗
• J est non vide
• Soit w ∈ J, puisque ρ(uwv) ≤ ρ(w) avec ρ(w) minimal, on a ρ(uwv) = ρ(w) et donc
uwv ∈ J pour u, v ∈ A∗ .
Soit w ∈ J, posons P = δ(Q, w). Montrons que l’on a P = δ(P, w).
D’une part δ(P, w) ⊂ δ(Q, w) = P et d’autre part δ(P, w) = δ(Q, w2 ). Il vient alors que
52 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Card(δ(P, w)) = Card(δ(Q, w2 )) = ρ(w2 ). Puisque ρ(w2 ) ≤ ρ(w), avec ρ(w) minimal, il
vient
Card(δ(P, w)) = ρ(w) = Card(P ).
L’égalité souhaitée en découle.
Ceci nous montre alors que l’application g : P → Q, p 7→ δ(p, w) a pour image P , et
est donc une bijection de P dans lui-même. Il existe donc un naturel n ≥ 1 tel que
l’application p 7→ δ(p, wn ) est l’application identité sur P . Puisque P = δ(Q, w), on a
δ(q, w) = δ(q, wn+1 ) pour tout q ∈ Q. Pour montrer que X est fin, il suffit de montrer qu’il
ne rencontre pas l’idéal J, vu la Remarque 2.2.3. Procédons par l’absurde en supposant
que J ∩ X 6= ∅.
Soit x ∈ J ∩ X. Nous avons alors δ(q0 , x) = f ∈ F puisque A accepte X. De plus, puisque
x ∈ J, nous savons que δ(q0 , xn+1 ) = δ(q0 , x) = f ∈ F . Il vient alors que xn+1 ∈ X, ce qui
contredit le fait que X est un code puisque xn+1 = (x)n+1 .

Remarque 2.2.29. La réciproque est fausse. En effet, l’ensemble X = {an bn | n ≥ 1} est

fin, puisque par exemple le mot ba est incomplétable dans X. Par contre nous savons que
X n’est pas régulier.
Proposition 2.2.30. Soit X ⊂ A+ un code. Soit y ∈ A∗ un mot sans bords tel que
A∗ yA∗ ∩ X ∗ = ∅. Soit
U = A∗ \(X ∗ ∪ A∗ yA∗ ).
L’ensemble Y = X ∪ y(U y)∗ est un code complet.
Démonstration. Posons V = A∗ \A∗ yA∗ . Par hypothèse, nous avons X ∗ ⊂ V et U = V \X ∗ .
• L’ensemble Z = V y est un code préfixe :
Soient v, v 0 ∈ V tels que vy soit préfixe propre de v 0 y. Plus précisément vy doit être
préfixe de v 0 . En effet, si ce n’était pas le cas, cela contredirait le fait que y est sans
bords :
v y

v0 y

Ainsi, il existe un mot u ∈ A∗ tel que vyu = v 0 . Il vient alors que v 0 ∈ A∗ yA∗ , ce qui
contredit le fait que v 0 ∈ V .
• L’ensemble Y est un code :
Procédons par l’absurde et supposons que Y n’est pas un code. Il existe donc un mot
w ∈ Y ∗ , supposé de longueur minimale, qui possède deux factorisations distinctes en
mots de Y :
w = y1 y2 · · · yn = y10 y20 · · · ym
0
, (2.38)
avec n, m ≥ 1, yi , yj0 ∈ Y et y1 6= y10 . L’ensemble X étant un code, il doit forcément
y avoir un des yi , yj0 qui appartient à X. Supposons que ce soit l’un des y1 , . . . , yn
qui soit dans Y \X et soit p le plus petit indice tel que yp ∈ y(U y)∗ . Par hypothèse,
2.2. ENSEMBLES COMPLETS 53

nous savons que y n’est pas complétable dans X ∗ , i.e. y ∈ / F (X ∗ ). Par conséquent,
/ F (X ∗ ) et donc w ∈
yp ∈ / X ∗ . Ainsi, nous savons qu’un des y10 , . . . , ym
0
est également
∗ 0 ∗
dans y(U y) . Soit q le plus petit indice tel que yq ∈ y(U y) . Nous avons donc

y · · · y y, y 0 · · · y 0 y ∈ Z
|1 {z p−1} |1 {z q−1}
∈X ∗ ⊂V ∈X ∗ ⊂V

Vu 2.38, on a que y1 · · · yp−1 est préfixe de y10 · · · yq−1

0
ou inversement. S’il s’agit d’un
préfixe propre, alors y1 · · · yp−1 y reste un préfixe propre de y10 · · · yq−1
0
y, ce qui contredit
0 0
le fait que Z est préfixe. Ainsi, on a y1 · · · yp−1 = y1 · · · yq−1 . Or, X est un code et
y1 6= y10 , on a alors forcément que p = q = 1, i.e. y1 , y10 ∈ y(U y)∗ . Posons donc

y1 = yu1 y · · · yuk y et y10 = yu01 y · · · yu0l y

avec u1 , . . . uk , u01 , . . . u0l ∈ U . Supposons que y1 soit préfixe de y10 . On sait que U ⊂ V
et donc ui y, u0j y ∈ Z. Il s’ensuit que

u1 = u01 , . . . , uk = u0k .

Posons t = u0k+1 y · · · yu0l y. On a

y2 y3 · · · yn = ty20 · · · ym
0
.

Le mot y, étant facteur de t, apparait dans y2 · · · yn . Ainsi, l’un des y2 , . . . , yn est

dans y(U y)∗ . Soit r le plus petit indice tel que yr ∈ y(U y)∗ . Donc y2 y3 · · · yr−1 y ∈ Z
et u0k+1 y ∈ Z sont préfixes d’un même mot, par conséquent

y2 y3 · · · yr−1 = u0k+1 .
| {z }
∈X ∗

Ainsi u0k+1 ∈ X ∗ , ce qui contredit le fait que u0k+1 ∈ U . Ainsi, Y est un code.
• L’ensemble Y est complet :
Soit w ∈ A∗ et décomposons-le de la façon suivante :

w = v1 yv2 y · · · yvn−1 yvn

avec n ≥ 1 et vi ∈ V . Puisque V = U ∪ X ∗ , notons vi1 , . . . , vik les vi qui sont dans

X ∗ , il vient alors

ywy = (yv1 y · · · yvi1 −1 )vi1 (yvi1 +1 y · · · yvi2 −1 y) · · · vik (yvik +1 y · · · yvn y).

Chaque parenthèse appartient à y(U y)∗ ⊂ Y . Ainsi, le mot ywy ∈ Y ∗ , i.e. w est
complétable dans Y ∗ .

Théorème 2.2.31. Tout code régulier est inclus dans un code régulier maximal.
54 CHAPITRE 2. DESCRIPTION QUANTITATIVE DES CODES

Démonstration. Soit X un code régulier. Si X est complet, alors il est maximal puisqu’il
est fin par la Proposition 2.2.28. Sinon, il existe y ∈ A∗ tel que A∗ yA∗ ∩ X ∗ = ∅. Au
vu du Lemme 2.2.9 6 , on peut le supposer sans bords. Puisque l’ensemble X est régulier,
nous savons que U = A∗ \(X ∗ ∪ A∗ yA∗ ) est également régulier. Il en va de même pour
Y = X ∪ y(U y)∗ . Vu les Propositions 2.2.28 et 2.2.30, l’ensemble Y est un code fin et
complet. Finalement, Y est maximal vu le Théorème 2.2.20.

En particulier, tout code fini est inclus dans un code régulier maximal.

6. Si Card(A) = 1, le théorème est évident. On peut donc supposer travailler sur un alphabet d’au
moins deux lettres.
Chapitre 3

Codes préfixes

Dans ce chapitre, nous allons nous focaliser sur une famille particulière de codes : les
codes préfixes. Lorsque l’on s’intéresse aux codes, les codes préfixes occupent rapidement
une place privilégiée puisqu’il s’agit des codes les plus faciles à construire et à manipuler.
Il est donc naturel de les étudier plus en profondeur.
Nous allons tout d’abord donner quelques résultats généraux concernant les ensembles
préfixes avant de nous intéresser aux liens entre les codes préfixes et les séries formelles.
Une partie de ce chapitre sera consacrée à l’étude des automates acceptant les en-
sembles préfixes. Pour cela, nous aurons besoin d’introduire préalablement la notion de
représentation littérale d’un ensemble X ⊂ A∗ .
Ensuite, nous adapterons les notions de densité vues dans la Section 2.2 au cas parti-
culier des ensembles préfixes dans le but d’en étudier la maximalité.
Finalement, nous nous concentrerons sur un sous-ensemble spécifique des codes pré-
fixes : les codes sémaphores. Nous établirons une série de résultats concernant cette nou-
velle famille avant de déboucher sur le Théorème 3.7.15 qui nous montrera que celle-ci
possède une propriété intéressante qui n’est pas partagée par les codes préfixes en toute
généralité.
Évidemment, tous les résultats présentés dans ce chapitre peuvent aisément être adaptés
aux ensembles suffixes.

3.1 Premiers résultats

Rappelons que pour des mots x, y ∈ A∗ , nous notons x  y (resp. x ≺ y) le fait que x
est préfixe (resp. préfixe propre) de y. L’ordre  est l’ordre préfixe.

Définition 3.1.1. Deux mots x, y ∈ A∗ sont dits incomparables pour l’ordre préfixe si x
n’est pas préfixe de y et si y n’est pas préfixe de x.

Naturellement, un sous-ensemble X ⊂ A∗ est préfixe si les mots de X sont incompa-

rables deux-à-deux pour l’ordre préfixe.

55
56 CHAPITRE 3. CODES PRÉFIXES

Posons
XA− = X(A+ )−1 = {w ∈ A∗ | ∃u ∈ A+ : wu ∈ X},
l’ensemble des préfixes propres des mots de X. Ainsi, w ∈ XA− si et seulement si w ≺ x
pour un x ∈ X.

Proposition 3.1.2. Soit X ⊂ A∗ . Les assertions suivantes sont équivalentes :

1. L’ensemble X est préfixe.
2. X ∩ XA− = ∅.
3. X ∩ XA+ = ∅.
4. Les ensembles XA− , X, XA+ sont deux-à-deux disjoints.
5. Si xu = x0 u0 avec x, x0 ∈ X et u, u0 ∈ A∗ , alors x = x0 et u = u0 .
6. Si x, xu ∈ X alors u = ε.

Démonstration. Les implications 1 ⇒ 2, 2 ⇒ 3, 3 ⇒ 4, 5 ⇒ 6 et 6 ⇒ 1 sont immédiates.

Nous allons démontrer que 4 implique 5, afin de compléter le cycle d’implications.
Soient x, x0 ∈ X et u, u0 ∈ A∗ tels que xu = x0 u0 .
• Cas 1 : u = u0 = ε
On a directement x = x0 et u = u0 .
• Cas 2 : u = ε et u0 ∈ A+ .
Alors x = x0 u0 . Ainsi, x ∈ X ∩ XA+ , ce qui contredit l’hypothèse.
• Cas 3 : u0 = ε et u ∈ A+ .
Alors x0 = xu. Ainsi, x0 ∈ X ∩ XA+ , ce qui contredit l’hypothèse.
• Cas 4 : u, u0 ∈ A+ .
— Supposons x ≺ x0 . Il existe alors v ∈ A+ tel que xv = x0 , i.e. xv ∈ X. Ainsi,
x ∈ X ∩ XA− , ce qui contredit l’hypothèse.
— Supposons x0 ≺ x. Il existe alors v 0 ∈ A+ tel que x0 v 0 = x, i.e. x0 v 0 ∈ X. Ainsi,
x0 ∈ X ∩ XA− , ce qui contredit l’hypothèse.
Il vient donc x = x0 et par conséquent u = u0 .

La proposition suivante nous permet de lier les notions de code préfixe et d’idéal à
droite.

Proposition 3.1.3. Pour tout ensemble Y ⊂ A∗ , l’ensemble X = Y \Y A+ est préfixe.

De plus,
XA∗ = Y A∗ (3.1)
et X est l’ensemble minimum avec cette propriété.
3.1. PREMIERS RÉSULTATS 57

Démonstration. Montrons tout d’abord que l’ensemble X est préfixe.

Puisque X ⊂ Y , il vient XA+ ⊂ Y A+ . Ainsi,

X ∩ XA+ ⊂ X ∩ Y A+ = ∅.

Vu les équivalences de la Proposition 3.1.2, on en tire que X est bien préfixe.

Montrons ensuite l’égalité 3.1.
⊂ : On a trivialement XA∗ ⊂ Y A∗ .
⊃ : Soient y ∈ Y et u son plus petit préfixe dans Y . On a alors u ∈ X. Ainsi, y ∈ XA∗ ,
et donc Y ⊂ XA∗ .
Montrons finalement que X est minimum pour cette propriété.
Soit Z un ensemble de générateurs de l’idéal à droite Y A∗ , i.e. ZA∗ = Y A∗ . Soit x ∈ X ⊂
Y ⊂ Y A∗ , alors x = zu pour u ∈ A∗ et z ∈ Z. Puisque XA∗ = Y A∗ , X génère également
l’idéal Y A∗ , et donc z = x0 u0 pour x0 ∈ X et u0 ∈ A∗ . Il vient donc

x = zu = x0 u0 u.

L’ensemble X étant préfixe, il vient que u0 u = ε, ce qui montre que X ⊂ Z.

Définition 3.1.4. L’ensemble X = Y \Y A+ est appelé la partie initiale de Y ou la base
de l’idéal à droite Y A∗ .
La notion d’ensemble préfixe est intimement liée à celles d’idéal à droite et d’ensemble
fermé par préfixes. En effet, la proposition suivante nous fournit des bijections naturelles
entre les familles d’ensembles suivantes :
1. La famille X des sous-ensembles préfixes de A∗ ;
2. La famille I composée de l’ensemble vide et des idéaux à droite de A∗ ;
3. La famille R des sous-ensembles fermés par préfixe de A∗ .
Proposition 3.1.5. 1. L’application f : X 7→ XA∗ est une bijection de X dans I.
L’application g : I 7→ I\IA+ est son inverse de I dans X .
2. L’application h : R 7→ A∗ \R est une bijection de R dans I. L’application i : I 7→
A∗ \I est son inverse de I dans R.
3. L’application j : X 7→ A∗ \XA∗ est une bijection de X dans R. L’application k : R 7→
({ε} ∪ RA)\R est son inverse de R dans X .
Démonstration. 1. Pour tout sous-ensemble non vide X ⊂ A∗ , l’ensemble XA∗ est un
idéal à droite de A∗ .
Pour tout sous-ensemble I de A∗ , l’ensemble I\IA+ est préfixe vu la Proposition
3.1.3.
Ainsi, les applications f et g sont bien définies. Nous allons montrer que ces applica-
tions sont inverses l’une de l’autre.
58 CHAPITRE 3. CODES PRÉFIXES

Montrons que f ◦ g = id, i.e. pour tout idéal à droite I de A∗ , on a (I\IA+ )A∗ = I.
Soit I un idéal à droite de A∗ . Posons X = I\IA+ . Par la Proposition 3.1.3, nous
avons XA∗ = IA∗ . De plus, nous savons que IA∗ = I, vu la définition d’un idéal à
droite. Il vient alors XA∗ = I.
Montrons que g ◦ f = id, i.e. pour tout ensemble préfixe X de A∗ , on a XA∗ \XA+ =
X.
Soit X ⊂ A∗ un ensemble préfixe. Vu la Proposition 3.1.2, nous avons X ∩ XA+ = ∅.
Il s’ensuit que X = X\XA+ . On a alors

X = X\XA+ = (X ∪ XA+ )\XA+ = XA∗ \XA+ .

2. Soit I un idéal à droite de A∗ . Si w ∈

/ I, alors aucun de ses préfixes n’est dans I, i.e.
tous ses préfixes sont dans A \I. En effet, si w = vu avec v ∈ I et u ∈ A∗ , puisque
∗

I est un idéal à droite on aurait que vu ∈ I, ce qui contredirait le fait que w ∈ / I.

∗
L’ensemble R = A \I est donc bien un ensemble fermé par préfixe.
Soit R un ensemble fermé par préfixe. L’ensemble A∗ \R est soit vide soit un idéal à
droite de A∗ . En effet si w ∈/ R alors wu ∈ / R pour tout u ∈ A∗ . Autrement dit, si
∗ ∗
w ∈ A \R alors wu ∈ A \R.
Les applications h et i sont bien définies. De plus, il est évident que ces applications
sont bien inverses l’une de l’autre.
3. Vu les points précédents, on a i ◦ f : X → R, X 7→ A∗ \XA∗ . Ainsi, j = i ◦ f est bien
une bijection de X dans R.
Soit R un ensemble fermé par préfixe. On a

g ◦ h : R → X , R 7→ (A∗ \R)\(A∗ \R)A+ .

Nous allons montrer que (A∗ \R)\(A∗ \R)A+ = ({ε} ∪ RA)\R, ainsi nous aurons
k = g ◦ h, qui est une bijection.
Remarquons tout d’abord que dans le cas où R = ∅, l’égalité est évidente puisque
({ε} ∪ RA)\R = {ε} et (A∗ \R)\(A∗ \R)A+ = A∗ \A+ = {ε}. Supposons donc que
R 6= ∅. Dans ce cas, ε ∈ R, ainsi il suffit de montrer l’égalité (A∗ \R)\(A∗ \R)A+ =
RA\R.
⊂ : Soit x ∈ (A∗ \R)\(A∗ \R)A+ ⊂ A∗ \R. Posons x = ua avec u ∈ A∗ et a ∈ A.
On a forcément que u ∈ R, sinon ua ∈ (A∗ \R)A, ce qui contredit le fait que
/ (A∗ \R)A+ . Ainsi, x = ua ∈ RA\R.
x = ua ∈
⊃ : Soit x ∈ RA\R ⊂ A∗ \R. Il existe donc r ∈ R et a ∈ A tels que x = ra.
Puisque R est fermé par préfixe, tous les préfixes propres de x sont dans R.
Ainsi, x n’a aucun préfixe propre dans A∗ \R, i.e. x ∈
/ (A∗ \R)A+ . Donc x ∈
∗ ∗ +
(A \R)\(A \R)A .

Corollaire 3.1.6. Soient X, Y ⊂ A∗ des ensembles préfixes. Si XA∗ = Y A∗ , alors X = Y .

3.2. LIEN AVEC LES SÉRIES FORMELLES 59

3.2 Lien avec les séries formelles

Proposition 3.2.1. Soit X un sous-ensemble de A+ et soit X ∗ le sous-monoïde engendré
par X. L’ensemble X est un code si et seulement si X ∗ = (X)∗ ou, de manière équivalente,
X ∗ = (ε − X)−1 .
Démonstration. Vu la Proposition 1.1.5, on sait que le coefficient ((X)∗ , w) d’un mot w ∈
A∗ est le nombre de factorisations distinctes de w en mots de X. La condition est nécessaire
puisque si X est un code alors

((X)∗ , w) = Card{(x1 , x2 , . . . , xn ) | n ≥ 0, xi ∈ X, w = x1 · · · xn }
(
1 si w ∈ X ∗
=
0 sinon
= (X ∗ , w).

La condition est aussi suffisante. Procédons par l’absurde et supposons que X n’est pas
un code. Il existe alors un mot w ∈ X ∗ tel que ((X)∗ , w) ≥ 2, ce qui contredit le fait que
X ∗ = (X)∗ .
Proposition 3.2.2. Soient X un code préfixe sur A et R = A∗ \XA∗ . Alors

X − ε = R(A − ε) (3.2)

et
A∗ = X ∗ R. (3.3)
Démonstration. Le produit XA∗ est non ambigu vu le point 5 de la Proposition 3.1.2.
Ainsi, par la Proposition 1.1.4, on a XA∗ = X A∗ . Il vient donc

R = A∗ \XA∗ = A∗ − X A∗ = (ε − X)A∗ . (3.4)

On a A∗ = (ε−A)−1 grâce à la proposition précédente. Ainsi, en multipliant 3.4 par (ε−A)

à droite, on obtient 3.2 :

R = (ε − X)A∗
⇒ R(ε − A) = (ε − X)A∗ (ε − A)
⇒ R(A − ε) = (X − ε) (ε − A)−1 (ε − A)
| {z }
=ε

⇒ R(A − ε) = (X − ε).

De plus, les égalités 3.2 et 3.3 sont équivalentes. Par la proposition précédente, puisque
X est un code, nous savons que X ∗ = (ε − X)−1 . Ainsi, en multipliant 3.2 par X ∗ à gauche
et A∗ à droite, on retombe sur 3.3. De manière analogue, en multipliant 3.3 à gauche par
(ε − X) et à droite par (ε − A), nous obtenons 3.2.
60 CHAPITRE 3. CODES PRÉFIXES

Remarque 3.2.3. 1. L’égalité 3.2 peut être réécrite

X − ε = R(A − ε)
X − ε = RA − R
X + R = RA + ε.

Ainsi, on voit qu’un mot de R concaténé à une lettre est soit dans X soit dans R.
De plus tout mot de X se décompose en un mot de R concaténé à une lettre.
2. L’égalité 3.3 nous apprend, quant à elle, que tout mot w ∈ A∗ possède une unique
factorisation de la forme
w = x1 · · · xn u
avec xi ∈ X et u ∈ R.

3.3 Représentation graphique des codes préfixes

Nous allons maintenant représenter les codes préfixes au moyen d’arbres dont les feuilles
correspondront aux mots du code.
Tout d’abord, nous associons un arbre infini à l’ensemble A∗ de la manière suivante :
L’alphabet est totalement ordonné et les mots de A∗ de même longueur sont ordonnés
lexicographiquement. Chaque sommet de l’arbre représente un mot de A∗ , les mots les plus
courts se trouvant en haut de l’arbre et les mots les plus longs sont en bas. Dans le cas de
mots de même longueur, ils sont disposés horizontalement selon l’ordre lexicographique de
gauche à droite. On dessine une arête d’un mot u vers un mot v si et seulement si v = ua
pour un a ∈ A.
L’arbre obtenu de cette manière est appelé la représentation littérale de A∗ .
Exemple 3.3.1. Considérons l’alphabet A = {a, b}. Sa représentation littérale débute
comme suit :
ε

a b

aa ab ba bb

aaa aab aba abb baa bab bba bbb

.. .. .. .. .. .. .. ..
. . . . . . . .

Maintenant nous considérons un sous-ensemble X de A∗ . Nous lui associons un « sous-

arbre » de la représentation littérale de A∗ :
On ne conserve que les sommets qui correspondent aux préfixes des mots de X. Parmi ceux-
ci nous ne nommons que ceux appartenant à X. L’arbre ainsi obtenu est la représentation
littérale de X.
3.4. ENSEMBLES PRÉFIXES ET AUTOMATES 61

Exemple 3.3.2. Considérons l’ensemble X = {a, ba, baa} sur l’alphabet A = {a, b}. La
représentation littérale de X est

ba

baa

On se convainc alors qu’un ensemble X est préfixe si et seulement si, dans sa représen-
tation littérale, les sommets correspondant aux mots de X sont exactement les feuilles de
l’arbre.
Exemple 3.3.3. Considérons l’ensemble préfixe X = {a, baa, bab, bb} sur l’alphabet A =
{a, b}. La représentation littérale de X est

bb

baa bab

Nous pouvons remarquer que nous avons en effet une correspondance entre les mots de X
et les feuilles de sa représentation littérale.

3.4 Ensembles préfixes et automates

Comme nous venons de le voir, la représentation littérale d’un sous-ensemble X de A∗
nous permet de vérifier s’il est ou non préfixe. De plus, elle nous fournit une méthode pour
déterminer si un mot w est dans X ∗ pour un certain code préfixe X fixé. En effet, il nous
suffit de suivre le chemin, partant de la racine et suivant chaque lettre successivement de w.
À chaque fois qu’une feuille est atteinte, nous continuons la lecture des lettres en repartant
de la racine. Si après avoir lu la dernière lettre de w nous atteignons une feuille, cela signifie
que le mot w appartient bien à l’ensemble X ∗ .
Dans cette section, nous allons nous intéresser à quelques automates dérivés des repré-
sentations littérales.

Nous commençons par présenter une caractérisation des ensembles préfixes en termes
d’automates.
Proposition 3.4.1. Soit X ⊂ A∗ . Les assertions suivantes sont équivalentes :
 62 CHAPITRE 3. CODES PRÉFIXES

1. L’ensemble X est préfixe.

2. L’automate minimal AX n’a soit qu’un état et celui-ci est non accepteur, soit qu’un
/ FX pour tout w ∈ A+ .
état final f . On a de plus δX (f, w) ∈
3. Il existe un automate déterministe A = (Q, q0 , F, A, δ) acceptant X tel que δ(f, w) ∈
/
F pour tous f ∈ F et w ∈ A+ .
Démonstration. L’implication 2 ⇒ 3 est évidente. Montrons alors les deux implications
suivantes afin de compléter le cycle.
1 ⇒ 2 : Si X = ∅, il est évident que l’automate minimal qui l’accepte ne possède qu’un état et
que celui-ci n’est pas final. Supposons alors que X 6= ∅. Soit AX l’automate minimal
de X. Pour tout f ∈ FX , on a
{w ∈ A∗ | δX (f, w) ∈ FX } = {ε}.
En effet, soit x ∈ X et w ∈ A∗ tels que δX (q0,X , x) = f et δX (f, w) ∈ FX . Alors
δX (q0,X , xw) ∈ FX , i.e. xw ∈ X, d’où w = ε puisque X est préfixe. Ainsi, on a bien
δX (f, w) ∈ / F pour tout w ∈ A+ .
Puisque AX est minimal, il est réduit. Donc si p, q ∈ FX , on a
{w ∈ A∗ | δX (p, w) ∈ FX } = {ε} = {w ∈ A∗ | δX (q, w) ∈ FX },
ce qui implique p = q, ce qui montre que l’état final est unique.
3 ⇒ 1 : On sait que δ(f, w) ∈ / F pour tous f ∈ F et w ∈ A+ . Si x ∈ X et w ∈ A+ alors
δ(q0 , xw) = δ(δ(q0 , x), w) ∈
/ F . Donc xw ∈
/ X. Ainsi, X est préfixe.
| {z }
∈F

Soit X un code préfixe. Nous allons construire un automate A acceptant X à partir de

la représentation littérale de X. Nous appellons cet automate l’automate littéral de X :
A = (XA− ∪ X, ε, X, A, ∆)
où la relation de transition est définie par ∆ = {(u, a, ua) | ua ∈ XA− ∪ X}.
Exemple 3.4.2. Soit l’ensemble X = {ab, bab, bb} sur l’alphabet A = {a, b}.
La représentation littérale de X est : L’automate littéral de X est :

ε
a b
a b
b a b

ab bb ab ba bb
b

bab bab
3.4. ENSEMBLES PRÉFIXES ET AUTOMATES 63

Remarque 3.4.3. Pour rendre l’automate littéral déterministe, il suffit de lui ajouter un
puits vers lequel sont dirigées toutes les transitions manquantes.
Considérons deux états de l’automate littéral. Cela revient à considérer deux préfixes
de mots de X, disons u et v. Ces deux états sont non distingués si et seulement si u−1 X =
v −1 X. Étant donné la construction de la représentation littérale, cette dernière égalité
traduit le fait que le sous-arbre de la représentation littérale de X partant de la racine u
est isomorphe à celui partant de la racine v.
Nous construisons alors l’automate minimal de X de la façon suivante : nous étiquetons
d’abord par 0 tous les états finals, c’est-à-dire les feuilles. Supposons que nous avons déjà
défini i étiquettes. Considérons les sous-arbres dont tous les nœuds sont étiquetés sauf la
racine. Nous étiquetons alors les racines de sous-arbres isomorphes de la même manière.
Finalement, ces étiquettes correspondront aux états de notre automate minimal.
Exemple 3.4.4. Considérons l’ensemble X défini à l’Exemple 3.4.2. Commençons par éti-
queter les nœuds de notre représentation littérale.

1 2

1
ab bb
0 0

bab
0

Nous pouvons maintenant construire notre automate minimal.

a b
3 1 0
b b
a

Nous présentons maintenant une caractérisation des sous-monoïdes unitaires à droite

en termes d’automates.
Proposition 3.4.5. Soit M un sous-ensemble de A∗ . Les assertions suivantes sont équi-
valentes :
1. M est un sous-monoïde unitaire à droite.
 64 CHAPITRE 3. CODES PRÉFIXES

2. L’automate minimal AM a un unique état final qui est l’état initial.

3. Il existe un automate déterministe acceptant M ayant l’état initial comme unique
état final.
Démonstration. L’implication 2 ⇒ 3 est évidente. Montrons alors les deux implications
suivantes afin de compléter le cycle.
1 ⇒ 2 : Les états de AM sont les ensembles u−1 M pour u ∈ A∗ . Si u ∈ M alors u−1 M = M .
En effet, si u ∈ M , on a uv ∈ M si et seulement si v ∈ M . Ainsi, il y a un unique
état final qui correspond à l’état initial.
3 ⇒ 1 : Soit A = {Q, q0 , {q0 }, A, δ} un automate acceptant M . L’ensemble M est un sous-
monoïde puisque ε ∈ M , étant donné que l’état initial est accepteur, et si u, v ∈ M ,
alors δ(q0 , uv) = δ(δ(q0 , u), v) = q0 . Ensuite, l’ensemble M est unitaire à droite. En
| {z }
=q0
effet, soient u, uv ∈ M . On a

δ(q0 , v) = δ(δ(q0 , u), v) = δ(q0 , uv) = q0 .

Ainsi, v ∈ M .

Définition 3.4.6. Soit A = {Q, q0 , F, A, δ} un automate déterministe. Le stabilisateur

d’un état q ∈ Q est
Stab(q) = {w ∈ A∗ | δ(q, w) = q}.
Remarquons que le stabilisateur d’un état d’un automate déterministe est un sous-
monoïde unitaire à droite.
Proposition 3.4.7. Tout sous-monoïde unitaire à droite est le stabilisateur d’un état d’un
automate déterministe.
Démonstration. Soit M un sous-monoïde unitaire à droite. Vu la proposition précédente,
on sait qu’il existe un automate déterministe acceptant M qui possède comme unique état
final l’état initial. Ainsi, Stab(q0 ) = M .
Soit X un code préfixe. Vu la Proposition 1.4.15, nous savons que X ∗ est unitaire à
droite.

La proposition suivante nous fournit une méthode pour construire l’automate minimal
AX ∗ de X ∗ à partir de l’automate minimal AX de X.
Proposition 3.4.8. Soient X un code préfixe non vide sur A et AX = {Q, q0 , {f }, A, δ}
l’automate minimal de X. Alors l’automate minimal de X ∗ est
(
(Q, f, {f }, A, ◦) si Stab(q0 ) 6= {ε}
AX ∗ =
(Q\{q0 }, f, {f }, A, ◦) si Stab(q0 ) = {ε}
3.4. ENSEMBLES PRÉFIXES ET AUTOMATES 65

où la fonction de transition, notée ◦, est définie par

q ◦ a = δ(q, a) si q 6= f

f ◦ a = δ(q0 , a).
Démonstration. Soit B l’automate (Q, f, {f }, A, ◦). On a L(B) = {w ∈ A∗ | f ◦ w = f } =
X ∗ . Vérifions que B est réduit. Considérons des états distincts p et q. Puisque AX est
réduit, il existe un mot u ∈ A+ qui distingue p et q. Supposons par exemple que

δ(p, u) = f et δ(q, u) 6= f.

On peut remarquer que, vu la Proposition 3.4.1, l’état p est distinct de l’état final f , puisque
δ(f, u) 6= f et que de plus, tous les états atteints en lisant successivement une lettre de u
sont également différents de l’état final. On a alors p ◦ u = δ(p, u) = f et p ◦ v 6= f pour
tout v ≺ u.
• Si q ◦ u 6= f , alors le mot u distingue p et q dans l’automate B.
• Sinon, si q ◦ u = f , il existe un préfixe v de u, supposons-le être le plus petit, tel que
q ◦ v = f . Montrons alors que δ(q, v) = f . Procédons par récurrence pour montrer
que ∀ v 0  v, q ◦ v 0 = δ(q, v 0 ).
— Cas de base : v 0 = ε.
Par convention, on a q ◦ ε = q = δ(q, ε).
— Induction : Supposons que l’on a q ◦ v 00 = δ(q, v 00 ) pour tout v 00 ≺ v 0 .
Supposons que v 0 = v 00 a. On a alors

q ◦ v 0 = (q ◦ v 00 ) ◦ a
= δ(q, v 00 ) ◦ a.

Comme v 00 ≺ v 0  v, on sait que δ(q, v 00 ) = q ◦ v 00 6= f , donc

δ(q, v 00 ) ◦ a = δ(δ(q, v 00 ), a) = δ(q, v 0 ).

Donc δ(q, v) = q ◦ v = f . Il vient alors que u 6= v et donc v ≺ u. On a alors p ◦ v 6= f

et q ◦ v = f . Ainsi, p et q sont distingués par v.
On sait que ε ∈/ X puisque X est un code préfixe. On a donc q0 6= f . Ainsi, l’état q0
est accessible dans B si et seulement si {w ∈ A∗ | f ◦ w = q0 } 6= ∅, autrement dit si et
seulement Stab(q0 ) 6= {ε}.
Ceci montre que B est l’automate minimal de X ∗ si Stab(q0 ) 6= {ε}. Sinon la partie
accessible de B est sa restriction à Q\{q0 }.
Remarque 3.4.9. Dans le cas où X est un code préfixe fini, son automate minimal a la
forme AX ∗ = (Q\{q0 }, f, {f }, A, ◦).
Exemple 3.4.10. Considérons l’ensemble X défini à l’Exemple 3.4.2. L’automate minimal
de X ∗ est
66 CHAPITRE 3. CODES PRÉFIXES

1 2
b b

a b
0

Nous pouvons également construire l’automate littéral de X ∗ pour un code préfixe X.

Il s’agit de l’automate
A = (XA− , ε, {ε}, A, ∆)
où les états sont les préfixes propres des mots de X et où la relation de transition est définie
par
∆ = {(u, a, ua) | ua ∈ XA− } ∪ {(u, a, ε) | ua ∈ X}.
Il est donc obtenu depuis l’automate littéral de X en identifiant les états finals à l’état
initial.

Exemple 3.4.11. Considérons l’ensemble X défini à l’Exemple 3.4.2. L’automate littéral

de X ∗ est

a
b

a b
ε ba
b
b

b
b

3.5 Codes préfixes maximaux

Tout comme nous l’avons fait dans le cadre des codes généraux, nous allons maintenant
nous intéresser à la structure des codes préfixes maximaux.

Un ensemble préfixe X ⊂ A∗ est maximal s’il n’est pas strictement inclus dans un autre
ensemble préfixe de A∗ , i.e. X ⊂ Y ⊂ A∗ et Y préfixe implique X = Y .
L’ensemble {ε} est un ensemble préfixe maximal. Tout autre ensemble préfixe maximal
est un code.
 3.5. CODES PRÉFIXES MAXIMAUX 67

Un code maximal qui est préfixe est en particulier un ensemble préfixe maximal. Notons
que la réciproque n’est pas vraie puisqu’il existe des codes préfixes maximaux qui ne sont
pas des codes maximaux. Cependant, dans le cas des ensembles fins, nous verrons que les
codes préfixes maximaux sont des codes maximaux.

Définition 3.5.1. Soient M un monoïde et N un sous-ensemble de M . Un élément m ∈ M

est dit complétable à droite dans N si mw ∈ N pour un certain w ∈ M , ce qui est équivalent
au fait que N rencontre l’idéal à droite mM , i.e. N ∩ mM 6= ∅.
L’ensemble N est dense à droite si pour tout m ∈ M , m est complétable à droite dans
N , ce qui est équivalent au fait que N rencontre tous les idéaux à droite de M .
L’ensemble N est complet à droite si le sous-monoïde engendré par N est dense à droite.
L’ensemble N est fin à droite s’il n’est pas dense à droite.

Soit N un sous-ensemble d’un monoïde M , on a trivialement les implications suivantes :

N dense à droite ⇒ N dense

N complet à droite ⇒ N complet
N fin ⇒ N fin à droite.

Remarque 3.5.2. Dans le cas du monoïde libre A∗ , un sous-ensemble X de A∗ est dense

à droite si et seulement si tout mot de A∗ est préfixe d’un mot de X. Ainsi, tout idéal à
gauche de A∗ est dense à droite.
L’ensemble X est complet à droite si tout mot w ∈ A∗ peut s’écrire

w = x 1 x2 · · · xn p

pour x1 , . . . , xn ∈ X (n ≥ 0) et p un préfixe d’un mot de X.

Proposition 3.5.3. Soit X ⊂ A∗ . Les conditions suivantes sont équivalentes :

1. L’ensemble XA∗ est dense à droite.
2. A∗ = XA− ∪ X ∪ XA+ .
3. Pour tout w ∈ A∗ , il existe u, v ∈ A∗ et x ∈ X tels que wu = xv.

Démonstration. On a les implications suivantes :

1 ⇒ 3 : Soit w ∈ A∗ . L’ensemble XA∗ étant dense à droite, nous avons

XA∗ ∩ wA∗ 6= ∅.

Il existe donc un mot w0 ∈ XA∗ ∩ wA∗ . Ainsi, w0 = xv = wu pour des mots x ∈ X

et u, v ∈ A∗ .
3 ⇒ 2 : L’inclusion XA− ∪ X ∪ XA+ ⊂ A∗ est évidente. Soit w ∈ A∗ . Il existe u, v ∈ A∗ et
x ∈ X tels que wu = xv.
Cas 1 : Si w ≺ x, alors il existe w0 ∈ A+ tel que ww0 = x. Ainsi, w ∈ XA− .
 68 CHAPITRE 3. CODES PRÉFIXES

Cas 2 : Si w = x, alors w ∈ X.
Cas 3 : Si x ≺ w, alors il existe v 0 ∈ A+ tel que xv 0 = w. Ainsi, w ∈ XA+ .
Ainsi, w ∈ XA− ∪ X ∪ XA+ .
2 ⇒ 1 : L’ensemble des préfixes de XA∗ est XA− ∪ X ∪ XA+ = A∗ . Ainsi, soit w ∈ A∗ , il
existe u ∈ A∗ tel que wu ∈ XA∗ . Le mot w est donc complétable à droite dans XA∗ .

Proposition 3.5.4. Soit X ⊂ A+ . L’ensemble XA∗ est dense à droite si et seulement si

X est complet à droite.

Démonstration. Supposons que XA∗ est dense à droite et considérons un mot w ∈ A∗ =

XA− ∪ X ∪ XA+ . Montrons par récurrence sur la longueur de w que w est complétable à
droite dans X ∗ .
• Cas de base : |w| = 0, i.e. w = ε.
Alors w ∈ X ∗ .
• Induction : Supposons que pour tout v ∈ A∗ tel que |v| < |w|, v est complétable à
droite dans X ∗ .
— Cas 1 : w ∈ XA− ∪ X. Alors, on a directement qu’il existe u ∈ A∗ tel que
wu ∈ X ∈ X ∗ .
— Cas 2 : w ∈ XA+ . Alors il existe x ∈ X et v ∈ A+ tels que w = xv. On a x 6= ε,
donc |v| < |w|. Par hypothèse de récurrence, il existe u ∈ A∗ tel que vu ∈ X ∗ .
Il vient alors wu = |{z} vu ∈ X ∗ .
x |{z}
∈X ∈X ∗
Réciproquement, supposons que w ∈ A∗ . Par hypothèse, wu ∈ X ∗ pour un certain
u ∈ A∗ . Quitte à concaténer ce dernier avec un mot de X, on a wu 6= ε. Ainsi, wu ∈ X + ⊂
XA∗ .

Remarque 3.5.5. Si X = {ε}, alors XA∗ = A∗ . Or A∗ est dense à droite alors que X
n’est pas complet à droite puisque X ∗ = {ε} n’est pas dense à droite. Ceci montre donc
que la proposition précédente ne se généralise pas au cas X ⊂ A∗ .

Nous allons démontrer l’analogue de la Proposition 3.1.5 dans le cas des ensembles
préfixes maximaux. Considérons les familles suivantes :
1. La famille M des ensembles préfixes maximaux ;
2. La famille D des idéaux à droite qui sont denses à droite ;
3. La famille P des ensembles fermés par préfixe qui ne contiennent pas d’idéaux à
droite.

Proposition 3.5.6. Nous avons les bijections suivantes :

1. L’application f 0 : X 7→ XA∗ est une bijection de M dans D. L’application g 0 : I 7→
I\IA+ est son inverse de D dans M.
3.5. CODES PRÉFIXES MAXIMAUX 69

2. L’application h0 : P 7→ A∗ \P est une bijection de P dans D. L’application i0 : I 7→

A∗ \I est son inverse de D dans P.
3. L’application j 0 : X 7→ XA− est une bijection de M dans P. L’application k 0 : P 7→
(P A ∪ {ε})\P est son inverse de P dans M.

Démonstration. Remarquons que ces applications ne sont que les restrictions des applica-
tions définies dans la Proposition 3.1.5. C’est évident pour celles des points 1 et 2, nous le
vérifierons ci-dessous pour le point 3.
1. Soit X un ensemble préfixe maximal. Tout mot u ∈ A∗ est comparable pour l’ordre
préfixe avec un mot de X. En effet, supposons que u et x sont incomparables pour
tout x ∈ X, i.e. x n’est pas préfixe de u et u n’est pas préfixe de x. Alors X ∪ {u}
est encore un ensemble préfixe, ce qui contredit la maximalité de X. On a alors
Cas 1 : Si u ≺ x alors il existe u0 ∈ A∗ tel que uu0 = x ∈ X ⊂ XA∗ .
Cas 2 : Si u = x alors u ∈ X ⊂ XA∗ .
Cas 3 : Si x ≺ u alors il existe v ∈ A∗ tel que xv = u ∈ XA∗ .
On en conclut donc que XA∗ est dense à droite.
Soit I un idéal à droite qui est dense à droite. Vu la Proposition 3.1.3 nous savons
déjà que l’ensemble I\IA+ est préfixe. Montrons que pour tout w ∈ A∗ , il existe
i ∈ I\IA+ tel que w est comparable avec i.
Soit w ∈ A∗ . Puisque I est dense à droite, il existe u ∈ A∗ tel que wu ∈ I. Soit i
/ IA+ . On a donc soit i ≺ w soit
le plus petit préfixe de wu tel que i ∈ I. Alors i ∈
i = w soit w ≺ i.
Ainsi, I\IA+ est un ensemble préfixe maximal.
2. Soit I un idéal à droite qui est dense à droite. On sait déjà, vu la Proposition 3.1.5,
que A∗ \I est fermé par préfixe. Montrons alors que A∗ \I ne contient pas d’idéal à
droite.
Procédons par l’absurde et supposons que I 0 ⊂ A∗ \I est un idéal à droite. Soit i0 ∈ I 0 .
On a alors i0 w ∈ I 0 pour tout w ∈ A∗ , ce qui contredit le fait que I est dense à droite
puisque i0 n’est pas complétable à droite dans I.
Soit P un ensemble fermé par préfixe ne contenant pas d’idéal à droite. On sait déjà,
vu la Proposition 3.1.5, que A∗ \P est un idéal à droite. Montrons alors que A∗ \P est
dense à droite.
Soit w ∈ A∗ . Puisque wA∗ est un idéal à droite, on sait que wA∗ 6⊂ P . Il existe donc
u ∈ wA∗ \P . Dès lors, u = wv pour un certain v ∈ A∗ . Donc wv ∈ A∗ \P , ce qui
montre que w est complétable dans A∗ \P .
3. Soit X un ensemble préfixe maximal. Vu le point 1, on sait que XA∗ est dense à
droite. Par la Proposition 3.1.2, on sait que X, XA+ et XA− sont des ensembles
disjoints deux-à-deux et par la Proposition 3.5.3, on sait que A∗ = XA− ∪ X ∪ XA+ .
Il vient alors :
A∗ \XA∗ = A∗ \(X ∪ XA+ ) = XA− .
70 CHAPITRE 3. CODES PRÉFIXES

Ainsi, j 0 = i0 ◦ f 0 est bien une bijection de M dans P.

Soit P un ensemble fermé par préfixe qui ne contient pas d’idéal droite. On a

g 0 ◦ h0 : P → M, P 7→ (A∗ \P )\(A∗ \P )A+ .

Vu la Proposition 3.1.5, on sait que (P A ∪ {ε})\P = (A∗ \P )\(A∗ \P )A+ . Ainsi,

k 0 = g 0 ◦ h0 est bien une bijection de P dans M.

Corollaire 3.5.7. Soient Y ⊂ A+ et X = Y \Y A+ . L’ensemble Y est complet à droite si

et seulement si X est un code préfixe maximal.

Démonstration. Vu la Proposition 3.5.4, Y est complet à droite si et seulement si Y A∗ est

dense à droite. Vu la Proposition 3.1.3, on sait que X est un ensemble préfixe et Y A∗ =
XA∗ . Ainsi, XA∗ est un idéal à droite qui est dense à droite. Par conséquent XA∗ \(XA∗ )A+
est un ensemble préfixe maximal vu la proposition précédente. Or XA∗ \(XA∗ )A+ =
XA∗ \XA+ = (X ∪XA+ )\XA+ . De plus, nous savons que X ∪XA+ est une union disjointe
puisque X est un ensemble préfixe. Ainsi, XA∗ \(XA∗ )A+ = X.
Ce corollaire nous fournit trivialement le résultat suivant :

Théorème 3.5.8. Soit X un code préfixe. L’ensemble X est complet à droite si et seule-
ment si X est un code préfixe maximal.

Nous pouvons exprimer la maximalité d’un code préfixe en termes de séries formelles
comme le montre le théorème suivant.

Théorème 3.5.9. Soient X un code préfixe sur A et P = XA− l’ensemble des préfixes
propres des mots de X. L’ensemble X est préfixe maximal si et seulement si on a les
conditions équivalentes suivantes :

X − ε = P (A − ε) (3.5)

et
A∗ = X ∗ P . (3.6)

Démonstration. Posons R = A∗ \XA∗ . Si X est préfixe maximal alors XA∗ est dense à
droite. Par la Proposition 3.1.2, nous savons que les ensembles XA− , X, XA+ sont disjoints
deux à deux. Ainsi, grâce à la Proposition 3.5.3, il vient

R = A∗ \XA∗ = A∗ \(XA+ ∪ X) = XA− = P.

Ainsi, par la Proposition 3.2.2, il vient directement que X − ε = P (A − ε).

Inversement, si X − ε = P (A − ε), vu la Proposition 3.2.2, il vient

P (A − ε) = R(A − ε).
 3.5. CODES PRÉFIXES MAXIMAUX 71

De plus, on sait que (A − ε) est inversible. On a alors P = R. Il s’ensuit que

A∗ \(XA+ ∪ X) = XA−
⇔ A∗ = XA− ∪ X ∪ XA+ .
Ainsi, XA∗ est dense à droite.
Observons que lorsque X est un code préfixe maximal fini, alors P est également fini
et donc P est un polynôme. Ainsi, l’ équation 3.5 nous donne une factorisation de X − ε
en deux polynômes.
Remarque 3.5.10. L’équation 3.5 peut se réécrire X + P = ε + P A. Sous cette forme,
la maximalité d’un code préfixe X peut se vérifier aisément à partir de sa représentation
littérale. En effet, nous allons montrer que X est un code préfixe maximal si et seulement
si pour tout nœud p qui n’est pas dans X, on a pour tout a ∈ A, pa qui est un nœud
dans la représentation littérale de X, i.e. X est un code préfixe maximal si et seulement si
∀p ∈ P et a ∈ A, pa ∈ X ∪ P .
Supposons que X est un code préfixe maximal. On sait alors que X + P = ε + P A.
Soient p ∈ P et a ∈ A. Le mot pa ∈ P A, il vient alors que (P A, pa) = 1. Puisque pa 6= ε,
on a même (P A + ε, pa) = 1. Puisque les ensembles X et P sont disjoints, vu que X est
préfixe, il s’ensuit que (X + P , pa) = (X ∪ P , pa) = 1. Ainsi, pa ∈ X ∪ P .
Réciproquement, supposons que pour tous p ∈ P et a ∈ A, pa ∈ X ∪ P . Montrons que
w ∈ X ∪ P si et seulement w ∈ P A ∪ {ε}.
Soit w ∈ X ∪ P . Si w = ε, alors w ∈ P A ∪ {ε}. Sinon, w = pa où p est un préfixe de
w ∈ X ∪ P . Donc p ∈ P . On en tire w ∈ P A.
Soit w ∈ P A ∪ {ε}. Si w = ε, alors w ∈ P . Sinon, si w ∈ P A, alors w = pa pour p ∈ P et
a ∈ A. Par hypothèse, on a alors que w ∈ X ∪ P .
Nous allons maintenant montrer que dans le cas particulier d’ensembles fins, un code
préfixe maximal est aussi un code maximal.
Théorème 3.5.11. Soit X un sous-ensemble fin de A+ . Les assertions suivantes sont
équivalentes :
1. L’ensemble X est un code préfixe maximal.
2. L’ensemble X est préfixe et un code maximal.
3. L’ensemble X est complet à droite et un code.
Démonstration. L’implication 2 ⇒ 1 est évidente.
1 ⇒ 3 : Soit X un code préfixe maximal. Alors, vu la Proposition 3.5.6, XA∗ est dense à
droite. Par la Proposition 3.5.4, on en tire que X est complet à droite.
3 ⇒ 2 : Soit Y = X\XA+ . Vu la Proposition 3.1.3, on sait que Y est préfixe et que XA∗ =
Y A∗ . Par la Proposition 3.5.4, XA∗ est dense à droite. Il s’ensuit, par la même
proposition, que Y est complet à droite et par conséquent, Y est complet. Puisque
Y ⊂ X, avec X fin, l’ensemble Y est fin également. Par le Théorème 2.2.20, Y est
un code maximal. Il vient alors Y = X.
 72 CHAPITRE 3. CODES PRÉFIXES

La proposition suivante découle directement des Théorèmes 3.5.11 et 2.2.25.

Proposition 3.5.12. Soit X un sous-ensemble fin de A+ . Les assertions suivantes sont

équivalentes :
1. L’ensemble X est un code préfixe maximal.
2. L’ensemble X est préfixe et il existe une loi de Bernoulli positive π telle que π(X) = 1.
3. L’ensemble X est préfixe et π(X) = 1 pour toute loi de Bernoulli positive π.

Pour terminer cette section, nous allons caractériser les codes préfixes maximaux au
moyen des automates acceptant les sous-monoïdes qu’ils engendrent.

Définition 3.5.13. Un état q d’un automate déterministe A = {Q, q0 , F, A, δ} est récur-

rent si pour tout u ∈ A∗ il existe un mot v ∈ A∗ tel que δ(q, uv) = q.

Proposition 3.5.14. Soit X un code préfixe sur A. Les assertions suivantes sont équiva-
lentes :
1. L’ensemble X est préfixe maximal.
2. L’automate minimal de X ∗ est coaccessible.
3. Tous les états de l’automate minimal de X ∗ sont récurrents.
4. L’état initial de l’automate minimal de X ∗ est récurrent.
5. L’ensemble X ∗ est le stabilisateur d’un état récurrent d’un automate déterministe.

Démonstration.
1 ⇒ 2 : Soit AX ∗ = (QX ∗ , q0,X ∗ , q0,X ∗ , A, δX ∗ ) l’automate minimal de X ∗ . Soit q ∈ QX ∗ .
Puisque AX ∗ est accessible, il existe un mot u ∈ A∗ tel que δX ∗ (q0,X ∗ , u) = q. Par le
Théorème 3.5.8, X est complet à droite. Ainsi u est complétable à droite dans X ∗ , donc
il existe un mot v ∈ A∗ tel que uv ∈ X ∗ . Il vient que δX ∗ (q, v) = δX ∗ (δX ∗ (q0,X ∗ , u), v) =
δX ∗ (q0,X ∗ , uv) = q0,X ∗ . L’état q est donc coaccessible.
2 ⇒ 3 : Soit q ∈ QX ∗ et u ∈ A∗ . Puisque AX ∗ est accessible, il existe v ∈ A∗ tel que
δX ∗ (q0,X ∗ , v) = q. Par hypothèse, l’automate minimal est coaccessible, il existe donc w ∈ A∗
tel que δX ∗ (δX ∗ (q, u), w) = q0,X ∗ . Ainsi δX ∗ (q, uwv) = δX ∗ (q0,X ∗ , v) = q.
3 ⇒ 4 : Évident.
4 ⇒ 5 : On a X ∗ = L(AX ∗ ) = {w ∈ A∗ |δX ∗ (q0,X ∗ , w) = q0,X ∗ } = Stab(q0,X ∗ ) et q0,X ∗ est
récurrent par hypothèse.
5 ⇒ 1 : Soient A = (Q, i, F, A, δ) un automate déterministe et q ∈ Q un état récurrent tel
que X ∗ = Stab(q) = {w ∈ A∗ |δ(q, w) = q}. Soit u ∈ A∗ , il existe v ∈ A∗ tel que δ(q, uv) =
q, puisque q est récurrent. Ainsi, uv ∈ Stab(q) = X ∗ . Il vient alors que X est complet à
droite. Ainsi, par le Théorème 3.5.8, l’ensemble X est un code préfixe maximal.
3.6. QUELQUES OPÉRATIONS SUR LES ENSEMBLES PRÉFIXES 73

3.6 Quelques opérations sur les ensembles préfixes

Proposition 3.6.1. Soient X et (Yi )i∈I des sous-ensembles de A∗ . Soit (Xi )i∈I une parti-
tion de X. Posons [
Z= Xi Yi .
i∈I

1. Si X et les Yi sont préfixes (resp. préfixes maximaux) alors Z est préfixe (resp. préfixe
maximal).
2. Si Z est préfixe alors tous les Yi sont préfixes.
3. Si X est préfixe et Z est préfixe maximal, alors X et les Yi sont préfixes maximaux.

Démonstration. 1. Supposons que z, zu ∈ Z. Il existe alors x ∈ Xi , y ∈ Yi et x0 ∈ Xj ,

y 0 ∈ Yj , avec i, j ∈ I, tels que z = xy et zu = x0 y 0 . On a alors zu = xyu = x0 y 0 .
Puisque X est préfixe, il vient que x = x0 . Il en découle i = j. On a alors y, y 0 ∈ Yi
avec y  y 0 . Étant donné que Yi est préfixe, il vient y = y 0 . Par conséquent u = ε.
L’ensemble Z est donc préfixe.
Supposons maintenant que X et les Yi sont préfixes maximaux. Par la Proposition
3.5.6, les ensembles XA∗ et Yi A∗ sont des ensembles denses à droite. Soit w ∈ A∗ .
Par la Proposition 3.5.3, il existe w0 , v ∈ A∗ et x ∈ X tels que

ww0 = xv.

Soit i ∈ I tel que x ∈ Xi . Puisque Yi A∗ est dense à droite, il existe v 0 ∈ A∗ tel que
vv 0 ∈ Yi A∗ . Donc ww0 v 0 = xvv 0 ∈ Xi Yi A∗ ⊂ ZA∗ , ce qui montre que ZA∗ est dense
à droite. Par la Proposition 3.5.6, l’ensemble Z est préfixe maximal.
2. Soient y, yu ∈ Yi et x ∈ Xi avec i ∈ I. On a xy, xyu ∈ Z. Or Z est préfixe donc
u = ε, ce qui montre que les ensembles Yi sont donc bien préfixes.
3. Puisque Z est préfixe maximal, on sait que ZA∗ est dense à droite. Étant donné que
ZA∗ ⊂ XA∗ , on en tire que XA∗ est également dense à droite. Ainsi, X est préfixe
maximal. Pour montrer que les Yi sont préfixes maximaux, nous allons montrer que
Yi A∗ est dense à droite.
Soit w ∈ A∗ . Pour tout x ∈ Xi , xw est complétable à droite dans ZA∗ . Il existe alors
t ∈ A∗ tel que xwt ∈ ZA∗ . Donc il existe z ∈ Z et u ∈ A∗ tels que xwt = zu. Il
existe alors x0 ∈ Xj et y 0 ∈ Yj tels que z = x0 y 0 . Il vient alors xwt = x0 y 0 u. Puisque
X est préfixe on a x = x0 . Il s’ensuit que i = j et donc wt = y 0 u ∈ Yi A∗ . Ainsi, w est
complétable à droite dans Yi A∗ .

Corollaire 3.6.2. Si X et Y sont des codes préfixes (resp. codes préfixes maximaux) alors
XY est un code préfixe (resp. code préfixe maximal).

Corollaire 3.6.3. Soient X ⊂ A+ et n ≥ 1. L’ensemble X est préfixe (resp. préfixe

maximal) si et seulement si X n est préfixe (resp. préfixe maximal).
74 CHAPITRE 3. CODES PRÉFIXES

Démonstration. Supposons que X est un code préfixe (resp. code préfixe maximal). Par le
corollaire précédent, le produit X n est un code préfixe (resp. code préfixe maximal).
Inversement, supposons que X n est préfixe. Puisque X n = X n−1 X, par le point 2 de la
Proposition 3.6.1, il vient que X est préfixe. Dans le cas où X n est préfixe maximal, alors
on conclut par le point 3 que X est préfixe maximal.

3.7 Codes sémaphores

Cette dernière section est dédiée à un sous-ensemble particulier des codes préfixes : les
codes sémaphores. Après avoir défini cette nouvelle notion et donné quelques caractérisa-
tions et propriétés, nous pourrons finalement démontrer le Théorème 3.7.15 propre à cette
nouvelle famille.
Proposition 3.7.1. Pour tout ensemble non vide S ⊂ A+ , l’ensemble

X = (A∗ S)\(A∗ S)A+ (3.7)

est un code préfixe maximal.

Démonstration. L’ensemble A∗ S est le plus petit idéal à gauche de A∗ engendré par S. Vu
la Remarque 3.5.2, on sait que A∗ S est dense à droite et par conséquent complet à droite.
On conclut alors que X est un code préfixe maximal par le Corollaire 3.5.7.

Définition 3.7.2. Un code X de la forme 3.7 est appelé un code sémaphore. L’ensemble
S ⊂ A+ est l’ensemble des sémaphores de X.
Soit X = (A∗ S)\(A∗ S)A+ un code sémaphore. Un mot x est dans X si et seulement
s’il se termine par un sémaphore mais qu’aucun de ses préfixes propres ne se finit par un
sémaphore.
On justifie l’emploi du terme « sémaphore » de la façon suivante : lorsqu’on lit un mot
de X ∗ , chaque occurrence d’un sémaphore dans ce mot est un « signal » indiquant la fin
d’un facteur dans la décomposition en mots de X 1 .

Les quelques propositions suivantes nous donnent des caractérisations des codes séma-
phores. Nous rappelons au lecteur que dans le cas où X ⊂ A+ , l’ensemble X est préfixe si
et seulement si X est un code préfixe.
Proposition 3.7.3. Soit X ⊂ A+ non vide. L’ensemble X est un code sémaphore si et
seulement si X est préfixe et A∗ X ⊂ XA∗ .
Démonstration. Supposons tout d’abord que X est un code sémaphore. Il existe alors
S ⊂ A+ non vide tel que X = (A∗ S)\(A∗ S)A+ . Par définition, on sait directement que X
est un code préfixe. Montrons donc que A∗ X ⊂ XA∗ .
1. Tout comme un sémaphore ferroviaire indique la fin d’un canton.
3.7. CODES SÉMAPHORES 75

Soit w ∈ A∗ X ⊂ A∗ S. Le mot w possède donc un facteur dans S. Soit w0 le plus

petit préfixe de w qui est dans A∗ S. On a alors w0 ∈ X. Ainsi, il existe u ∈ A∗ tel que
w = w0 u ∈ XA∗ .
Supposons maintenant que X est un code préfixe et que A∗ X ⊂ XA∗ . Posons M =
XA∗ . Par la Proposition 3.1.5, puisque X est préfixe, on sait que X = XA∗ \(XA∗ )A+ =
M \M A+ . On a alors
A∗ M = A∗ XA∗ ⊂ XA∗ = M.
Donc M = A∗ M et X = (A∗ M )\(A∗ M )A+ , ce qui montre que X est un code sémaphore.

L’exemple suivant nous montre qu’être un code préfixe maximal n’est pas suffisant pour
être un code sémaphore.

Exemple 3.7.4. Considérons l’ensemble X = {a2 , aba, ab2 , b} sur l’alphabet A = {a, b}.
Il s’agit d’un code préfixe. On sait aussi que l’ensemble X étant fini, il est fin. De plus, la
loi uniforme de Bernoulli sur A est telle que

π(X) = π(a)π(a) + π(a)π(b)π(a) + π(a)π(b)π(b) + π(b)

1 1 1 1
= + + +
4 8 8 2
= 1.

Ainsi par la Proposition 3.5.12, X est un code préfixe maximal. Cependant, X n’est pas
un code sémaphore puisque ab ∈ A∗ X mais ab ∈ / XA∗ .

Proposition 3.7.5. Soit X ⊂ A+ . L’ensemble X est un code sémaphore si et seulement

si X est complet à droite et X ∩ A∗ XA+ = ∅.

Démonstration. Supposons que X est un code sémaphore. S’agissant d’un code préfixe
maximal, il est complet à droite vu le Théorème 3.5.8. Montrons alors que X ∩A∗ XA+ = ∅.
Vu la proposition précédente, on sait que A∗ X ⊂ XA∗ . On a donc A∗ XA+ ⊂ XA+ . Ainsi,
il vient
X ∩ A∗ XA+ ⊂ X ∩ XA+ .
L’ensemble X étant préfixe, nous savons, grâce à la Proposition 3.1.2, que X ∩ XA+ = ∅,
d’où la conclusion.
Supposons maintenant que X est complet à droite et que X ∩ A∗ XA+ = ∅. Puisque
X ∩ XA+ ⊂ X ∩ A∗ XA+ = ∅, on en tire que X est préfixe par la Proposition 3.1.2. Pour
vérifier que X est bien un code sémaphore, nous allons montrer que A∗ X ⊂ XA∗ . Soit
w = ux ∈ A∗ X avec u ∈ A∗ et x ∈ X. L’ensemble X étant complet à droite, il existe un
mot v ∈ A∗ tel que uxv ∈ X ∗ . Il existe donc x0 ∈ X et y 0 ∈ X ∗ tels que uxv = x0 y 0 . Puisque
X ∩ A∗ XA+ = ∅, ux n’est pas un préfixe propre de x0 . Ainsi, ux ∈ x0 A∗ ⊂ XA∗ .

Corollaire 3.7.6. Soient X ⊂ A+ un code sémaphore et P = XA− . On a alors P X ⊂

XP ∪ X 2 .
76 CHAPITRE 3. CODES PRÉFIXES

Démonstration. Soient p ∈ P et x ∈ X. On a px ∈ P X ⊂ A∗ X ⊂ XA∗ . Il existe donc

y ∈ X et u ∈ A∗ tels que px = yu. L’ensemble X étant un code préfixe, on a |p| < |y|.
En effet, si |p| ≥ |y|, alors y est préfixe de p qui est lui-même un préfixe d’un mot de X.
Ainsi, y est préfixe d’un mot de X, ce qui contredit le fait que X est préfixe. Dès lors,
u est un suffixe propre de x et vu que X ∩ A∗ XA+ = ∅, u ∈ / XA+ . Étant donné que X
est un code préfixe maximal, nous savons, par la Proposition 3.5.6, que XA∗ est dense à
droite. Ainsi, par la Proposition 3.5.3, on sait alors que A∗ = XA− ∪ X ∪ XA+ . Il vient
alors u ∈ XA− ∪ X = P ∪ X. On obtient finalement px = yu ∈ X(P ∪ X).

Soit X un code sémaphore. La condition X ∩ A∗ XA+ = ∅ impose non seulement que

X est préfixe, c’est-à-dire qu’aucun mot de X n’est préfixe d’un autre mot de X, mais
également qu’aucun mot de X n’est facteur d’un autre mot de X sauf s’il en est un suffixe.
Autrement dit, soient x, x0 deux éléments de X, la seule possibilité pour que x apparaisse
comme facteur de x0 est que x soit suffixe de x0 .

Proposition 3.7.7. Soient X ⊂ A+ et P = XA− . L’ensemble X est un code sémaphore

si et seulement si X est un code préfixe maximal et P est fermé par suffixe.

Démonstration. Supposons que X est un code sémaphore. On sait donc que c’est un code
préfixe maximal. Montrons que P est fermé par suffixe.
Soit p = uq ∈ P avec u, q ∈ A∗ . Par définition de P , il existe un mot v ∈ A+ tel que
pv ∈ X. Le mot q ne peut pas être dans XA∗ sinon pv = uqv ∈ X ∩ A∗ XA+ = ∅. Il
s’ensuit que q ∈ A∗ \XA∗ . Or, on sait par la Proposition 3.7.5 que X est complet à droite.
Ainsi, XA∗ est dense à droite et A∗ = XA− ∪ X ∪ XA+ . Il vient donc q ∈ XA− = P .
Inversement, supposons que X est un code préfixe maximal et que P est fermé par
suffixe. Par le Théorème 3.5.8, X est complet à droite. Nous allons montrer que X ∩
A∗ XA+ = ∅ et grâce à la Proposition 3.7.5 nous pourrons conclure que X est un code
sémaphore.
Procédons par l’absurde. Supposons qu’il existe x ∈ X ∩A∗ XA+ . Il existe donc u ∈ A∗ , x0 ∈
X et v ∈ A+ tels que x = ux0 v. On a alors que ux0 ∈ P . L’ensemble P étant fermé par
suffixe, il vient que x0 ∈ P , ce qui contredit le fait que X est préfixe.

Proposition 3.7.8. Tout code sémaphore est fin.

Démonstration. Soit X un code sémaphore. On a alors X ∩ A∗ XA+ = ∅. Ainsi, aucun mot

de XA+ n’est facteur d’aucun mot de X. On conclut donc par la Remarque 2.2.4 que X
n’est pas dense.

Corollaire 3.7.9. Tout code sémaphore est un code maximal.

Proposition 3.7.10. Deux sous-ensembles non vides S et T de A+ définissent le même

code sémaphore si et seulement si A∗ SA∗ = A∗ T A∗ .
Pour tout code sémaphore X, il existe un unique ensemble minimal de sémaphores :
T = X\A+ X.
3.7. CODES SÉMAPHORES 77

Démonstration. Soient X = A∗ S\A∗ SA+ et Y = A∗ T \A∗ T A+ deux codes sémaphores.

Par la Proposition 3.1.3, il vient XA∗ = A∗ SA∗ et Y A∗ = A∗ T A∗ . Par le Corollaire 3.1.6,
on sait que XA∗ = Y A∗ si et seulement si X = Y .
Montrons maintenant que T = X\A+ X est un ensemble de sémaphores de X. Soit X =
A∗ S\A∗ SA+ un code sémaphore. En utilisant la Proposition 3.1.3 adaptée aux ensembles
suffixes 2 , nous avons A∗ T = A∗ X. Il vient alors A∗ T A∗ = A∗ XA∗ = A∗ SA∗ , ce qui
implique que T et S définissent le même code sémaphore X, i.e. X = A∗ T \A∗ T A+ .
Finalement, montrons que T est bien minimal. Soit S ⊂ A+ tel que X = A∗ S\A∗ SA+ =
A T \A∗ T A+ . Soit t ∈ T . Puisque A∗ T A∗ = A∗ SA∗ , il existe u, v ∈ A∗ et s ∈ S tels que
∗

t = usv. De plus, il existe u0 , v 0 ∈ A∗ et t0 ∈ T tels que s = u0 t0 v 0 . On a alors t = uu0 t0 v 0 v.

Par définition T ⊂ X donc v 0 v = ε puisque X ∩ A∗ XA+ = ∅. De plus, on sait que T est
un code suffixe2 , donc uu0 = ε. Il vient donc t = t0 = s ∈ S.
Étudions maintenant quelques opérations sur les codes sémaphores.

Proposition 3.7.11. Si X et Y sont des codes sémaphores, alors XY est un code séma-
phore.
Inversement, si XY est un code sémaphore et si X est un code préfixe, alors X est un
code sémaphore.

Démonstration. Supposons que X et Y sont des codes sémaphores. Par le Corollaire 3.6.2,
XY est un code préfixe. Vu la Proposition 3.7.3, pour montrer que XY est un code sé-
maphore, il nous reste à montrer que A∗ XY ⊂ XY A∗ . Puisque X et Y sont des codes
sémaphores, on a A∗ X ⊂ XA∗ et A∗ Y ⊂ Y A∗ . Il vient donc

A∗ XY ⊂ XA∗ Y ⊂ XY A∗ .

Inversement, supposons que XY est un code sémaphore et que X est un code préfixe.
Pour montrer que X est un code sémaphore, il nous reste à montrer que A∗ X ⊂ XA∗ .
Soit w = ux ∈ A∗ X avec u ∈ A∗ et x ∈ X. Soit y un mot de Y supposé de longueur
minimale. Puisque XY est sémaphore, on a A∗ XY ⊂ XY A∗ . Il vient alors wy = uxy =
x0 y 0 u0 , pour x0 ∈ X, y 0 ∈ Y et u0 ∈ A∗ . Étant donné que y est de longueur minimale, on a
|y| ≤ |y 0 | ≤ |y 0 u0 | et par conséquent |ux| ≥ |x0 |, ce qui montre que ux ∈ XA∗ .
Si XY est un code sémaphore, alors Y n’est, quant à lui, pas nécessairement sémaphore,
comme nous le montre l’exemple suivant.

Exemple 3.7.12. Soient X = a∗ b et Y = {a2 , aba, ab2 , b} des ensembles définis sur l’al-
phabet A = {a, b}. Comme nous l’avons vu dans l’Exemple 3.7.4, Y est un code préfixe
maximal mais n’est pas un code sémaphore. Par contre, l’ensemble X est un code séma-
phore. En effet, nous voyons que X est préfixe. De plus, soit w ∈ A∗ X. Il existe u ∈ A∗ et
n ∈ N tels que
w = uan b.
2. Pour tout ensemble Y ⊂ A∗ , l’ensemble X = Y \A+ Y est suffixe. De plus, A∗ X = A∗ Y et X est
l’ensemble minimum avec cette propriété.
78 CHAPITRE 3. CODES PRÉFIXES

• Si u commence par a, après avoir lu une première occurrence de b dans w (dans u ou

non), nous avons un préfixe de w dans X. On a donc w ∈ XA∗ .
• Si u commence par b, cette première lettre est notre préfixe dans X. Ainsi, w ∈ XA∗ .
• Si u = ε, on a directement w ∈ X ⊂ XA∗ .
Ainsi, par la Proposition 3.7.3, X est bien un code sémaphore.
L’ensemble Z = XY est un code sémaphore. En effet, grâce au Corollaire 3.6.2, on sait
que Z est un ensemble préfixe maximal. De plus, l’ensemble ZA− = a∗ ∪ a∗ b ∪ a∗ ba ∪ a∗ bab
est fermé par suffixe. Par la Proposition 3.7.7, l’ensemble Z est bien sémaphore.

Corollaire 3.7.13. Pour tous X ⊂ A+ et n ≥ 1, l’ensemble X est un code sémaphore si

et seulement si X n est un code sémaphore.

Démonstration. Si X est un code sémaphore, alors il découle directement de la proposition

précédente que X n est un code sémaphore.
Inversement, si X n est un code sémaphore, alors par le Corollaire 3.6.3 l’ensemble X
est un code préfixe maximal. Par la proposition précédente, on en tire que X est un code
sémaphore.

Comme nous l’avons déjà mentionné, tous les résultats s’appliquant aux codes préfixes
sont adaptables au cas des codes suffixes. Il est clair que nous pouvons passer d’un code
préfixe à un code suffixe au moyen d’une bijection qui associe à un mot son miroir. Cepen-
dant, dans le cas des codes sémaphores, nous obtenons le résultat suivant, plus surprenant,
nous permettant de passer d’un code sémaphore à son dual, qui est alors suffixe, au moyen
d’une bijection associant à un mot l’un de ses conjugués.

Définition 3.7.14. Deux mots x et y sont conjugués s’il existe des mots u, v ∈ A∗ tels
que x = uv et y = vu. On dit que y est un conjugué de x.

Théorème 3.7.15. Soit S ⊂ A+ . Il existe une bijection β de X = A∗ S\A∗ SA+ dans

Y = SA∗ \A+ SA∗ telle que pour tout x ∈ X, β(x) est un conjugué de x.

Démonstration. Premièrement, considérons l’idéal J = A∗ SA∗ . On a alors

X = J\JA+ et Y = J\A+ J.

En effet, on a A∗ JA∗ = A∗ SA∗ et par la Proposition 3.7.10, il vient X = A∗ J\A∗ JA+ .

Puisque A∗ J = J, il vient que X = J\JA+ . On montre que Y = J\A+ J par un raisonne-
ment analogue.
Définissons ensuite, pour chaque x ∈ X,

D(x) = {d ∈ A+ |∃g ∈ A∗ tel que x = gd et dg ∈ J}.

L’ensemble D(x) ne contient donc que des suffixes de x. Remarquons que D(x) 6= ∅ puisque
x ∈ D(x). Ainsi, chaque D(x) contient un plus petit élément.
3.7. CODES SÉMAPHORES 79

Nous allons définir l’application β comme suit : pour x ∈ X

β(x) = dg,

où d est le plus petit mot de D(x) et g est tel que x = gd. De cette manière β(x) est bien
un conjugué de x et β(x) ∈ J. Montrons alors que β(x) ∈ J\A+ J = Y .
Supposons le contraire, supposons qu’il existe x ∈ X tel que

β(x) = dg = uj,

avec u ∈ A+ et j ∈ J. Puisque g est un préfixe propre de x, g ∈/ J. En effet, si g ∈ J alors

x = gd ∈ JA+ , ce qui contredit le fait que x ∈ X. Ainsi, |g| < |j|. Sinon, si |j| < |g|, il
existe v ∈ A∗ tel que g = vj. Or, J est un idéal donc vj ∈ J, ce qui contredit le fait que
g∈ / J. Donc on a forcément |d| > |u|. Il existe donc d0 ∈ A+ tel que d = ud0 . Cependant,
d ∈ D(x) puisque d0 gu = ju ∈ J et gud0 = gd = x. Ceci contredit donc le fait que d est le
0

plus petit mot de D(x). Donc β(x) ∈ Y , ce qui montre que l’application β est bien définie.
Considérons maintenant, pour y ∈ Y

G(y) = {e ∈ A+ |∃h tel que y = eh et he ∈ J}.

Définissons l’application inverse γ de Y dans X en posant

γ(y) = he

avec e ∈ G(y) supposé de longueur minimale et h tel que y = eh. Si y = β(x) = dg et si

γ(y) = he alors
dg = β(x) = eh.
Puisque x = gd ∈ J, on a d ∈ G(y). On en tire alors que |d| ≥ |e|. Mais e n’est pas un
préfixe propre de d. Sinon il existe u ∈ A+ tel que d = eu et ug = h. Il vient alors

geu = gd = x et uge = he ∈ J,

ce qui montre que u ∈ D(x) et contredit le fait que d est le plus petit mot de D(x). On en
déduit alors que d = e et g = h. On obtient donc

γ(β(x)) = γ(eh) = he = gd = x.

Par un raisonnement similaire, nous obtenons

β(γ(y)) = β(he) = β(gd) = dg = y.

Ainsi, les applications β et γ sont bien inverses l’une de l’autre, ce qui montre que β est
une bijection.
80 CHAPITRE 3. CODES PRÉFIXES

Exemple 3.7.16. Illustrons la construction de la preuve précédente. Soient A = {a, b} et

S = {a2 , ba, b2 } un ensemble de sémaphores. On a

X = A∗ S\A∗ SA+ = {a2 , ba, b2 , aba, ab2 }

et
Y = SA∗ \A+ SA∗ = {a2 , a2 b, ba, bab, b2 }.
Le tableau suivant nous fournit, pour chaque mot x de X, ses suffixes, l’ensemble D(x) et
son image par β.
x Suffixes 6= ε de x D(x) d g β(x)
aa a, aa a, aa a a aa
ba a, ba ba ba ε ba
bb b, bb b, bb b b bb
aba a, ba, aba a, ba, aba a ab aab
abb b, bb, abb b, bb, abb b ab bab

On constate effectivement que les mots de Y sont bien les images par β des mots de X.

Les codes sémaphores ont la propriété d’être en bijection avec un code suffixe par une
application qui associe à un mot l’un de ses conjugués. Ceci n’est pas vrai pour les codes
préfixes quelconques, comme nous le montre l’exemple suivant.

Exemple 3.7.17. Considérons l’ensemble X = {ab, ba, c, ac, bca} sur l’alphabet A =
{a, b, c}. Il est évident que c’est un code préfixe. Supposons qu’il existe une bijection β
de X dans un code suffixe Y qui à x associe un de ses conjugués.
x Conjugués
ab ab , ba
ba ba, ab
c c
ac ac, ca
bca bca, cab, abc

Il est clair, vu le tableau ci-dessus, que Y contient forcément c, ab et ba. De plus, il doit
contenir ca. Si ce n’est pas le cas, il contient alors ac et c contredisant le fait qu’il est
suffixe. Cependant, les conjugués de bca ont des suffixes égaux à c, ab, ca, ce qui montre
qu’une telle bijection β ne peut exister.
Bibliographie

[1] J. Berstel, D. Perrin, J. F. Perrot, et A. Restivo, Sur le théorème du défaut, J. Algebra

60 (1979), 169–180.
[2] Jean Berstel et Dominique Perrin, Theory of codes, 2002, disponible via
l’URL <[Link]
851&rep=rep1&type=pdf>.
[3] Jean Berstel, Dominique Perrin, et Christophe Reutenauer, Codes and automata, vol.
129, Cambridge : Cambridge University Press, 2010.
[4] Jean Berstel et Christophe Reutenauer, Noncommutative rational series with applica-
tions, vol. 137, Cambridge : Cambridge University Press, 2011.
[5] M. Lothaire, Algebraic combinatorics on words, vol. 90, Cambridge : Cambridge Uni-
versity Press, 2002.
[6] Michel Rigo, Automates et langages formels, 2009–2010, disponible via l’URL <http:
//[Link]/cours/main_autom.pdf>.

81