Définitions

un alphabet

un ensemble fini non vide dont les éléments sont appelés des lettres .

un mot

un mot sur un alphabet A est une suite finie d'éléments de A. La suite de zéro lettre est appelée le mot vide et noté ε.

• L'ensemble des mots sur l'alphabet A est noté A^*
• L'ensemble des mots sur l'alphabet A excepté le mot vide ε est noté A⁺
• A^{+} = A^{*} \setminus \epsilon

La longueur d'un mot x est la longueur de la suite associée au mot x et est notée |x|. On note x[i], avec 0 ≤ i ≤ |x|-1, la lettre à l'indice i de x avec par convention une numérotation des indices à partir de 0. L'indice i représente une position sur x si x ≠ ε. La j-ième lettre de x est la lettre à la position j-1 sur x et x=x[0]x[1]…x[|x|-1].

L'égalité de deux mots quelconques est définie par

L'ensemble des lettres sur lequel est formé le mot x est noté alph(x).

produit

concaténation

de deux mots x et y est le mot composé des lettres de x puis de celles de y dans cet ordre. Ce produit est noté xy ou x⋅y (pour faire apparaître une décomposition du mot résultant).

:: l'élément neutre pour le produit est ε.!!

puissance

Pour tout mot x et tout entier n ≥0, la n-ième puissance du mot x notée xⁿ est définie par

• x⁰ = ε
• x^k = x^k-1 ⋅x (k > 0)

Sont notés respectivement zy^-1 et x^-1z les mots x et y lorsque z = x⋅y.

renversé

image miroir

Le renversé (ou image miroir) du mot x est le mot x^~ défini par x^~ = x[|x|-1]x[|x|-2]…x[0]

!!

facteur

un mot x est un facteur d'un mot y s'il existe deux mots u et v tels que y = u⋅x⋅v .

préfixe

lorsque u = ε, x est un préfixe de y

suffixe

lorsque v = ε, x est un suffixe de y

propre

un facteur, préfixe ou suffixe x d'un mot y est qualifié de propre si x ≠ y.

Une occurrence d'un mot non vide x dans un mot y, apparaît lorsque x est un facteur de y. Une occurrence de x peut être caractérisée par une position sur y. Une occurrence de x débute à la position (gauche) i sur y lorsque y[i..i+|x|-1] = x. Il est également possible de considérer la position droite i+|x|-1 où l'occurrence se termine.

Les notations avec des crochets pour les lettres des mots sont étendues aux facteurs. On définit le facteur x[i..j] du mot x par x[i..j]=x[i≠x[i+1]…x[j] pour tous les entiers i et j satisfaisant

1. 0 ≤ i ≤ |x|
2. -1 ≤ j ≤ |x|-1
3. i ≤ j + 1

Lorsque i = j+1, le mot x[i..j] = x[j+1 ..j] = x[i..i-1], est vide.

langage

Tout sous-ensemble de A^* est un langage X sur l'alphabet A.

Le produit défini sur les mots est étendu aux langages en posant XY = X⋅Y = {xy : (x,y)∈ X × Y} pour tous les langages X et Y.

Similairement ¹⁾, la puissance définie sur les mots est étendue aux langages en posant X⁰ = {ε} et X^k=X^k-1 X avec k > 0.

• L'étoile de X est le langage X^* = \cup_{n\geq 0} X^n
• Le langage X⁺ est défini par X^+ = \cup{n\geq 1} X^n

La longueur définie sur les mots est étendue aux langages en posant |X| = \sum_{x\in X} |X| .

Les ensembles des facteurs, des préfixes et des suffixes des mots d'un langage X sont des langages particuliers notés respectivement Fact(X),Préf(X) et Suff(X).

: à rajouter

Soient x un mot non vide et n le plus grand des entiers k pour lequel Bord^k(x) est défini (soit Bordⁿ(x)=ε). Alors (Bord(x), Bord²(x)…Bordⁿ(x)) est la suite des bords de x classés par ordre décroissant de longueur, et (|x|-|Bord(x)|, |x|-|Bord²(x)|,…|x|-|Bordⁿ(x)|) est la suite des périodes de x classées par ordre croissant.

Soient x et y deux mots. S'il existe deux entiers naturels non nuls m et n tels que x^m = yⁿ alors x et y sont des puissances d'un certain mot z.

Trouver un exemple de x^m = yⁿ et x,y puissances de z.

• x = abab
• y = ababab
• x³ = y² = (ab)⁶ ⇒ z=ab

Un mot non vide est primitif si et seulement s'il n'est facteur de son carré qu'en tant que préfixe et suffixe.

• mot primitif : aba ou abaab
• mot non primitif : baba → ba⋅baba⋅ba ⇒ facteur au milieu, pas seulement en préfixe et suffixe

conjugués

Deux mots x et y sont conjugués s'il existe deux mots u et v tels que x = u⋅v et y = v⋅u. Deux mots conjugués ont la même longueur. La conjugaison et une relation d'équivalence. Elle n'est pas compatible avec le produit.

AAC → ACA → CAA → AAC ⇒ 20 classes de trinucléotides conjugués.

Deux mots non vides x et y sont conjugués si et seulement s'il existe un mot z tel que x⋅z=z⋅y.

Exemple de mot z pour AAC et ACA : z=A ⇐ AACz = zACA ⇔ AACA = AACA

search_2