séquence 209_2

4. Relations entre mots

Ici, nous présentons quelques relations classiques entre mots. Tout d'abord, intuitivement, un mot est préfixe (respectivement suffixe puis sous-chaîne) d'un autre mot, s'il en est un début (respectivement une fin, puis un morceau).

Préfixe, suffixe et sous-chaîne

Si x et y sont deux chaînes quelconques sur A, alors

x est un préfixe de y (x ∈ Pref(y)) s'il existe z dans A^* tel que y = xz, autrement dit x ∈ Pref(y) si et seulement si ∃z ∈ A*, y = xz;
x est un suffixe de y (x ∈ Suff(y)) s'il existe z dans A^* tel que y = zx, autrement dit x ∈ Suff(y) si et seulement si ∃ z ∈ A*, y = zx;
x est une sous-chaîne (ou facteur) de y s'il existe w et z dans A^* tel que y = wxz, autrement dit x ∈ Fact(y) si et seulement si ∃ w, z ∈ A*, y = wxz.

Si x ≠ y (c'est-à-dire si z ≠ ε), alors le préfixe ou le suffixe est dit propre.

Par exemple, dans la chaîne 001110, 00 est un préfixe, 10 est un suffixe et 0111 est une sous-chaîne.

Remarques :

De manière plus générale, x est un préfixe (facteur gauche) de x ⊕ y ⊕ z, z en est un suffixe (facteur droit) et y en est une sous-chaîne.

x, comme y et z peuvent très bien être vides,

ε est préfixe, suffixe et sous-chaîne de toute chaîne.

Pref(x) ⊆ Fact(x) et Suff(x) ⊆ Fact(x)

Occurrence

Une occurrence d'une chaîne x dans une chaîne y est une apparition de x à un endroit précis dans la chaîne y.

Par exemple, avec A = {a,b}, le mot y = ababababa comporte quatre occurrences de la sous-chaîne x = aba.

Par ailleurs, notons que dans A^* défini sur A = {x₁,x₂, ..., x_n}, il est possible de définir plusieurs relations d'ordre :

l'ordre préfixiel, ordre partiel définit par : u < v si et seulement si u est un préfixe propre de v ;

l'ordre lexicographique (ordre du dictionnaire), ordre total défini par : u < v si et seulement si u = wau₂ et v = wbv₂ tels que w ∈ A^*, a < b avec a et b ∈ A ; Autrement dit u<v si et seulement si u=aw, v=bz et (a<b) ou ((a=b) et (w<z)), a, b ∈ A et w,z ∈ A^* avec ε < t ∀t ∈ A⁺.
Tout ceci est valable si et seulement si ∀x_i, x_j ∈ A, x_i ≤ x_j si i ≤ j.

l'ordre hiérarchique, ordre total pour lequel les mots sont classés en premier lieu par longueur, puis pour les mots de même longueur, par ordre lexicographique.

Exercices et tests :

Exercice 4.1. Soit x=abbcc un mot sur l'alphabet A={a,b,c} :

Donner l'ensemble Pref(x)
Donner l'ensemble Suff(x)

Exercice 4.2. Soient u₁, u₂ et v trois mots de A*. Montrer que si u₁ ∈ Pref(v) et u₂ ∈ Pref(v) alors soit u₁ ∈ Pref(u₂), soit u₂ ∈ Pref(u₁).

Exercice 4.3. Soit les mots suivants sur l'alphabet A={a,b,c} :

a
abcd
bc
dbc
ab
cd
cdab
abdd

Trier ces mots selon les trois exemples d'ordre vus dans cette section. On supposera l'ordre suivant sur l'alphabet : a<b<c<d

mardi, 25/11/03 16:25